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

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ Выполнила: Рогозянская Л.М. учитель информатики МКОУ Жилинская СОШ

ЗАДАЧА: Для игры в локальной сети необходимо соединить компьютерным кабелем шесть домов РЕШЕНИЕ ЗАДАЧИ: Определение маршрута прокладки кабеля минимальной длины, но при этом подходящего к каждому дому. Для решения таких задач используют теорию графов. 1 4 5 3 6 2 400 700 100 200 100 800 200 300 200 600

1 4 5 3 6 2 100 200 100 200 300 200 Экономия: 2500 м кабеля

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ v5 v2 v3 v1 v4 R34 R45 R15 R23 R35 R34 R12 R14 V-ВЕРШИНЫ (населенные пункты, компьютеры, элементы блок-схем, логические элементы, стационарные телефоны и т.д. R-Ребра (дороги, линии связи между компьютерами, стороны геометрических фигур) Смежные вершины (соединенные ребром)

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ v5 v2 v3 v1 v4 R34 R45 R15 R23 R35 R34 R12 R14 количество вершин и количество ребер определяют мощность множеств V и R G=(V,R) - граф G Ребро и любая из его двух вершин называются инцидентными Степень вершины – количество инцидентных ей рёбер V-5 R-8

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ v5 v2 v3 v1 v4 R34 R45 R15 R23 R35 R34 R12 R14 МАРШРУТ ГРАФА –ПОСЛЕДОВАТЕЛЬНОСТЬ ЧЕРЕДУЮЩИХСЯ ВЕРШИН И РЕБЕР Простая цепь - все его вершины и ребра различны Замкнутая цепь – начальная и конечная вершины совпадают Связной граф – любая вершина достижима из любой другой вершины Изолированные вершины - не имеют инцидентных ребер (например v6) v6

ТИПЫ ГРАФОВ

ОПИСАНИЕ ГРАФА С ПОМОЩЬЮ МАТРИЦЫ СМЕЖНОСТИ R51 ВЕС СЕТИ = 240 1 2 3 4 5 1 0 1 0 1 1 2 1 0 1 0 1 3 0 1 0 1 1 4 1 0 1 0 1 5 1 1 1 1 0 1 2 3 4 5 1 0 50 0 25 10 2 50 0 25 0 30 3 0 25 0 50 35 4 25 0 50 0 15 5 10 30 35 15 0