Презентация по информатике «Введение в теорию графов» (10–11 классы)

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

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

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

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

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

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

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

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

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