Презентация на тему "Введение в теорию графов" 11 класс

Содержание

• 
  Слайд 1

  Введение в теорию графов

• 
  Слайд 2

  Задача прокладки коммуникаций

  2 3 4 1 5

• 
  Слайд 3

  Граф G:

  G=(V,R),где V – множество вершин R – множество рёбер, соединяющих пары вершин V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

• 
  Слайд 4
  

  Смежные вершины – те, которые соединены рёбрами V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

• 
  Слайд 5
  

  Мощность множеств V и R- количество вершин и количество ребер соответственно V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 5 вершин и 8 рёбер

• 
  Слайд 6
  

  ребро и любая из его двух вершин называются инцидентными V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

• 
  Слайд 7
  

  Степень вершины – количество инцидентных ей рёбер V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 Степень V3 – 3 Степень V5– 4

• 
  Слайд 8
  

  Маршрут графа – это последовательность чередующихся вершин и рёбер Замкнутый (циклическим) – называется тот маршрут, у которого начальная и конечная вершины совпадают V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

• 
  Слайд 9
  

  Маршрут называется простой цепью, если все его вершины и рёбра - различны V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

• 
  Слайд 10
  

  Граф является связным если каждая его вершина достижима из другой вершины V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15

• 
  Слайд 11
  

  Вершины, не имеющие инцидентных рёбер, называются изолированными вершинами. V2 V3 V1 V4 V5 R12 R23 R34 R14 R25 R35 R45 R15 V6