26. Графы. Типы графов

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

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

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

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

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

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

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

Рисунок 5

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

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

Рисунок 6

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

Рисунок 7

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

Рисунок 8

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

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

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

Рисунок 9

< Предыдущая		Следующая >