6.3. Типы графов |
209 |
|
|
|
|
Дезориентация дуг орграфа заключается в наложении на образующие полукольца K следующих определяющих соотношений:
°> °< = 1;°< °> = 0;°» 2 = 1; 2 = 1; (т.е.1 + 1 = 1),
то есть в переходе к булевой алгебре Bf0; 1g).
»
Матрица смежности R(G) над B неориентированного графа G =
|
|
|
|
|
! |
! |
! |
(X; U) получается из матрицы смежности R(G) орграфа G= (X; U) |
|||||||
следующим образом: |
|
|
|
|
|||
» |
! |
T |
! |
T |
– знак транспонирования). |
|
|
R(G) = R(G) ¢ R |
(G) ( |
|
|
|
|||
6.3.3 Двудольные (бихроматические) графы
Обыкновенный граф G = (X; U) называется двудольным (бихроматическим, графом Кенига, простым), если множество его вершин X можно представить в виде объединения двух непересекающихся подмножеств X1 и X2, таких, что никакие вершины одного и того же множества не смежны, т.е.
X = X1 [ X2; X1 \ X2 = ?,
»
8x; y 2 X[xy2 U ) (x 2 X1&y 2 X2) _ (x 2 X2&y 2 X1)].
Двудольный граф записывают в виде G = (X1; X2; U). Тем самым задается и конкретный граф.
Пример 6.13.
1 |
2 |
5 |
r |
r |
r |
r 7
r |
r |
r |
4 |
3 |
6 |
Граф, представленный на рисунке, может быть задан как двудольный четырьмя различными способами:
G1 = (f1; 3; 5; 7g; f2; 4; 6g; U); G2 = (f1; 3; 6; 7g; f2; 4; 5g; U); G3 = (f1; 3; 5g; f2; 4; 6; 7g; U); G4 = (f1; 3; 6g; f2; 4; 5; 7g; U);
210 |
Глава 6. Определения и примеры |
|
|
Матрица смежности двудольного графа полностью определяется своей прямоугольной подматрицей, строки которой соответствуют вершинам X1, а столбцы – вершинам X2.
Для нашего примера G1 :
|
R |
2 |
4 |
6 |
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
|
R = |
3 |
1 |
1 |
0 |
J |
|
5 |
0 |
0 |
1 |
|
|
7 |
0 |
0 |
0 |
|
|
|
|
|
|
|
Задание двудольного графа G = (X1; X2; U) равносильно заданию двух множеств X1 и X2 и многозначного отображения ¡, которое ставит в соответствие каждой вершине x 2 X подмножество (возможно, пустое) ¡ x µ X2 всех смежных с x вершин y 2 X2.
Двудольный граф называется полным, если каждая вершина множества X1 смежна с каждой вершиной множества X2.
Такой граф определяется с точностью до изоморфизма, сохраняющего каждое из подмножеств X1, X2 заданием упорядоченной пары чисел j X! j, j X2 j. Полный двудольный граф обозначается
KjX1j;jX2j.
Например, K3;4 – полный двудольный граф с jX1j = 3; jX2j = 4.
6.3.4 Помеченные и взвешенные графы
Задавая на вершинах и на ребрах графа G = (X; U; P ) функции f : X 7!L,
g : U 7!C,
где L и C – произвольные множества, получим помеченный граф
G[f; g] = (X; U; P ; f; g).
На множествах X и U можно задать и более, чем по одной функции, или, наоборот, можно задать функцию, например, только на ребрах. Значения функций f и g будем называть метками. В том случае, если значения функций есть численные значения, будем называть граф взвешенным, а сами метки – весами.
Примеры 6.14.
1. Карта дорог : L – названия населенных пунктов, C – расстояния между ними.