2. Классы графов.

Класс орграфов (ориентированных графов). Это граф G=(X,U), у которого =.

Класс неорграфов (неориентированных графов). Это граф G=(X,U), у которого =.

Класс смешанных графов. Это граф G=(X,U), у которого

 U,  U и   U.

Класс мультиграфов. Мультиграф - это граф G=(X,U), у которого имеются параллельные (кратные) рёбра, т.е.

 x,yx u_k y , x u_m y,…, x u_p y, u_{k ,}u_m,…, u_p  U.

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

Особо важную роль играют так называемые обыкновенные графы. Граф этого класса характеризуется следующими четырьмя свойствами:

1) он конечен;

2) он является неориентированным, т.е. не содержит дуг;

3) он не содержит петель;

4) он не содержит "параллельных" ("кратных") рёбер; иначе говоря, никакие две его вершины не могут соединяться более чем одним ребром (звеном).

Определение:

Обыкновенный граф – это неориентированный униграф без петель. Униграф - это граф, в котором смежные вершины связаны только одним неориентированным ребром.

3. Способы задания графов.

3.1. Геометрический.

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

3.2. Описание графа через предикат (инцидентор) p.

Говорят, что задан граф G=(X,U,P), если дано множество вершин Х, множество ребер U и трёхместный предикат (инцидентор) P, определяющий, какую пару вершин x_i, x_j, принадлежащих множеству вершин Х, соединяет ребро u_k=(x_i,x_j). Инцидентор P удовлетворяет двум условиям:

А. Инцидентор P определён на всех таких упорядоченных тройках элементов x, u, y, для которых x, y  X и u  U;

Б.  u  x, y {P(x, u, y)   x^’, y’[P(x’, u, y’)  (x = x’  y = y’)  (x = y’  y = x’)]} .

Условие Б говорит говорит о том, что каждое ребро графа соединяет какую-либо пару (xy) его вершин, но кроме этой пары может (хотя не обязательно) соединять ещё обратную пару (yx).

Для каждого u Є U истинно одно и только одно из следующих трёх высказываний:

 x, y[ x≠y & P (x,u,y) & ¬ P(y,u,x)]; (1)

 xP(x,u,x) ; (2)

 x, y[ x≠y & P (x,u,y) & P(y,u,x)]. (3)

В соответствии с этим множество U разбивается на три попарно не пересекающихся подмножества −

множество дуг; множество петель; множество звеньев (неор. ребро).