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

Содержание

• 
  Слайд 1

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

• 
  Слайд 2
  

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

• 
  Слайд 3

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

• 
  Слайд 4

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

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

• 
  Слайд 5
  

  Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мосты

  Важно, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста. С А Д В

• 
  Слайд 6
  

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

• 
  Слайд 7
  

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

• 
  Слайд 8

  Алгоритм решения задач

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

• 
  Слайд 9

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

  А А А Б Б Г Г Д А Б Г В В В В Б

• 
  Слайд 10

  Задача о 15 мостах

  В некоторой местности через протоки переброшено 15 мостов. А E В F С D

• 
  Слайд 11

  Построим граф, где вершины – острова и берега, а ребра – мосты.

  Нечетные вершины: D, E.  ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен. Его Начало может быть в местности D, а Конец в местности E. А E В F С D 4 4 6 3 5 8