Графы Наглядная геометрия 5 класс

Графы

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

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

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

Вместо отрезков в качестве ребер графов рассматриваются также кривые линии.

В режиме слайдов ответы появляются после кликанья мышкой

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

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

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

В режиме слайдов ответы появляются после кликанья мышкой

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

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

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

В режиме слайдов ответы появляются после кликанья мышкой

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

Вопрос 1

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Вопрос 2

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Вопрос 3

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Вопрос 4

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Упражнение 1

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей с началом и концом в вершине A показан на рисунке. Числа обозначают порядок прохождения ребер графа

8

Упражнение 2

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей с началом в вершине A и концом в вершине B показан на рисунке. Числа обозначают порядок прохождения ребер графа

9

Упражнение 3

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей с началом в вершине A и концом в вершине B показан на рисунке. Числа обозначают порядок прохождения ребер графа

10

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

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

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

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

В режиме слайдов ответы появляются после кликанья мышкой

10

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Вопрос 5

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Вопрос 6

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Упражнение 4

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: 6.

Упражнение 5

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: 10.

Упражнение 6

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

Ответ: Нет. В этом случае число ребер равнялось бы что невозможно.

В режиме слайдов ответы появляются после кликанья мышкой

Упражнение 7

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Упражнение 8

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

В режиме слайдов ответы появляются после кликанья мышкой

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

Упражнение 9

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один.

Упражнение 10

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: 18.

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

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

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

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

В режиме слайдов ответы появляются после кликанья мышкой

22

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

Для связного простого графа имеет место равенство В - Р + Г = 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

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: а), б) Да.

27

Упражнение 13

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: а) Да; б) нет.

28

Упражнение 14

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Да.

29

Упражнение 15

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

Предположим, что это сделать можно. Тогда мы имеем связный простой граф, у которого В = 5, Р = 10 и, следовательно, Г = 7. С другой стороны, поскольку каждая область ограничена, по крайней мере тремя ребрами, то число ребер должно быть больше или равно Противоречие.

В режиме слайдов ответы появляются после кликанья мышкой

30

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

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

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

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

В режиме слайдов ответы появляются после кликанья мышкой

30

Упражнение 16

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей показан на рисунке. Числа обозначают порядок прохождения ребер графа

32

Упражнение 17

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей показан на рисунке. Числа обозначают порядок прохождения ребер графа

33

Упражнение 18

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей показан на рисунке. Числа обозначают порядок прохождения ребер графа

34

Упражнение 19

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей показан на рисунке. Числа обозначают порядок прохождения ребер графа

35

Упражнение 20

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: Один из возможных путей показан на рисунке. Числа обозначают порядок прохождения ребер графа

36

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

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Однако в этом графе 6 вершин индекса 4 и 8 вершин индекса 3. Следовательно, искомого пути не существует.

37

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ. в).

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

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

В режиме слайдов ответы появляются после кликанья мышкой

Ответ. в).