Типы графов

1. Граф и ограф.

2. -граф (граф, построенный на вершинах и ребрах).

3. Полный граф на вершинах (все вершины смежны между собой). Пример ( )

4. Тривиальный граф (граф, состоящий из одной вершины).

5. Пустой граф (граф на вершинах, не содержащий ни одного ребра )

6. Двудольный граф (граф называется двудольным, если и и ). Примеры

7. Полный двудольный граф (двудольный граф, в котором каждая вершина одной доли смежна с каждой вершиной другой доли). Пример ( )

Операции на графах

Операция удаления ребра , ( ) - частичный граф графа .
Операция удаления вершины , ( - подграф графа , у которого удалена вершина )
Операция объединения графов ( ) Результат зависит от того, выполняется ли условие
Операция сложения графов ( , - полный двудольный граф, построенный на элементах и элементах , которые не являются общими для этих двух графов. )
Операция дополнения графа (до полного) , ( , ) Граф, изоморфный своему дополнению называется самодополнительным.
Операция произведения графов ( )

Пример

Сколько ребер имеет граф ?

Связность в графах Понятие цепи

Пусть - некоторый граф. Последовательность попарно инцидентных между собой вершин и ребер графа называется цепью.

и - концевые вершины цепи.

Длина цепи - число ребер, образующих цепь ( и - концевые вершины цепи).

Цепь называется составной, если она содержит повторяющиеся ребра. Цепь называется сложной, если она содержит повторяющиеся вершины за исключением, быть может, первой и последней. Цепь, которая не является ни составной, ни сложной называется простой. Цепь называется циклом, если концевые вершины цепи совпадают. Циклы также бывают простые, составные и сложные. - простой цикл, состоящий из ребер. Пусть и - некоторые вершины графа. Тогда расстояние между вершинами . Введенное таким образом понятие расстояния является метрикой на графах:

1) ; 2) ; 3) .

Диаметром графа называется величина .

Пример

(целая часть числа).

Связность графа

Говорят, что две вершины и связны, если существует простая цепь, в которой и являются концевыми вершинами. Граф называется связным, если любые две вершины его связны. Минимальное количество вершин графа, удаление которых делает граф несвязным (или тривиальным) называется вершинной связностью графа. Обозначается . Минимальное количество ребер графа, удаление которых делает граф несвязным (или тривиальным) называется реберной связностью графа. Обозначается .

Примеры

Если , то соответствующая вершина называется точкой сочленения графа. Если , то соответствующее ребро называется мостом графа.

Теорема Для любого графа .