Комбинаторика
<<  Эйлеровы графы Задачи на графы  >>
Определение графа
Определение графа
Задача Эйлера 1
Задача Эйлера 1
Индекс вершины графа
Индекс вершины графа
Упражнение 1
Упражнение 1
Упражнение 2
Упражнение 2
Упражнение 3
Упражнение 3
Вершины нечетного индекса
Вершины нечетного индекса
Упражнение 4
Упражнение 4
Упражнение 5
Упражнение 5
Упражнение 6
Упражнение 6
Уникурсальные графы
Уникурсальные графы
Теорема Эйлера
Теорема Эйлера
Решение задачи Эйлера
Решение задачи Эйлера
Упражнение 7
Упражнение 7
Упражнение 8
Упражнение 8
Упражнение 9
Упражнение 9
Упражнение 10
Упражнение 10
Упражнение 11
Упражнение 11
Упражнение 12
Упражнение 12
Упражнение 13
Упражнение 13
Упражнение 14
Упражнение 14
Упражнение 15
Упражнение 15
Упражнение 16
Упражнение 16
Упражнение 17
Упражнение 17
Упражнение 18
Упражнение 18
Упражнение 19
Упражнение 19
Упражнение 20
Упражнение 20
Упражнение 21
Упражнение 21
Упражнение 22
Упражнение 22
Упражнение 23
Упражнение 23
Задача Эйлера 2
Задача Эйлера 2
Теорема Эйлера
Теорема Эйлера
Доказательство теоремы Эйлера
Доказательство теоремы Эйлера
Решение задачи Эйлера
Решение задачи Эйлера
Упражнение 24
Упражнение 24
Упражнение 25
Упражнение 25
Упражнение 26
Упражнение 26
Упражнение 27
Упражнение 27
Упражнение 28
Упражнение 28

Презентация: «Определение графа». Автор: *. Файл: «Определение графа.ppt». Размер zip-архива: 620 КБ.

Определение графа

содержание презентации «Определение графа.ppt»
СлайдТекст
1 Определение графа

Определение графа

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

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

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

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

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

3 Индекс вершины графа

Индекс вершины графа

Для решения задачи Эйлера введем понятие индекса вершины графа.

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

Например, на рисунке индекс вершины А равен 5, индекс вершин Л, Б, П равен 3.

4 Упражнение 1

Упражнение 1

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

5 Упражнение 2

Упражнение 2

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

6 Упражнение 3

Упражнение 3

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

7 Вершины нечетного индекса

Вершины нечетного индекса

Теорема. Сумма индексов всех вершин графа равна удвоенному числу ребер этого графа.

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

Выведем из этого, что число вершин с нечетным индексом четно. Действительно, если бы оно было нечетно, то сумма индексов вершин графа с нечетными индексами была бы нечетна. С другой стороны, сумма индексов вершин графа с четными индексами четна. Но тогда сумма всех индексов вершин графа была бы нечетна, что противоречит теореме.

8 Упражнение 4

Упражнение 4

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

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

9 Упражнение 5

Упражнение 5

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

Ответ: Нет. Число вершин с нечетным индексом должно быть четным.

10 Упражнение 6

Упражнение 6

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

Ответ: Нет.

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

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

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

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

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

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

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

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

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

Верно и обратное: Если у связного графа число вершин нечетного индекса равно нулю или двум, то он является уникурсальным.

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

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

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

14 Упражнение 7

Упражнение 7

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

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

15 Упражнение 8

Упражнение 8

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

Ответ: 18.

16 Упражнение 9

Упражнение 9

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

Ответ: Один.

17 Упражнение 10

Упражнение 10

Можно ли обойти все ребра тетраэдра, пройдя по каждому ребру ровно один раз?

Ответ: Нет.

18 Упражнение 11

Упражнение 11

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

Ответ: Одно.

19 Упражнение 12

Упражнение 12

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

Ответ: Два.

20 Упражнение 13

Упражнение 13

Можно ли обойти все ребра куба, пройдя по каждому ребру ровно один раз?

Ответ: Нет.

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

Упражнение 14

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

Ответ: Три.

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

Упражнение 15

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

Ответ: Четыре.

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

Упражнение 16

Можно ли обойти все ребра октаэдра, пройдя по каждому ребру ровно один раз?

Ответ: Да.

24 Упражнение 17

Упражнение 17

Можно ли обойти все ребра икосаэдра, пройдя по каждому ребру ровно один раз?

Ответ: Нет.

25 Упражнение 18

Упражнение 18

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

Ответ: Пять.

26 Упражнение 19

Упражнение 19

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

Ответ: Шесть.

27 Упражнение 20

Упражнение 20

Можно ли обойти все ребра додекаэдра, пройдя по каждому ребру ровно один раз?

Ответ: Нет.

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

Упражнение 21

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

Ответ: Девять.

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

Упражнение 22

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

Ответ: Десять.

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

Упражнение 23

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

Доказательство. Пусть A – вершина графа с наибольшим индексом, равным n. Если среди вершин A1, …, An имеется имеется вершина индекса n, то мы получим две вершины индекса n. Если индексы всех вершин A1, …, An меньше n, то среди этих вершин найдутся две вершины одинакового индекса, так как количество вершин равно n, а индексы этих вершин могут принимать значения только 1, 2, …, n – 1.

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

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

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

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

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

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

Простой граф разбивает плоскость на несколько кусков – областей.

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

Теорема. Для любого связного простого графа имеет место равенство В - Р + О = 2, где В - число вершин, Р - общее число ребер, О - число областей.

33 Доказательство теоремы Эйлера

Доказательство теоремы Эйлера

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

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

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

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

35 Упражнение 24

Упражнение 24

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

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

36 Упражнение 25

Упражнение 25

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

37 Упражнение 26

Упражнение 26

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

38 Упражнение 27

Упражнение 27

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

39 Упражнение 28

Упражнение 28

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

«Определение графа»
http://900igr.net/prezentacija/algebra/opredelenie-grafa-82293.html
cсылка на страницу

Комбинаторика

25 презентаций о комбинаторике
Урок

Алгебра

35 тем
Слайды