- •Основные объекты графов
- •Способы задания графов
- •Графический способ задания графов.
- •Изоморфизм на графах
- •Элементы графов
- •Степень вершины. Степень графа
- •Типы графов
- •Операции на графах
- •Связность в графах Понятие цепи
- •Связность графа
- •Компоненты связности графа
- •Нахождение компонент связности
- •Связность в орграфах
- •Цикломатика графа
- •Алгоритм нахождения базисной системы циклов
- •Разделяющие множества. Разрезы
- •Алгоритм нахождения базисной системы разрезов
- •Устойчивость графа Внешняя устойчивость графа
- •Внешняя устойчивость орграфа
- •Внутренняя устойчивость графа
- •Алгоритм нахождения пустых подграфов
- •Полные подграфы. Плотность графа
- •Алгоритм нахождения полных подграфов
Типы графов
Граф и ограф.
-граф (граф, построенный на вершинах и ребрах).
Полный граф на вершинах (все вершины смежны между собой). Пример ( )
Тривиальный граф (граф, состоящий из одной вершины).
Пустой граф (граф на вершинах, не содержащий ни одного ребра )
Двудольный граф (граф называется двудольным, если и и ). Примеры
Полный двудольный граф (двудольный граф, в котором каждая вершина одной доли смежна с каждой вершиной другой доли). Пример ( )
Операции на графах
|
|
|
|
|
|
|
|
|
Граф, изоморфный своему дополнению называется самодополнительным. |
|
|
Пример
Сколько ребер имеет граф ?
Связность в графах Понятие цепи
Пусть - некоторый граф. Последовательность попарно инцидентных между собой вершин и ребер графа называется цепью.
и - концевые вершины цепи.
Длина цепи - число ребер, образующих цепь ( и - концевые вершины цепи).
Цепь называется составной, если она содержит повторяющиеся ребра. Цепь называется сложной, если она содержит повторяющиеся вершины за исключением, быть может, первой и последней. Цепь, которая не является ни составной, ни сложной называется простой. Цепь называется циклом, если концевые вершины цепи совпадают. Циклы также бывают простые, составные и сложные. - простой цикл, состоящий из ребер. Пусть и - некоторые вершины графа. Тогда расстояние между вершинами . Введенное таким образом понятие расстояния является метрикой на графах:
1) ; 2) ; 3) .
Диаметром графа называется величина .
Пример
(целая часть числа).
Связность графа
Говорят, что две вершины и связны, если существует простая цепь, в которой и являются концевыми вершинами. Граф называется связным, если любые две вершины его связны. Минимальное количество вершин графа, удаление которых делает граф несвязным (или тривиальным) называется вершинной связностью графа. Обозначается . Минимальное количество ребер графа, удаление которых делает граф несвязным (или тривиальным) называется реберной связностью графа. Обозначается .
Примеры
|
|
Если , то соответствующая вершина называется точкой сочленения графа. Если , то соответствующее ребро называется мостом графа.
Теорема Для любого графа .