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

Слайд 2

Задача прокладки коммуникаций 2 3 4 1 5

Слайд 3

Граф G : G=(V,R) , где V – множество вершин R – множество рёбер, соединяющих пары вершин V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15

Слайд 4

Граф G : Смежные вершины – те, которые соединены рёбрами V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15

Слайд 5

Граф G : Мощность множеств V и R - количество вершин и количество ребер соответственно V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15 5 вершин и 8 рёбер

Слайд 6

Граф G : ребро и любая из его двух вершин называются инцидентными V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15

Слайд 7

Граф G : Степень вершины – количество инцидентных ей рёбер V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15 Степень V 3 – 3 Степень V 5 – 4

Слайд 8

Граф G : Маршрут графа – это последовательность чередующихся вершин и рёбер Замкнутый (циклическим) – называется тот маршрут, у которого начальная и конечная вершины совпадают V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15

Слайд 9

Граф G : Маршрут называется простой цепью , если все его вершины и рёбра - различны V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15

Слайд 10

Граф G : Граф является связным если каждая его вершина достижима из другой вершины V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15

Слайд 11

Граф G : Вершины, не имеющие инцидентных рёбер, называются изолированными вершинами . V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 34 R 14 R 25 R 35 R 45 R 15 V 6