Similar presentations:
Основы теории графов
1. Основы теории графов
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
Применение на практикеХроматическое число
плоского графа не превосходит 4
28. Задача коммивояжёра
одна из самых известныхзадач комбинаторной
оптимизации,
заключающаяся в
отыскании самого
выгодного маршрута,
проходящего через
указанные города хотя
бы по одному разу с
последующим возвратом
в исходный город.
29. Определение расстояний между станциями
Применение на практикеОпределение расстояний между
станциями
30. Сетевой график
Применение на практикеСетевой график
31. Составление графика на дисциплине «Технология перевозочного процесса»
Применение на практикеСоставление графика на дисциплине «Технология
перевозочного процесса»