Графы

1.

1
Графы

2.

2
Графом называется геометрическая фигура, состоящая из точек и
соединяющих их линий. Точки называются вершинами графа, а
линии — ребрами.

3.

Два ребра называются смежными, если они имеют общую вершину.
ребра называются кратными, если они соединяют одну и ту же пару
3 Два
вершин.
Ребро называется петлей, если его концы совпадают.
Степенью вершины называют количество ребер, для которых она является
концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для
одного ребра.
Вершина называется висячей, если из неё выходит ровно одно ребро.
Граф без кратных ребер и петель называется обыкновенным.

4.

4
В деревне 15 телефонов. Можно ли их соединить проводами так,
чтобы каждый телефон был соединен ровно с пятью другими?
Предположим, что это возможно. Рассмотрим тогда граф, вершины
которого соответствуют телефонам, а ребра — соединяющим их
проводам. В этом графе 15 вершин, степень каждой из которых равна
пяти. Подсчитаем количество ребер в этом графе. Для этого сначала
просуммируем степени всех его вершин. Ясно, что при таком подсчете
каждое ребро учтено дважды (оно ведь соединяет две вершины).
Поэтому число ребер графа должно быть равно (15∙5)/2. Но это число
нецелое. Следовательно, такого графа не существует, а значит, и
соединить телефоны требуемым образом невозможно.

5.

5
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу
ребер.
Доказательство
Если ребро соединяет две различные вершины графа, то при подсчете
суммы степеней вершин мы учтем это ребро дважды; если же ребро
является петлей, то при подсчете суммы степеней вершин мы также
учтем его дважды (по определению степени вершины)
Следствие. В любом графе число вершин нечетной степени четно.

6.

6
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3
друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей
(считается, что все дружбы взаимные)?
Если бы это было возможно, то можно было бы нарисовать граф с
30 вершинами, 9 из которых имели бы степень 3, 11 — степень 4, 10
— степень 5. Однако у такого графа 19 нечетных вершин, что
противоречит следствию из леммы о рукопожатиях.

7.

7
Может ли в государстве, в котором из каждого города выходит 3
дороги, быть ровно 100 дорог?
Если в государстве n городов, то дорог — 3n / 2. Это число не может
быть равно 100.
Ответ. Не может.

8.

8

9.

9
Путем (или цепью) в графе называют конечную последовательность
вершин, в которой каждая вершина (кроме последней) соединена со
следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины
совпадают.
Путь (или цикл) называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф
называется связным.

10.

10
Докажите, что граф с n вершинами, степень каждой из
которых не менее (n-1)/ 2, связен.
Рассмотрим две произвольные вершины и предположим, что они
не соединены путем. Каждая из этих двух вершин по условию
соединена не менее чем с (n-1)/2 другими; при этом все эти
вершины различны (если какие-то две из них совпадают, то есть
путь, соединяющий исходные вершины). Таким образом, в графе
не менее (n-1)/2 + (n-1)/2 +2 = n+1 вершин. Противоречие.

11.

11
Рассмотрим подмножество вершин графа такое, что каждые две
вершины этого подмножества соединены путем, а никакая другая
вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество (вместе со всеми ребрами исходного
графа, соединяющими вершины этого подмножества) называется
компонентой связности.

12.

12
В некоторой стране из Столицы выходит 21 дорога, а из города
Крайний — одна, а из всех остальных городов — по 20.
Докажите, что из Столицы можно доехать до Крайнего
(возможно, с пересадками).
Рассмотрим компоненту связности графа дорог, содержащую
Столицу. Нам нужно доказать, что она содержит также и город
Крайний. Предположим противное. Тогда в этой компоненте
связности из одной вершины (Столицы) выходит 21 ребро, а из
всех остальных вершин — по 20 ребер. Таким образом, в этом
графе (компоненте связности) ровно одна нечетная вершина.
Противоречие.

13.

13
В стране из каждого города выходит 100 дорог и от любого
города можно добраться до любого другого. Одну дорогу
закрыли на ремонт. Докажите, что и теперь от любого города
можно добраться до любого другого.
Если закрыта дорога АВ , то нам достаточно доказать, что и после
этого можно добраться из А в В . Рассмотрим компоненту
связности, содержащую вершину А . Если в этой компоненте нет
вершины В , то в этой компоненте все вершины, кроме А, имеют
четную степень. Но наличие ровно одной вершины с нечетной
степенью противоречит следствию из леммы о рукопожатиях.

14.

14
ЛЕОНАРД ЭЙЛЕР
(1707-1783)
Российский ученый — математик, механик,
физик и астроном.

15.

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

16. Кенигсберг (Калининград)

16
КЕНИГСБЕРГ
(КАЛИНИНГРАД)

17.

17
Задача о кенигсбергских мостах. Город Кенигсберг (ныне
Калининград) расположен на берегах реки Прегель и двух островах на
этой реке. Части города соединены мостами. Спрашивается, можно ли,
выйдя из какой-нибудь точки города, пройти по каждому мосту ровно
один раз и вернуться в исходную точку.

18. Кенигсбергские мосты

18
КЕНИГСБЕРГСКИЕ МОСТЫ
С
А
В

19.

19 5.
2014 год
В 8«А» классе 23 человека. Некоторые ученики дружат между собой. По
исследованию школьного психолога оказалось, что староста класса Надя дружит
со всеми своими одноклассниками, ее лучшие подруги Ангелина, Лера и Катя
имеют по 10 друзей среди одноклассников, а у каждого из остальных учеников
класса имеется 1, 3, 5 или 7 друзей среди одноклассников. Директор-математик,
ознакомившись с этими результатами, сказал, что психолог ошибся. Прав ли
директор? (Считаем, что если А дружит с Б, то Б дружит с А).
Задачу легко решить, используя простейшие знания по теории графов. Пусть
ученики – это вершины графа, отрезки, соответствующие дружбе двух учеников – ребра
графа. Из условия следует, что степень одной вершины равна 22, три вершины имеют
степень 10, и 19 вершин имеют степени 1, 3, 5 или 7 (т.е. нечетные числа). Однако
известно, что в любом графе должно быть четное количество нечетных вершин.
Получили противоречие.
Ответ: директор прав.

20.

20
На небольшом предприятии каждый рабочий имеет по 2
специальности. Всего специальностей 4, причем на каждой
специальности занято по 3 рабочих. Сколько рабочих на
предприятии? Изобразите решение в виде графа.
В графе для этой задачи вершины, соответствующие рабочим,
обозначим звездочкой, а вершины соответствующие специальностям
– кружочком. Каждое ребро графа соединяет ровно две вершины:
одну звездочку и один кружочек, причем количество кружочков - 4.
Обозначим за х количество рабочих, тогда 2х = = 6.

21.

21
Задача 1. Один из ребят сказал: «А у нас в классе 25 человек, и каждый дружит ровно с
семью одноклассниками!»
«Не может быть этого», - ответил приятелю Витя Иванов, победитель олимпиады.
Почему он так ответил?
Задача 2. В стране 15 городов, каждый соединен дорогами не менее чем с 7-ю другими.
Докажите, что из любого города можно проехать в любой другой либо напрямую, либо
через один промежуточный город.
Задача 3. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик
– с 3 девочками. Сколько в классе мальчиков и девочек?
Задача 4. За некотором пространстве под землёй живут 20 кротов, каждой
в своей пещере-жилище. Чтобы общаться друг с другом, не вылезая на
поверхность, кроты прорыли между своими жилищами 90 тоннелей.
Каждый тоннель соединяет только 2 жилища, тоннели не пересекаются, и
никакие 2 тоннеля не соединяют одну и туже пару жилищ. Докажите, что
есть крот, который может по вырытым тоннелям переползать в жилища
не менее чем 10 других кротов (посещая, возможно, по пути другие жилища).
Задача 5. Расположите на плоскости 6 точек и соедините их непересекающимися линиями
так, чтобы из каждой точки выходили четыре линии.
Задача 6. В марсианском метро 100 станций. От любой станции до любой другой можно
проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так,
чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая
станция найдётся.

22.

Контрольное задание
22
1. В трёх вершинах правильного пятиугольника расположили по фишке. Разрешается
передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться
того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами?
2. На математической олимпиаде было предложено 20 задач. На закрытие пришло 20
школьников. Каждый из них решил по две задачи, причём выяснилось, что среди при-шедших
каждую задачу решило ровно два школьника. Докажите, что можно так организовать разбор
задач, чтобы каждый школьник рассказал одну из решенных им задач, и все задачи были
разобраны
3. В спортклубе тренируются 100 толстяков, веса которых равны 1 кг, 2 кг, ..., 100 кг. На какое
наименьшее число команд их можно разделить, чтобы ни в какой команде не было двух
толстяков, один из которых вдвое тяжелее другого?
4. В тридевятом царстве каждые два города соединены дорогой с односторонним
движением. Докажите, что существует город, из которого можно проехать в любой другой не
более чем по двум дорогам.
5. В городе на каждом перекрестке сходится чётное число улиц. Известно, что с любой улицы
города можно проехать на любую другую. Докажите, что все улицы города можно объехать,
побывав на каждой по одному разу.
6. Дан правильный 45-угольник. Можно ли так расставить в его вершинах цифры от 0 до 9 так,
чтобы для любой пары различных цифр нашлась сторона, концы которой занумерованы
этими цифрами.