🗊Презентация Теория графов. Задача коммивояжера

Категория: Математика
Нажмите для полного просмотра!
Теория графов. Задача коммивояжера, слайд №1Теория графов. Задача коммивояжера, слайд №2Теория графов. Задача коммивояжера, слайд №3Теория графов. Задача коммивояжера, слайд №4Теория графов. Задача коммивояжера, слайд №5Теория графов. Задача коммивояжера, слайд №6Теория графов. Задача коммивояжера, слайд №7Теория графов. Задача коммивояжера, слайд №8Теория графов. Задача коммивояжера, слайд №9Теория графов. Задача коммивояжера, слайд №10Теория графов. Задача коммивояжера, слайд №11Теория графов. Задача коммивояжера, слайд №12Теория графов. Задача коммивояжера, слайд №13Теория графов. Задача коммивояжера, слайд №14Теория графов. Задача коммивояжера, слайд №15Теория графов. Задача коммивояжера, слайд №16Теория графов. Задача коммивояжера, слайд №17Теория графов. Задача коммивояжера, слайд №18Теория графов. Задача коммивояжера, слайд №19Теория графов. Задача коммивояжера, слайд №20
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория графов. Задача коммивояжера. Доклад-сообщение содержит 20 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче­ская задача коммивояжера. Формулировка задачи. Коммивояжер должен совершить поездку по городам и вер­нуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче­ская задача коммивояжера. Формулировка задачи. Коммивояжер должен совершить поездку по городам и вер­нуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.

Слайд 2


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некоторое числовое значение, называемое весом ребра. Элементами матрицы смежности взвешенного графа являются весовые значения ребер (дуг) графа.
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некоторое числовое значение, называемое весом ребра. Элементами матрицы смежности взвешенного графа являются весовые значения ребер (дуг) графа.

Слайд 3


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра – связывающие их дороги. Кроме того, каждое ребро оснащено ве­сом, обозначающим транспортные затраты, необходимые для передвижения по соответствующей дороге, такие, как, например, рассто­яние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра – связывающие их дороги. Кроме того, каждое ребро оснащено ве­сом, обозначающим транспортные затраты, необходимые для передвижения по соответствующей дороге, такие, как, например, рассто­яние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.

Слайд 4


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Методы решения задачи коммивояжера: метод ветвей и границ (алгоритм Литтла); алгоритм «ближайшего соседа» («жадный алгоритм»); метод нахождения минимального остовного дерева («деревянный алгоритм»); алгоритм Дейкстры.
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Методы решения задачи коммивояжера: метод ветвей и границ (алгоритм Литтла); алгоритм «ближайшего соседа» («жадный алгоритм»); метод нахождения минимального остовного дерева («деревянный алгоритм»); алгоритм Дейкстры.

Слайд 5


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Алгоритм «ближайшего соседа» относится к алгоритмам поиска субопти­мального решения. Субоптимальное решение необязательно даст цикл минимального oбщегo веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамиль­тоновых циклов.
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Алгоритм «ближайшего соседа» относится к алгоритмам поиска субопти­мального решения. Субоптимальное решение необязательно даст цикл минимального oбщегo веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамиль­тоновых циклов.

Слайд 6


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Формулировка алгоритма. Пункты (вершины) обхода графа последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Формулировка алгоритма. Пункты (вершины) обхода графа последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута

Слайд 7


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Пример. Применим алгоритм ближайшего соседа к графу, изо­браженному на рис. 15. За исходную вершину возьмем вершину D. Рисунок 15
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Пример. Применим алгоритм ближайшего соседа к графу, изо­браженному на рис. 15. За исходную вершину возьмем вершину D. Рисунок 15

Слайд 8


ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Решение.
Описание слайда:
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Решение.

Слайд 9


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Существует класс графов, называемых деревьями. Дерево – связный граф, не содержащий циклов (ацикличный граф). Пусть G = (V, Е) – граф с n вершинами и m ребрами. Мож­но сформулировать несколько необходимых и достаточных условий, при которых G является деревом: • любая пара вершин в G соединена единственным путем; • G связен и m = n-1; • G связен, а удаление хотя бы одного его ребра нарушает связность графа; • G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Существует класс графов, называемых деревьями. Дерево – связный граф, не содержащий циклов (ацикличный граф). Пусть G = (V, Е) – граф с n вершинами и m ребрами. Мож­но сформулировать несколько необходимых и достаточных условий, при которых G является деревом: • любая пара вершин в G соединена единственным путем; • G связен и m = n-1; • G связен, а удаление хотя бы одного его ребра нарушает связность графа; • G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

Слайд 10


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ В любом связном графе найдется под­граф, являющийся деревом. Подграф в G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ В любом связном графе найдется под­граф, являющийся деревом. Подграф в G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом.

Слайд 11


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Остовное дерево в графе G строится просто: выбираем произволь­ное его ребро и последовательно добавляем другие ребра, не созда­вая при этом циклов, до тех пор, пока нельзя будет добавить ника­кого ребра, не получив при этом цикла. Для построения остовного дерева в графе из n вершин необходимо выбрать ровно n - 1 ребро.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Остовное дерево в графе G строится просто: выбираем произволь­ное его ребро и последовательно добавляем другие ребра, не созда­вая при этом циклов, до тех пор, пока нельзя будет добавить ника­кого ребра, не получив при этом цикла. Для построения остовного дерева в графе из n вершин необходимо выбрать ровно n - 1 ребро.

Слайд 12


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Все остовные деревья графа (рис. 16), представлены на рисунке 17. Рисунок 16
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Все остовные деревья графа (рис. 16), представлены на рисунке 17. Рисунок 16

Слайд 13


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Рисунок 17
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Рисунок 17

Слайд 14


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Нахождение минимального остовного дерева (minimal spanning tree – MST). В графе G=(V, E) рассмотрим U – некоторое подмножество V, такое что U і V-U не пусты. Пусть (u, v) – ребро наименьшей стоимости, одна вершина которого – u принадлежит U, а другая – v принадлежит V-U. Тогда существует некоторое MST, которое содержит ребро (u, v).
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Нахождение минимального остовного дерева (minimal spanning tree – MST). В графе G=(V, E) рассмотрим U – некоторое подмножество V, такое что U і V-U не пусты. Пусть (u, v) – ребро наименьшей стоимости, одна вершина которого – u принадлежит U, а другая – v принадлежит V-U. Тогда существует некоторое MST, которое содержит ребро (u, v).

Слайд 15


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ На этом свойстве основан алгоритм Прима. Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U. Перебрав все вершины, находим минимальный остов.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ На этом свойстве основан алгоритм Прима. Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U. Перебрав все вершины, находим минимальный остов.

Слайд 16


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Найдем минимальный остов графа (рис. 18). Рисунок 18
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Найдем минимальный остов графа (рис. 18). Рисунок 18

Слайд 17


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ U={0}, V-U={A,B,C,D,E}. Начнем с вершины В: U={B}, V-U={A,C,D,E}. Выбираем ребро с наименьшим весом – это ребро ВА (вес – 1): U={B,A}, V-U={C,D,E}. Теперь выбираем ребро с наименьшим весом к оставшимся вершинам, т.е. из V-U ={C,D,E}. Если вес ребер одинаковый – выбираем любое, например ребро ВС (вес ребра – 3): U={B,A,C}, V-U={D,E}.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ U={0}, V-U={A,B,C,D,E}. Начнем с вершины В: U={B}, V-U={A,C,D,E}. Выбираем ребро с наименьшим весом – это ребро ВА (вес – 1): U={B,A}, V-U={C,D,E}. Теперь выбираем ребро с наименьшим весом к оставшимся вершинам, т.е. из V-U ={C,D,E}. Если вес ребер одинаковый – выбираем любое, например ребро ВС (вес ребра – 3): U={B,A,C}, V-U={D,E}.

Слайд 18


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Опять выбираем ребро с наименьшим весом к оставшимся вершинам, т.е. из V-U ={D,E}, например, ребро СЕ (вес ребра – 2): U={B,A,C,Е}, V-U={D}. Остается ребро ED: U={B,A,C,Е,D}, V-U={0}.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Опять выбираем ребро с наименьшим весом к оставшимся вершинам, т.е. из V-U ={D,E}, например, ребро СЕ (вес ребра – 2): U={B,A,C,Е}, V-U={D}. Остается ребро ED: U={B,A,C,Е,D}, V-U={0}.

Слайд 19


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ По предложенной взвешенной матрице смежности восстановить граф и найти его все возможные минимальные остовные деревья.
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ По предложенной взвешенной матрице смежности восстановить граф и найти его все возможные минимальные остовные деревья.

Слайд 20


ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Задача. Являются ли графы, задаваемые следующими ма­трицами смежности, деревьями?
Описание слайда:
ТЕОРИЯ ГРАФОВ ДЕРЕВЬЯ Задача. Являются ли графы, задаваемые следующими ма­трицами смежности, деревьями?

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию