Цель темы: рассмотреть основные понятия теории графов; применение графов для формализации задач
Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. НАПРИМЕР – Электрическая схема. - Карта дорог. - Описание конструкции. - Работа цифрового автомата.
В подобных случаях удобно рассматриваемые объекты изображать точками, называемыми вершинами, а связи между ними задавать линиями, называемыми ребрами. Множество вершин V, связи между которыми определены множеством ребер E, называют графом и обозначают G={V ; E}
Вершины и рёбра графа называются элементами графа, число вершин в графе — порядком, число рёбер — размером графа. Вершины U и V называются концевыми вершинами (или просто концами ) ребра e={U, V} . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают. Ребро называется петлёй, если его концы совпадают, то есть e={U, U} .
Ориентированный и неориентированный. Смешанный. Конечный и бесконечный. Полный граф. Мультиграф и псевдограф. Двудольный граф или биграф.
Задача Эйлера Неориентированный граф – граф, у которого ребра не имеют направленности. мосты Территории города
Часто связи между объектами характеризуются определенной ориентацией – направлением. НАПРИМЕР - течение тока, направление передачи сигнала, направление движения автомобилей, причинная связь. Для указания направления ребро графа отмечается стрелкой и называется дугой, а граф с ориентированными ребрами называется орграфом.
Если множество вершин графа конечно, то он называется конечным графом. Существуют бесконечные графы, но мы их рассматривать не будем. Ориентированный конечный граф Смешанный конечный граф
Граф без петель и кратных ребер называется обыкновенным или простым графом. Граф без петель, но с кратными ребрами называется мультиграфом. Граф содержащий петли и кратные ребра называют псевдографом.
Простой граф, у которого любые две вершины соединены называется полным. Если граф не имеет ребер, то все его вершины изолированы и он называется пустым или нульграфом. Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V1 и V2, что не существует ребер, соединяющие вершины одного и того же подмножества, то он называется биграфом.
Две вершины Vi и Vj графа G={V, E} называют смежными. Если они являются вершинами ребра Отношение смежности на множестве вершин графа можно определить, представив каждое ребро как пару смежных вершин. Множество вершин V с определенным на нем отношением смежности полностью определяет граф.
Если вершина Vi является началом или концом ребра Ek, то говорят что они инцидентны. Инцидентность определяет отношение разнородных объектов вершин и ребер графа. В орграфах различают положительную и отрицательную инцидентность. Число ребер, инцидентных вершине называют степенью вершины. Петля учитывается дважды.
Для любого псевдографа сумма степеней всех его вершин – число четное равное удвоенному числу ребер графа. ДОКАЗАТЕЛЬСТВО : Заключение этой теоремы следует из того, что каждое ребро имеет два конца, а каждая петля учитывается два раза. СЛЕДСТВИЕ : В любом конечном графе число вершин нечетной степени четно.
Любой граф может быть задан матрицей смежности или матрицей инцидентности. ПРИМЕР матрицы смежности. ЗАДАЧА. Используя матрицу смежности постройте граф.
ребра вершины петля Для орграфа направление определяется знаком 1 или -1.
Графы в которых сохраняются отношения инцидентности при различных графических изображениях называют изоморфными. Планарный граф – без пересечений ребер
Три дома с враждующими соседями и три колодца. ВОПРОС Можно ли проложить дороги от домов к колодцам так, что бы соседи идя к колодцу не встречались друг с другом?
ДОМА КОЛОДЦЫ
У планарных графов существует закономерность между количеством вершин В ребер Р и граней Г. В – Р + Г = 2 ПРОВЕРИТЬ!!!
При анализе граф можно разобрать на отдельные части Часть графа Подграф Суграф v1 v4
Пусть G неориентированный граф. Маршрутом в G называется такая последовательность ребер, в которой каждые два ребра имеют инцидентную вершину. В маршруте одно и тоже ребро может встречаться несколько раз. В маршруте существует понятие начала и конца маршрута.
Соединение узлов – это маршрут. Узел отправитель Узел получатель. Коммутация – соединение конечных узлов через сеть транзитных узлов. ВОПРОС СКОЛЬКО СУЩЕСТВУЕТ МАРШРУТОВ ИЗ УЗЛА 2 В УЗЕЛ 4;
Маршрут, все ребра которого различны называется цепью. Маршрут у которого различны все вершины называется простой цепью. Замкнутая цепь называется циклом. Понятие ориентированный маршрут используется на орграфе. Число ребер маршрута называется длиной пути.
Две вершины графа называются связанными если существует маршрут соединяющий эти вершины. Граф, у которого любая пара вершин связана называется связным графом. В противном случае граф называется несвязным.
Расстоянием между вершинами неориентированного связного графа называют минимальную длину простой цепи связывающую эти вершины. Центром графа называется вершина, от которой максимальное расстояние до других вершин являлось бы минимальным. Максимальное расстояние от центра графа до его вершин называется радиусом графа.
Задан граф. Найдите центр графа и его радиус. v3 v1 v4 v5 v2
Эйлеров цикл – цикл графа, содержащий все ребра графа. Эйлеров граф - граф, имеющий эйлеров цикл (Эйлеров цикл можно считать следом пера, вычерчивающего граф без отрыва от бумаги). ОПРЕДЕЛИТЕ ЭЛЕРОВ ЦИКЛ НА ГРАФАХ
Для того чтобы неориентированный граф G был эйлеровым, необходимо и достаточно, чтобы он был связным и степени его вершин были четными. Задача имеет решение ???
Неориентированный связный граф не имеющий петель и кратных ребер часто выгодно рассматривать как дерево. В дереве между двумя вершинами существует только одна цепь. Несвязный неориентированный граф, компонентами которого являются деревья называется лесом. Дерево состоящее из Р вершин имеет Р-1 ветвей
Дерево с шестью вершинами. Сколько Вариантов?
1. Объединением графов G 1( V 1, E 1) и G 2( V 2, E 2) называется граф G ( V, E ) = , где V = , E = . Аппарат теории множеств полностью применяется в теории графов
Семантическая сеть
Высокая отказоустойчивость, а главное минимальный диаметр равный двум для любых узлов Диаметр D = 2min(n \ 2) Связность I =2N Ширина бисекции B = 2n
Биология Химия. Экономика. Транспорт. Логистика.
