Задачи, приводящие к теории графов. Основные понятия и определения.

Сентябрь 2, 2022

Главная
Алгебра
Задачи, приводящие к теории графов. Основные понятия и определения.

Содержание

2. Историческая записка Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в 1727 году. Не было
3. Леонард Эйлер 1707-1783
4. Задачи, приводящие к теории графов Попробуйте нарисовать закрытый конверт одним росчерком, т.е., не отрывая карандаша от
5. Задача о Кёнигсбергских мостах Впервые над задачей описанного выше типа задумался Леонард Эйлер после посещения города
6. Задача о трех домах и трех колодцах Всегда ли можно изобразить граф на плоскости так, чтобы
17. Метрические характеристики графа
25. Степени вершин графа
29. По степенной последовательности можно построить графы
30. Задача Существуют ли графы с данной степенной последовательностью? Ответ пояснить. 1) (1;2;3;4); 2) (13;22;3;5); 3) (0;1;2;3;42);
31. Подграфы. Операции над графами
33. 4
38. Цепи. Циклы
42. Деревья
43. Граф без циклов (ациклический) называется лесом.
48. Скачать презентацию

Слайд 2

Историческая записка
Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в

1727 году. Не было такой области математики XVIII века, в которой Эйлер не достиг бы заметных результатов. Например, решая головоломки и развлекательные задачи, Эйлер заложил основы теории графов, ныне широко используемой во многих приложениях математики.
Напряженная работа повлияла на зрение ученого, в 1766 году он ослеп, но и после этого продолжал работу, диктуя ученикам свои статьи.
Эйлер умер в 76 лет и был похоронен на Смоленском кладбище Санкт-Петербурга. В 1957 году его прах был перенесен в Александро-Невскую лавру.

Слайд 3

Леонард Эйлер
1707-1783

Слайд 4

Задачи, приводящие к теории графов
Попробуйте нарисовать закрытый конверт одним росчерком, т.е.,

не отрывая карандаша от бумаги и не проводя дважды один и тот же отрезок.
А если конверт распечатать?

Слайд 5

Задача о Кёнигсбергских мостах
Впервые над задачей описанного выше типа задумался Леонард

Эйлер после посещения города Кенигсберга (ныне Калининград).
В городе было семь мостов через реку Прегель.
Гостям города предлагали задачу: пройти по всем мостам ровно один раз. Никому из гостей не удавалось справиться с задачей.
Эйлер отметил на карте города по одной точке на каждом берегу реки и на каждом острове.
Затем он соединил эти точки в соответствии с расположением мостов. Задача обхода мостов свелась к задаче изображения одним росчерком следующей картинки

Слайд 6

Задача о трех домах и трех колодцах
Всегда ли можно изобразить граф

на плоскости так, чтобы его ребра не пересекались? Впервые этот вопрос возник при решении старой головоломки. Вот как ее описывает Льюис Кэрролл.
В трех домиках жили три человека, неподалеку находилось три колодца: один с водой, другой с маслом, а третий с повидлом. Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант по этой причине их не устраивал.

Слайд 7

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Слайд 17

Метрические характеристики графа

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Слайд 22

Слайд 23

Слайд 24

Слайд 25

Степени вершин графа

Слайд 26

Слайд 27

Слайд 28

Слайд 29

По степенной последовательности можно построить графы

Слайд 30

Задача
Существуют ли графы с данной степенной последовательностью? Ответ пояснить.
1) (1;2;3;4);
2)

(13;22;3;5);
3) (0;1;2;3;42);
4) (12;23;32;4);
5) (12;32;4).
Решение.
1) Не существует, так как все степени различные (смотри теорему 3).
2) Не существует, так как число вершин нечетной степени нечетно, а именно 5 ( смотри теорему 2).
3) Не существует(смотри задачу 1).
4) Построим граф, имеющий данную степенную последовательность
5) Не существует, так как, соединив вершину степени 4 с четырьмя из оставшихся вершин, убеждаемся, что для вершин степени 3 не достаточно смежных вершин.

Слайд 31