2.1 Типы графов

Граф G = (V, E) называют полным, если для любой пары вершин v_i и v_j в V существует ребро (v_i, v_j) в неориентированном графе =(V,) т. е. для каждой пары вершин графа G должна существовать, по крайней мере, одна дуга, соединяющая их (рис. 5,а).

Граф G = (V, E) называется симметрическим, если в множестве дуг E для любой дуги (v_i, v_j) существует также противоположно ориентированная дуга (v_j, v_i) (рис. 5,б).

Антисимметрическим называется такой граф, для которого справедливо следующее условие: если дуга (vi, vj)∈ A, то во множестве A нет противоположно ориентированной дуги, т. е. (v_j, v_i)∉ A (рис. 5,в). Очевидно, что в антисимметрическом графе нет петель.

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

Комбинируя определения полного и симметрического графов и полного и антисимметрического графов, получили следующие определения:

• граф G =(V, E), в котором любая пара вершин (v_i, v_j) соединена двунаправленными дугами, называется полным симметрическим (рис. 5,г);

• граф G =(V, E), имеющий для каждой пары вершин (v_i, v_j) только одну дугу, называется полным антисимметрическим или турниром.

Рисунок 5

Связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью, называется деревом (рис 6). Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево.

Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (например, вершины v₁), равна 1, а полустепень захода вершины v₁ (называют корнем этого дерева) равна 0 (рис 6,б).

Рисунок 6

Граф G =(V, E), который может быть изображен на плоскости или сфере без пересечений называется планарным (рис 7).

Рисунок 7

На рис. 8 показаны непланарные графы. Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.

Рисунок 8

Неориентированный граф G = (V, E)называют двудольным, если множество его вершин V может быть разбито на такие два подмножества V^а и V^b, что каждое ребро имеет один конец в V^а , а другой в V^b (рис. 9,а).

Ориентированный граф G называется двудольным, если его неориентированный двойник – двудольный граф (рис. 9,б,в).

Двудольный граф G=(V^а∪V^b, E) называют полным, если для любых двух вершин v_i∈V^а и v_j ∈V^b существует ребро (v_i,v_j) в G=(V,E) (рис. 9,г).

Рисунок 9