X
Код презентации скопируйте его
Решение задач с помощью графов
Скачать эту презентацию
Презентация на тему Решение задач с помощью графов
Скачать эту презентациюCлайд 1
Cлайд 2
Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью множества различных путей перемещения по ребрам между некоторыми парами вершин Граф называется связным если любая пара его вершин — связная. Ребро соединяет две вершины графа элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом Вершина Ребро это ориентированное ребро. Дуга ребро, начало и конец которого находятся в одной и той же вершине Петля любой связный граф, не имеющий циклов. Дерево
Cлайд 3
Кенигсбергские мосты
Cлайд 4
Кенигсбергские мосты Можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Cлайд 5
Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мосты Важно, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста.
Cлайд 6
Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках. Нечетные вершины: А, B, C, D. 3 3 3 5
Cлайд 7
Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым графом Условия существования Эйлеровой линии: -граф связный -все вершины четные Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком Эйлеров граф
Cлайд 8
Алгоритм решения задач 1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты. 2. Определить степень каждой вершины и подписать возле нее. 3. Посчитать количество нечетных вершин. 4. Обход возможен: a. ЕСЛИ все вершины – четные, и его можно начать с любого участка. b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей. 5. Обход невозможен, если нечетных вершин больше 2. 6. Сделать ВЫВОД. 7. Указать Начало и Конец пути.
Cлайд 9
Достроить графы до Эйлеровых
Cлайд 10
Задача о 15 мостах В некоторой местности через протоки переброшено 15 мостов.
Cлайд 11
Построим граф, где вершины – острова и берега, а ребра – мосты. Нечетные вершины: D, E. ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен. Его Начало может быть в местности D, а Конец в местности E. 4 4 6 3 5 8
