Презентация, доклад Теория графов конференция

правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?»

ЗАДАЧА
олимпиада - 2012

задач.

Задачи исследования:
рассмотреть решение задач при помощи графов;
научиться переводить задачи на язык графов;
сравнить традиционные методы решения задач с методами теории графов.

графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты), построении путей транспортировки и доставки, решении задач. Графы используют в связи с развитием теории вероятностей, математической логики и информационных технологий.

Гипотеза:
Использование теории графов делает решение многих логических и комбинаторных задач менее трудоемким.

Изображение генеалогического древа

Изображение созвездий

некоторые из которых соединены линиями.

При изображении графа не имеет значения расположение вершин на плоскости, кривизна и длина ребер.

Вершины графов обозначаются буквами или натуральными числами.
Ребра графа – пары чисел.

семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

«Мне была предложена задача об острове, расположенном в городе Кёнигсберге и окружённом рекой,
через которую перекинуто 7 мостов. Спрашивается, может ли
кто – нибудь непрерывно обойти их, проходя только однажды
через каждый мост…»
(Из письма Л. Эйлера итальянскому математику и инженеру
Маринони от 13 марта 1736 года)

Леонард Эйлер
(1707 – 1783)

История возникновения теории графов

Если все вершины графа чётные, то можно одним росчерком
(т.е. не отрывая карандаша от бумаги и не проводя дважды
по одной и той же линии) начертить граф.
2. Граф с двумя нечётными вершинами тоже можно начертить
одним росчерком. Движение нужно начинать от любой
нечётной вершины, а заканчивать на другой нечётной вершине.
3. Граф с более чем двумя нечётными вершинами, невозможно
начертить одним росчерком.

ребрам графа , проходящий по одному разу через все вершины, называется гамильтоновым циклом.

от них находились три колодца: один с соленой водой, второй- со сладкой , третий – с пресной , и ходили к ним по тропинкам. Однажды эти люди перессорились и решили по-новому провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. Как это сделать?

чудес»

нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами.

1

3

2

4

1. Число рёбер в графе ровно в 2 раза меньше, чем сумма
степеней вершин.
Доказательство. Любое ребро графа связывают 2 вершины. Значит,
если будем складывать число степеней всех вершин графа, то получим
удвоенное число рёбер, т.к. каждое ребро было подсчитано дважды.

Лемма 2. Сумма степеней вершин графа чётна.
Доказательство. По лемме1 число рёбер в графе в 2 раза меньше
суммы степеней вершин, значит сумма степеней вершин
чётна (делится на 2).

степень не чётная, то вершина нечётная.
Лемма 3. Число нечётных вершин графа чётно.
Доказательство. Если в графе есть n чётных и k нечётных вершин, то сумма степеней чётных вершин чётна. Сумма степеней нечётных вершин нечётна, если количество этих вершин нечётна. Но тогда общее число степеней вершин тоже нечётна, чего не может быть. Значит, k чётно.

 

двузначное число, которое делится на 13. Докажите,
что среди этих цифр нет цифры 8.

Решение. Существует 7 двузначных чисел, которые делятся на 13.
Обозначим эти числа точками и применим определение графа.
По условию каждые 2 подряд идущие цифры образуют двузначное число, которые делятся на 13, значит цифры, из которых состоит 10-значное число, повторяются. Соединим вершины графа рёбрами так, чтобы цифры, входящие в этот граф повторялись.

13

39

65

78

52

91

26

с каждым по одной партии. Сколько партий было сыграно?

6 партий

по десятибалльной системе. Сколькими способами он может сдать экзамены, чтобы быть принятым в университет, если проходной балл в тот год составил 28 баллов?

Решение.
Для решения этой задачи, как и во многих других комбинаторных и вероятностных задачах, эффективным оказывается организация элементов анализируемого множества в виде дерева. От одной выделенной вершины проводятся ребра, соответствующие оценке на первом экзамене, а затем к их концам добавляются новые ребра, соответствующие возможным результатам второго экзамена, а затем и третьего. Таким образом, для поступления на физмат можно сдать вступительные экзамены 10 различными способами.

рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?»
Решение:

Р

Р

Р

П

П

П

Да Да Нет Да Да Да

Да Да Да Нет Нет

древа, решать задачи, связанные с теорией игр, задачи предлагаемые на олимпиадах.

На языке теории графов формируются и решаются не только математические, но и технические задачи, задачи из области экономики, социологии, менеджмента и других областей.