Презентация на тему «Графы»

Графы

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

Задача Эйлера

Теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Одной из таких задач-головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).

Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (Л - левый берег, П - правый берег, А и Б - острова). Можно ли, прогуливаясь вдоль реки, пройти по каждому мосту ровно один раз?

Уникурсальные графы

На рисунке представлен граф, соответствующий задаче Эйлера, в котором ребра соответствуют мостам, а вершины – берегам и островам.

Требуется выяснить, можно ли пройти по каждому ребру этого графа ровно один раз, или, что то же самое, нарисовать этот граф «одним росчерком»,

т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз. Такие графы называются уникурсальными.

Вопрос 1

Какая фигура называется графом?

Ответ: Графом называется фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек.

Вопрос 2

Какой граф называется связным?

Ответ: Граф называется связным, если любые две его вершины можно соединить ломаной, состоящей из ребер графа.

Вопрос 3

Какой граф называется простым?

Ответ: Граф называется простым, если его ребра не пересекаются, т.е. не имеют общих внутренних точек.

Вопрос 4

Какой граф называется уникурсальным?

Ответ: Граф называется уникурсальным, если его можно ли нарисовать «одним росчерком», т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз.

Упражнение 1

Укажите путь, проходящий по каждому ребру графа ровно один раз.

Упражнение 2

Укажите путь, проходящий по каждому ребру графа ровно один раз.

Упражнение 3

Укажите путь, проходящий по каждому ребру графа ровно один раз.

Теорема Эйлера

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

Теорема Эйлера. Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

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

Решение задачи Эйлера

Решение задачи Эйлера. Найдем индексы вершин графа задачи Эйлера. Вершина А имеет индекс 5, Б - 3, П - 3 и Л - 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следовательно, данный граф не является уникурсальным. Значит, нельзя пройти по каждому из семи мостов только один раз.

Вопрос 5

Что называется индексом вершины графа?

Ответ: Индексом вершины графа называется число ребер, сходящихся в этой вершине (ребра, с началом и концом в данной вершине считаются дважды).

Вопрос 6

Что можно сказать об индексах вершин уникурсального графа?

Ответ: Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

Упражнение 4

В графе 4 вершин, каждая из которых имеет индекс 3. Сколько у него ребер? Нарисуйте такой граф.

Упражнение 5

В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у него ребер? Нарисуйте такой граф.

Упражнение 6

Может ли граф иметь пять вершин, в каждой из которых сходится три ребра?

Упражнение 7

Может ли граф иметь: а) одну вершину нечетного индекса; б) две вершины нечетного индекса; в) три вершины нечетного индекса; г) четыре вершины нечетного индекса?

Ответ: а), в) Нет; б), г) да.

Упражнение 8

Выясните, какие графы, изображенные на рисунке, являются уникурсальными?

Ответ: а), б), г), д), ж), з).

Упражнение 9

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

Ответ: Один.

Упражнение 10

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

Ответ: 18.

Задача Эйлера

Еще одной задачей, связанной с именем Л.Эйлера является задача о трех домиках и трех колодцах.

Задача. Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

Теорема Эйлера

Для связного простого графа имеет место равенство В - Р + Г = 2, где В - число вершин, Р - общее число ребер, Г - число областей (граней), на которые граф разбивает плоскость.

Например, для графа, изображенного на рисунке, В = 8, Р = 12, Г = 6.

Доказательство

Для установления справедливости равенства Эйлера, стянем какое-нибудь ребро связного простого графа, соединяющее две его вершины, в точку. При этом число ребер и число вершин уменьшаться на единицу, а число областей не изменится. Следовательно, В – Р + Г не измениться. Продолжая стягивать ребра, мы придем к графу, у которого имеется одна вершина, а ребрами являются петли. Уберем какое-нибудь ребро. При этом число ребер и число областей уменьшаться на единицу. Следовательно, В – Р + Г не изменится. Продолжая убирать ребра, мы придем к графу, у которого имеется одна вершина и одно ребро. У этого графа В = 1, Р = 1, Г = 2 и, следовательно, В – Р + Г = 2. Значит, для исходного графа также выполняется равенство В – Р + Г = 2.

Решение задачи Эйлера

Предположим, что можно провести непересекающиеся дорожки от каждого дома к каждому колодцу. Рассмотрим граф, вершинами которого являются домики и колодцы, а ребрами – дорожки. У него В = 6, Р = 9 и, следовательно, Г = 5. Каждая из пяти областей ограничена, по крайней мере, четырьмя ребрами, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро разделяет две области, то количество ребер должно быть не меньше (5?4)/2 = 10, что противоречит тому, что их число равно 9.

Упражнение 11

Посчитайте число вершин (В), ребер (Р) и областей (Г) для графов, изображенных на рисунке.

Ответ: а) В = 6, Р = 12, Г = 8; б) В = 20, Р = 30, Г = 12; в) В = 12, Р = 30, Г = 20.

Упражнение 12

Два соседа имеют: а) три общих колодца; б) четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

Упражнение 13

Три соседа имеют: а) два общих колодца; б) четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

Упражнение 14

Четыре соседа имеют четыре общих колодца. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединен с тремя колодцами?

Упражнение 15

Докажите, что пять домиков нельзя соединить непересекающимися дорожками так, чтобы каждый домик был соединен со всеми другими домиками.

Гамильтоновы графы

В 1859 г. ирландский математик У.Р. Гамильтон предложил головоломку, в которой требовалось найти путь по ребрам додекаэдра, проходящий через каждую вершину ровно один раз.

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

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

Упражнение 16

Укажите путь, проходящий через каждую вершину графа (тетраэдра) ровно один раз.

Упражнение 17

Укажите путь, проходящий через каждую вершину графа (куба) ровно один раз.

Упражнение 18

Укажите путь, проходящий через каждую вершину графа (октаэдра) ровно один раз.

Упражнение 19

Укажите путь, проходящий через каждую вершину графа (икосаэдра) ровно один раз.

Упражнение 20

Укажите путь, проходящий через каждую вершину графа (додекаэдра) ровно один раз.

Упражнение 21*

Докажите, что граф, изображенный на рисунке, не является гамильтоновым.

Упражнение 22*

Требуется проложить шоссейные дороги, соединяющие населённые пункты A, B, C, расположенные в вершинах треугольника. Выберите из предложенных вариантов расположения дорог тот, в котором суммарная длина дорог наименьшая. Проверьте правильность своего выбора измерением линейкой.

Ответ. в).

Упражнение 23*

Требуется проложить шоссейные дороги, соединяющие населённые пункты A, B, C, D, расположенные в вершинах прямоугольника. Выберите из предложенных вариантов расположения дорог тот, в котором суммарная длина дорог наименьшая. Проверьте правильность своего выбора измерением линейкой.

Ответ. в).