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

6.3Типы графов

Классификация графов по типам проводится по различным его характеристикам.

Классификация по типу ребер.

² Ориентированный граф (орграф, диграф – directed graph) –

»

это граф без звеньев: U= ?.

~

² Неориентированный граф: U= ?.

±

² Граф без петель: U= ?. Возможны варианты: ориентированный граф без петель, неориентированный граф без петель.

»~ ±

²Вырожденный граф: U= ?, U= ? , U=6 ?.

²Пустой граф: U = ?.

Классификация по числу ребер, соединяющих пару вершин.

p-граф – это такой граф, в котором каждая пара вершин соединена не более чем p ребрами, т.е.

8x; y 2 X[s(x; y) 6 p].

При p = 1 p-граф называется униграфом, а при p > 1 – мультиграфом; при p = 0 граф вырожденный или пустой.

Граф общего вида, в котором все вершины попарно смежны, называется плотным.

Граф является полным в своем классе, если он содержит все ребра, возможные при принадлежности графа к данному классу. Например, p-граф будет полным, если при каждой вершине будет ровно p петель, а каждая пара различных вершин соединена ровно p ребрами (причем среди ребер могут быть как звенья, так и дуги любых направлений). В полном ориентированном униграфе без петель из каждой вершины в другую идет ровно одна дуга. Для графов общего вида понятие полноты не имеет смысла.

Примеры 6.9.

1. Полный 3-граф (на 4-х вершинах).

2. Полный ориентированный униграф.

¾» ¾»

½¼ ½¼

З а м е ч а н и е. Если граф задан как бинарное отношение, то графы можно классифицировать по типам (свойствам) бинарных отношений. Так граф может быть рефлексивным, симметричным, транзитивным, графом порядка и т.д. Например, полный симметричный и рефлексивный граф есть полный ориентированный униграф.

Примером классификации по топологии может служить планарный (плоский) граф. Граф называется планарным (плоским),

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

Наконец, графы можно классифицировать по мощности множеств его элементов. Если мощности вершин и ребер графа jXj; jUj конечны, то граф – конечный, в противном случае – бесконечный. Мы будем рассматривать только конечные графы. I

6.3.1 Обыкновенные графы

Очень важную роль в теории графов и ее приложениях играют неориентированные униграфы без петель – обыкновенные графы. Элементы матрицы соседства вершин обыкновенного графа G = (X; U; P ) имеют вид:

bii = s»(xi)°» 2, где s»(xi) = Pn s»(xi; xj),

j=1

i =6 j; bij = s»(xi; xj)°» 2,

s»(xi; xj) = s»(xj; xi) = 1, если вершины xi; xj смежны, s»(xi; xj) = s»(xj; xi) = 0, в противном случае.

Элементы матрицы смежности R будут, соответственно, таки-

ми:

rii = 0,

i 6= j; rij = bij.

Мы не потеряем никакой информации о графе, если наложим на полукольцо K определяющее соотношение °» 2 = 1 (не обязательно это делается всегда). Таким образом, обыкновенный граф можно определить как множество с заданным на нем бинарным симметричным антирефлексивным отношением смежности. При этом можно установить взаимно-однозначное соответствие между множеством всех ребер и множеством всех неупорядоченных пар смежных вершин, т.е. каждое ребро может быть представлено парой смежных вершин, как это и делается на практике. Мы будем обозначать ребра обыкновенного графа в виде пары (x; y) ,

»

либо xy . Сам граф G будем обозначать G = (X; U), указывая этим, что инцидентор P полностью определяется заданием множеств X и U . При этом U можно рассматривать как бинарное отношение смежности U µ X £ X.

Пример 6.10.