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

МИНОБРНАУКИ РОССИИ «Челябинский государственный университет»   Математический факультет Кафедра теорииАктуальность темы
 Актуальность теории графов в различных отраслях наук 
 1.Гамильтоновы цепи и циклы
  Гамильтонов цикл -   Линейно-выпуклые эллипсы
 Теорема 1. Если 2a > 2x + y ,гдеЛинейно-выпуклые эллипсы
   Доказательство теоремы 1
 1. Локальное рассогласование четностиЛинейно-выпуклые эллипсыЛинейно-выпуклые эллипсы
 2. Локальное рассогласование четностиСклейки прямоугольных графов 
 Расстояние пар точек по линейной норме равноТеорема 2. Если в прямоугольных графах и существуют гамильтоновы циклы, тоСклейки прямоугольных графов  
 Теорема 3. Если в любом прямоугольномСклейки прямоугольных графов  
 Теорема 4. Если в существует гамильтоновСпасибо за внимание



Слайды и текст этой презентации
Слайд 1
Описание слайда:
МИНОБРНАУКИ РОССИИ «Челябинский государственный университет» Математический факультет Кафедра теории управления и оптимизации Выпускная квалификационная работа Гамильтоновы цепи в некоторых типах линейно-выпуклых графов


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

Слайд 3
Описание слайда:
Гамильтоновы цепи и циклы Гамильтонов цикл - Гамильтонова цепь  - незамкнутая задача коммивояжера замкнутая задача коммивояжера

Слайд 4
Описание слайда:
Линейно-выпуклые эллипсы Теорема 1. Если 2a > 2x + y ,где -четное, -нечетное, то в линейно-выпуклом эллипсе не существует гамильтоновой цепи

Слайд 5
Описание слайда:
Линейно-выпуклые эллипсы Доказательство теоремы 1 1. Локальное рассогласование четности Шаг 1. Шаг 2.

Слайд 6
Описание слайда:
Линейно-выпуклые эллипсы

Слайд 7
Описание слайда:
Линейно-выпуклые эллипсы 2. Локальное рассогласование четности

Слайд 8
Описание слайда:
Склейки прямоугольных графов Расстояние пар точек по линейной норме равно единице, т.е. или

Слайд 9
Описание слайда:
Теорема 2. Если в прямоугольных графах и существуют гамильтоновы циклы, то в склейке существует гамильтонов цикл. Теорема 2. Если в прямоугольных графах и существуют гамильтоновы циклы, то в склейке существует гамильтонов цикл. цикл в поворот ребер

Слайд 10
Описание слайда:
Склейки прямоугольных графов Теорема 3. Если в любом прямоугольном графе четное число вершин, то в нем существует гамильтонов цикл.

Слайд 11
Описание слайда:
Склейки прямоугольных графов Теорема 4. Если в существует гамильтонов цикл, а в существует гамильтонова цепь, то в склейке существует гамильтонова цепь.

Слайд 12
Описание слайда:
Спасибо за внимание


Скачать презентацию на тему Гамильтоновы цепи в некоторых типах линейно-выпуклых графов можно ниже:

Похожие презентации