P = fP (a; 1; b); P (a; 3; c); P (c; 3; a); P (a; 4; d); P (c; 2; b),

P (d; 5; a)g.

G0 = (X0; U0; P 0); X0 = fe; f; g; hg; U0 = fs; t; u; v; zg;

P 0 = fP 0(e; t; g); P 0(e; u; f); P 0(f; u; e); P 0(f; v; g),

P 0(f; s; h); P 0(h; z; f)g.

Взаимно-однозначное соответствие устанавливается следующим образом:

a $ f; b $ g; c $ e; d $ h;

1 $ v; 2 $ t; 3 $ u; 4 $ s; 5 $ z;

P (a; 1; b) , P 0(f; v; g); P (a; 3; c)&P (c; 3; a) ,

, P 0(f; u; e)&P 0(e; u; f),

P (a; 4; d) , P 0(f; s; h); P (c; 2; b) , P 0(e; t; g),

P (d; 5; a) , P 0(h; z; f). J

6.2Задание графов с помощью матриц

Чтобы задать конкретный граф, нужно задать пару множеств X; U и инцидентор P . Так как P – трехместный предикат (тернарное отношение), то в общем случае для задания графа нужна трехмерная матрица. Использование многозначной логики позволяет представить граф двумерной матрицей. Другой способ, равносильный применению пятизначной логики состоит в следующем.

6.2.1 Матрица инциденций

Пусть K – свободное полукольцо с нулем и образующими элементами

°> , °< , °± , °» , 0.

Пусть задан граф G = (X; U; P ) , X = fx1; : : : ; xng , U = fu1; : : : ; umg

, U =6 ?.

Определение. Матрицей инциденций над полукольцом K графа G называется прямоугольная таблица

A = A(G) = kaijk; i = 1; : : : ; n; j = 1; : : : ; m,

элементы которой aij принадлежат полукольцу K и определяются по графу G следующим образом:

если uj – дуга, исходящая из вершины xi, то aij = °> ; если uj – дуга, заходящая в вершину xi, то aij = °< ; если uj – звено, инцидентное вершине xi, то aij = °» ; если uj – петля при вершине xi, то aij = °± ;

если ребро uj и вершина xi не инцидентны, то aij = 0.

Пример 6.6.

Для графа, изображенного на рисунке, матрица инциденций имеет следующий вид:

6.2.2 Матрица соседства вершин

Определение. Квадратная матрица B(G) = B = AAT порядка n = jXj называется матрицей соседства вершин.

Пример 6.7.

Для графа из примера 6.6 получим:

Здесь 2 °± 2 означает °± ¢ °± + °± ¢ °± . (Знак умножения ¢ мы договорились опускать ранее), °> 2 означает °> ¢ °> и т.д. J

Из определения матрицы соседства вершин B следует, что ее элементы имеют вид

bii = s+(xi) °> 2 + s¡(xi) °< 2 + s±(xi) °± 2 + s»(xi) °» 2,

i =6 j; bij = s+(xi; xj) °> °< +s¡(xi; xj) °< °> +s»(xi; xj) °» 2,

где

s+(xi) – число дуг, исходящих из вершины xi; s¡(xi) – число дуг, заходящих в вершину xi; s±(xi) – число петель при вершине xi;

s»(xi) –число звеньев, инцидентных вершине xi; s+(xi; xj) – число дуг, идущих из xi в xj;

s¡(xi; xj) – число дуг, идущих из xj в xi.

Число ребер, соединяющих вершины x; y графа: s(x; y) = s+(x; y) + s¡(x; y) + s»(x; y), если x 6= y;

s(x; y) = s±(x; y), если x = y. Степень вершины x обозначается s(x) и определяется как

s(x) = s+(x) + s¡(x) + s±(x) + s»(x)

(число ребер, инцидентных вершине x). Валентность v(x) вершины x есть

v(x) = s+(x) + s¡(x) + 2s±(x) + s»(x)

(число “усиков” при вершине). Очевидно,

P v(x) = 2jUj = 2m(G).

x2X

Число ребер, соединяющих вершину x с другими вершинами графа (т.е. число непетель, инцидентных x) есть

2s(x) ¡ v(x) = s+(x) + s¡(x) + s»(x).

²Если 2s(x)¡v(x) = 0, то вершина x называется изолированной (при вершине могут быть петли);

²Если s(x) = 0 или v(x) = 0, вершина x называется голой (нет никаких ребер, инцидентных x).

²Если 2s(x) ¡ v(x) = 1, то вершина называется висячей.

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

6.2.3 Матрица смежности

Определение. Матрица смежности R(G) = R = krijk графа получается из матрицы соседства вершин B(G) следующим образом:

rii = s±(xi)°± 2,

i 6= j rij = bij.

Переход к матрице смежности не приводит к дальнейшей потере информации о графе, так как

s+(x) = Pn s+(x; xi);

i=1

s¡(x) = Pn s¡(x; xi);

i=1

s»(x) = Pn s»(x; xi).

i=1

Пример 6.8.

Из матрицы соседства вершин в предыдущем примере получим матрицу смежности вершин:

Очень редко используется матрица соседства ребер

H(G) = H = AT A порядка m = jUj.