Презентация на тему: Решение задач с помощью графов

Решение задач с помощьюграфов

Простейшая модель системы.Отображает элементарный состав системы и структуру связейГраф с возможностью множества различных путей перемещения по ребрам между некоторыми парами вершинэлемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графомРебро соединяет две вершины графаэто ориентированное ребро.ребро, начало и конец которого находятся в одной и той же вершинеесли любая пара его вершин — связная.любой связный граф, не имеющий циклов.

Кенигсбергские мосты

Кенигсбергские мостыМожно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мостыВажно, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста.

Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках.Нечетные вершины: А, B, C, D.

Эйлеров граф Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым графомУсловия существования Эйлеровой линии:-граф связный-все вершины четные Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком

Алгоритм решения задач1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты. 2. Определить степень каждой вершины и подписать возле нее.3. Посчитать количество нечетных вершин.4. Обход возможен:a. ЕСЛИ все вершины – четные, и его можно начать с любого участка.b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей.5. Обход невозможен, если нечетных вершин больше 2.6. Сделать ВЫВОД.7. Указать Начало и Конец пути.

Достроить графы до Эйлеровых

Задача о 15 мостахВ некоторой местности через протоки переброшено 15 мостов.

Построим граф, где вершины – острова и берега, а ребра – мосты.Нечетные вершины: D, E. ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен.Его Начало может быть в местности D, а Конец в местности E.