Введение в теорию графов 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику Н.Д.Угриновича. - презентация

1 Введение в теорию графов 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику Н.Д.Угриновича

2 Введение в теорию Цель: проектирование компьютерных сетей, телефонных линий, трубопроводов Задача: минимизировать затраты на прокладку коммуникаций Здание, к которому проводятся коммуникации

3 Основные понятия Граф G G = (V,R) V – множество вершин, R – множество ребер (R) = Ø Примеры: Населенные пункты – дороги, Вершины треугольника – стороны треугольника, Перекрестки улиц – улицы. Множества V и R – конечные, если можно перечислить все ребра и вершины графа. Мощность множества V равна 5, множества R равна 8.

4 Основные понятия Граф G V – множество вершин, R – множество ребер V 1 и V 2 – смежные вершины, соединяемые одним ребром R 12. Ребро и любая из его вершин – инцидентные. Количество инцидентных ребер вершины – степень вершины. Маршрут графа – последовательность чередующихся вершин и ребер. Цикл графа (замкнутый маршрут) – если начальная и конечная вершина маршрута совпадают. Например, в графе G: V1 R12 V2 R23 V3 R34 V4 R14 V1 V2 R23 V3 R35 V5 R25 V2 Простая цепь – маршрут, если все его вершины и ребра различны. Длина маршрута = количеству входящих в него ребер.

5 Основные понятия Граф G V – множество вершин, R – множество ребер Одна вершина достижима из другой, если между ними проложен маршрут. Связный граф – если каждая вершина является достижимой из любой другой. Изолированные вершины – вершины, не имеющие инцидентных ребер. Степень таких вершин нулевая. Изолированные вершины недостижимы из других вершин.

6 Ориентированные графы (орграфы) Каждое ребро (дуга) имеет одно направление Пример: в системе улиц имеются улицы с односторонним движением. Понятия: входящая степень вершины, исходящая степень вершины

7 Работа самостоятельно: указать множество вершин и их степени, множество ребер, мощность, конечность, наличие циклов, изолированных вершин, связность графов.