Полный граф. Двудольный граф. Цикломатическое число графа. Гамильтонов цикл. Число планарности

Теория графов.

Ориентированные – дуги (все - орграф), неориентированные – рёбра (все - неограф).

Полный граф – считай, полносвязный. Число рёбер U=n(n-1)/2

Двудольный граф – если можно разбить граф на 2 непересек. множества и в рамках каждого из них элементы не соединены между собой.

Изоморфные графы – одинак. кол-во вершин и каждой соединённой паре вершин в одном графе соответств. соединен. пара в другом.

Эйлер цикл – в котором содержатся все рёбра (чётность всех степеней его вершин).

Гамильтонов цикл – простой цикл, проходящий через все вершины (r(xi)>= n/2, где r – степень вершины). Дерево – связанный граф без циклов. 

Цикломатическое число графа – число рёбер, которые нужно убрать из графа, чтобы получить дерево (избавиться от циклов).

Хроматическое число – миним. кол-во цветов.

Внурт. устойчив-ть (независимость) – L или a (альфа) – максимальное число несмежных между собой вершин (рисуем граф, ищем множ-ва несмежных вершин).

Внешн. устойч. (доминирование) – B - каждая вершина графа находится на расстоянии не более единицы от внешнеустойчивого множества. Т.е. это мно-во, с которым соединены все остальные вершины хотябы одним ребром. Выбираем миним.

Плоский граф – не пересек. рёбра, изоморфный ему – планарный.

Число планарности – Q -  миним. число рёбер, кот. надо удалить, чтобы граф стал планарным.

Гомеоморфные – если после сжатия или расширения могут стать изоморфными.

Графы Понтрягина-Куратовского: К5 – непланарный граф с мин.кол-вом вершин (n=5, К=10); К3,3 – двудольный непланарный граф с min кол-вом рёбер (n=6, K=9)

Гиперграф – рёбра могут соединять более 2 вершин. В ВТ юзают матрицы смежности и инцидентности. Задачи: независимость и доминирование, раскраска, размещение центров, размещение медиан (сумма мин. расстояний – в миним.), задача на звенья (миним. дерево для соединения всех вершин), кратчайшие пути, эйлеровые (почтальон) и гамильтоновы (комивоежёр) циклы, потоки, транспортная задача.

Плоский граф – не пересек. рёбра, изоморфный ему – планарный.

Число планарности – Q -  миним. число рёбер, кот. надо удалить, чтобы граф стал планарным.

Гомеоморфные – если после сжатия или расширения могут стать изоморфными.

Графы Понтрягина-Куратовского: К5 – непланарный граф с мин.кол-вом вершин (n=5, К=10); К3,3 – двудольный непланарный граф с min кол-вом рёбер (n=6, K=9)

Гиперграф – рёбра могут соединять более 2 вершин. В ВТ юзают матрицы смежности и инцидентности. Задачи: независимость и доминирование, раскраска, размещение центров, размещение медиан (сумма мин. расстояний – в миним.), задача на звенья (миним. дерево для соединения всех вершин), кратчайшие пути, эйлеровые (почтальон) и гамильтоновы (комивоежёр) циклы, потоки, транспортная задача.