Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Основы теории графов
Содержание
- 1. Основы теории графов
- 2. Слайд 2
- 3. Леонард ЭйлерМёбиус Карл АвгустГустав Роберт Кирхгоф Артур
- 4. Слайд 4
- 5. Слайд 5
- 6. Виды графов
- 7. Слайд 7
- 8. Бывший Кенигсберг (ныне Калининград) расположен на реке
- 9. Эйлер взял план города и заменил его
- 10. Слайд 10
- 11. Одним росчеркомЕсли все вершины графа четные, то
- 12. Одним росчеркомГраф, имеющий всего две нечетные вершины,
- 13. Задача о Кенигсбергских мостахНо, поскольку граф на
- 14. Слайд 14
- 15. Слайд 15
- 16. Слайд 16
- 17. Слайд 17
- 18. Слайд 18
- 19. Слайд 19
- 20. Слайд 20
- 21. Задача: В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1
- 22. Слайд 22
- 23. Слайд 23
- 24. Слайд 24
- 25. Слайд 25
- 26. Проблема четырех красокВыяснить, можно ли всякую расположенную
- 27. Хроматическое число плоского графа не превосходит 4Применение на практике
- 28. Задача коммивояжёраодна из самых известных задач комбинаторной
- 29. Определение расстояний между станциямиПрименение на практике
- 30. Сетевой графикПрименение на практике
- 31. Составление графика на дисциплине «Технология перевозочного процесса»Применение на практике
- 32. Скачать презентанцию
Леонард ЭйлерМёбиус Карл АвгустГустав Роберт Кирхгоф Артур Кэли Андрей Андреевич МарковУильям Роуэн ГамильтонОсвальд ВебленДжордж Юджин Уленбек…Всё, что без этого было темно, сомнительно и неведомо, математика сделала ясным, верным и очевидным…
Слайды и текст этой презентации
Слайд 3Леонард
Эйлер
Мёбиус Карл Август
Густав Роберт Кирхгоф
Артур Кэли
Андрей Андреевич
Марков
и неведомо, математика сделала ясным, верным и очевидным…
Слайд 8Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах
города река омывает два острова. С берегов на острова были
перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
Слайд 9Эйлер взял план города и заменил его упрощенной схемой, на
которой части города изображены точками (вершинами), а мосты - линиями (ребрами).
Слайд 11Одним росчерком
Если все вершины графа четные, то можно не отрывая
карандаш от бумаги («одним росчерком»), проводя по каждому ребру только
один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Слайд 12Одним росчерком
Граф, имеющий всего две нечетные вершины, можно начертить, не
отрывая карандаш от бумаги, при этом движение нужно начать с
одной из этих нечетных вершин и закончить во второй из них.
Слайд 13Задача о Кенигсбергских мостах
Но, поскольку граф на этом рисунке имеет
четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно.
Слайд 26Проблема четырех красок
Выяснить, можно ли всякую расположенную на сфере карту
раскрасить четырьмя красками так, чтобы любые две области, имеющие общий
участок границы, были раскрашены в разные цвета.
Слайд 28
Задача коммивояжёра
одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании
самого выгодного маршрута, проходящего через указанные города хотя бы по одному
разу с последующим возвратом в исходный город.
