Гамильтоновы цепи в некоторых типах линейно-выпуклых графов

Сентябрь 14, 2022

Главная
Математика
Гамильтоновы цепи в некоторых типах линейно-выпуклых графов

Содержание

2. Актуальность темы Актуальность теории графов в различных отраслях наук 1. В информатике – граф-схема алгоритма, кодирование
3. Гамильтоновы цепи и циклы Гамильтонов цикл - Гамильтонова цепь - незамкнутая задача коммивояжера замкнутая задача коммивояжера
4. Линейно-выпуклые эллипсы
5. Линейно-выпуклые эллипсы Граничное сечение эллипса
6. Линейно-выпуклые эллипсы
7. Линейно-выпуклые эллипсы
8. Склейки прямоугольных графов Инцидентные вершины в склейке прямоугольных графов
9. Склейки прямоугольных графов
10. Склейки прямоугольных графов Теорема 3. Если в любом прямоугольном графе четное число вершин, то в нем
11. Склейки прямоугольных графов
13. Скачать презентацию

Слайд 2

Актуальность темы
Актуальность теории графов в различных отраслях наук
1. В информатике

– граф-схема алгоритма, кодирование и декодирование информации
2. В физике – при построении электрических схем
3. В геометрии – чертежи многоугольников многогранников, пространственных фигур
4. В экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог)
5. В географии – при составлении карт

Слайд 3

Гамильтоновы цепи и циклы
Гамильтонов цикл - Гамильтонова цепь -
незамкнутая задача коммивояжера

замкнутая задача коммивояжера

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

Слайд 4

Линейно-выпуклые эллипсы

Слайд 5

Линейно-выпуклые эллипсы

Граничное сечение эллипса

Слайд 6

Линейно-выпуклые эллипсы

Слайд 7

Линейно-выпуклые эллипсы

Слайд 8

Склейки прямоугольных графов

Инцидентные вершины в склейке прямоугольных графов

Слайд 9

Склейки прямоугольных графов

Слайд 10

Склейки прямоугольных графов
Теорема 3. Если в любом прямоугольном графе четное

число вершин, то в нем существует гамильтонов цикл.

граф n×2k граф 2k×m

Слайд 11

Склейки прямоугольных графов