Презентация на тему "Задачи на графах"

Содержание

• 
  Слайд 1

  Задачи на графах

• 
  Слайд 2
  
• 
  Слайд 3
  
• 
  Слайд 4
  
• 
  Слайд 5
  

  2. Список ребер – перечисление всех ребер графа как пар обозначений связываемых этими ребрами вершин.

• 
  Слайд 6
  
• 
  Слайд 7

  Разбор задач:

• 
  Слайд 8

  Решение

  Задача на построение графа. Вершинами искомого графа являются названия городов от А до F, ребра определяются наличием в таблице чисел, указывающих весА этих ребер. Для построения графа достаточно разместить точки А, В, С, D, E, F и соединить их линиями.

• 
  Слайд 9
  

  Данный граф является ориентированным или неориентированным? Неориентированный граф, т.к. в условии задачи не указано, что нужно двигаться в каком-то направлении.

• 
  Слайд 10

  Получается граф вида:

• 
  Слайд 11
  
• 
  Слайд 12
  
• 
  Слайд 13
  

  Граф является ориентированным или неориентированным? По данному графу нужно проследить все возможные пути от А до Н. Для этого строятся вспомогательные деревья. Построение начинается с вершины А. К каким вершинам ведут ребра исходного графа?

• 
  Слайд 14
  
• 
  Слайд 15
  
• 
  Слайд 16

  м

• 
  Слайд 17
  
• 
  Слайд 18
  
• 
  Слайд 19
  
• 
  Слайд 20

  Самостоятельное решение:

• 
  Слайд 21
  
• 
  Слайд 22
  

  http://inf.reshuege.ru/test?theme=213 Задачи по матрице смежности http://inf.reshuege.ru/test?theme=203 Задачи по графам