Презентация на тему Определение графа

Содержание

2. Задача ЭйлераТеория графов зародилась в ходе решения
3. Уникурсальные графыНа рисунке представлен граф, соответствующий задаче
4. ТеоремаИндексом вершины графа называется число ребер, сходящихся
5. Решение задачи ЭйлераРешение задачи Эйлера. Найдем индексы
6. Вопрос 1Какая фигура называется графом? Ответ: Графом
7. Вопрос 2Какой граф называется уникурсальным? Ответ: Граф
8. Вопрос 3Что называется индексом вершины графа? Ответ:
9. Вопрос 4Что можно сказать об индексах вершин
10. Упражнение 1В графе 4 вершин, каждая из
11. Упражнение 2В графе 5 вершин, каждая из
12. Упражнение 3Выясните, какие графы, изображенные на рисунке, являются уникурсальными?Ответ: а), б), г), д), ж), з).
13. Упражнение 4Может ли граф иметь: а) одну
14. Упражнение 5Какое наименьшее число мостов в задаче
15. Упражнение 6Можно ли обойти все ребра тетраэдра, пройдя по каждому ребру ровно один раз?Ответ: Нет.
16. Упражнение 7Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра тетраэдра? Ответ: Одно.
17. Упражнение 8Какое наименьшее число ребер придется пройти
18. Упражнение 9Можно ли обойти все ребра куба, пройдя по каждому ребру ровно один раз?Ответ: Нет.
19. Упражнение 10Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра куба? Ответ: Три.
20. Упражнение 11Какое наименьшее число ребер придется пройти
21. Упражнение 12Можно ли обойти все ребра октаэдра, пройдя по каждому ребру ровно один раз?Ответ: Да.
22. Упражнение 13Можно ли обойти все ребра икосаэдра, пройдя по каждому ребру ровно один раз?Ответ: Нет.
23. Упражнение 14Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра икосаэдра? Ответ: Пять.
24. Упражнение 15Какое наименьшее число ребер придется пройти
25. Упражнение 16Можно ли обойти все ребра додекаэдра, пройдя по каждому ребру ровно один раз?Ответ: Нет.
26. Упражнение 17Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра додекаэдра? Ответ: Девять.
27. Упражнение 18Какое наименьшее число ребер придется пройти
28. Скачать презентацию
29. Похожие презентации

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

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

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

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

Решение задачи ЭйлераРешение задачи Эйлера. Найдем индексы вершин графа задачи Эйлера. Вершина

Вопрос 1Какая фигура называется графом? Ответ: Графом называется фигура, образованная конечным набором

Вопрос 2Какой граф называется уникурсальным? Ответ: Граф называется уникурсальным, если его можно

Вопрос 3Что называется индексом вершины графа? Ответ: Индексом вершины графа называется число

Вопрос 4Что можно сказать об индексах вершин уникурсального графа?Ответ: Для уникурсального графа

Упражнение 1В графе 4 вершин, каждая из которых имеет индекс 3. Сколько

Упражнение 2В графе 5 вершин, каждая из которых имеет индекс 4. Сколько

Упражнение 3Выясните, какие графы, изображенные на рисунке, являются уникурсальными?Ответ: а), б), г), д), ж), з).

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

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

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

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

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

Упражнение 9Можно ли обойти все ребра куба, пройдя по каждому ребру ровно один раз?Ответ: Нет.

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

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

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

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

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

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

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

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

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

Упражнение 19Каким правильным многогранникам соответствуют графы, изображенные на рисунке? Ответ: а) куб;

Слайды презентации

Слайд 2 Задача Эйлера
Теория графов зародилась в ходе решения головоломок

Задача ЭйлераТеория графов зародилась в ходе решения головоломок двести с лишним

двести с лишним лет назад. Одной из таких задач-головоломок

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

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

Слайд 3 Уникурсальные графы
На рисунке представлен граф, соответствующий задаче Эйлера,

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

в котором ребра соответствуют мостам, а вершины – берегам

и островам.

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

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

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

этой вершине (ребра, с началом и концом в данной

вершине считаются дважды).

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

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

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

Слайд 5 Решение задачи Эйлера
Решение задачи Эйлера. Найдем индексы вершин

Решение задачи ЭйлераРешение задачи Эйлера. Найдем индексы вершин графа задачи Эйлера.

графа задачи Эйлера. Вершина А имеет индекс 5, Б

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