Основы теории графов

Август 6, 2022

Главная
Математика
Основы теории графов

Содержание

3. Леонард Эйлер Мёбиус Карл Август Густав Роберт Кирхгоф Артур Кэли Андрей Андреевич Марков Уильям Роуэн Гамильтон
6. Виды графов
8. Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С
9. Эйлер взял план города и заменил его упрощенной схемой, на которой части города изображены точками (вершинами),
11. Одним росчерком Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»),
12. Одним росчерком Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при
13. Задача о Кенигсбергских мостах Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то такой
21. Задача: В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1
26. Проблема четырех красок Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы
27. Хроматическое число плоского графа не превосходит 4 Применение на практике
28. Задача коммивояжёра одна из самых известных задач комбинаторной оптимизацииодна из самых известных задач комбинаторной оптимизации, заключающаяся
29. Определение расстояний между станциями Применение на практике
30. Сетевой график Применение на практике
32. Скачать презентацию

Слайд 2

Слайд 3

Леонард
Эйлер
Мёбиус Карл Август
Густав Роберт Кирхгоф
Артур Кэли
Андрей Андреевич Марков
Уильям

Роуэн Гамильтон

Освальд Веблен

Джордж Юджин Уленбек

…Всё, что без этого было темно, сомнительно и неведомо, математика сделала ясным, верным и очевидным…

Слайд 4

Слайд 5

Слайд 6

Виды графов

Слайд 7

Слайд 8

Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города

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

Слайд 9

Эйлер взял план города и заменил его упрощенной схемой, на которой

части города изображены точками (вершинами), а мосты - линиями (ребрами).

Слайд 10

Слайд 11

Одним росчерком
Если все вершины графа четные, то можно не отрывая карандаш

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

Слайд 12

Одним росчерком
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая

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

Слайд 13

Задача о Кенигсбергских мостах
Но, поскольку граф на этом рисунке имеет четыре

нечетные вершины, то такой граф начертить «одним росчерком» невозможно.

Слайд 14

Слайд 15

Слайд 16

Слайд 17

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Задача: В графе (Рис. 1) найти длину кратчайшего пути из Х4

в Х1

Слайд 22

Слайд 23

Слайд 24

Слайд 25

Слайд 26

Проблема четырех красок
Выяснить, можно ли всякую расположенную на сфере карту раскрасить

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

Слайд 27

Хроматическое число плоского графа не превосходит 4
Применение на практике

Слайд 28

Задача коммивояжёра
одна из самых известных задач комбинаторной оптимизацииодна из самых известных задач комбинаторной

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

Слайд 29