ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5664
Скачиваний: 10
56
тем свойством, что любая вершина из Х»=Х\Х’ смежна по край-
ней мере с одной вершиной Х’. Размер наименьшего всесмежного
графа называется числом внешней устойчивости
β(L).
Пример 2.5.5. Задача о пяти ферзях.
Сколько ферзей достаточно расставить на шахматной доске
так, чтобы каждая клетка доски находилась под ударом. Ответ:
β=5 для ферзей, β=8 для ладей, β=12 для коней, β=8 для слонов.
К задачам рассматриваемого типа сводятся многочисленные
практические задачи распределения ресурсов.
Алгоритм Магу
−Уэйсмана нахождения максимальных пус-
тых подграфов.
Пусть L=(x,u) – заданный обыкновенный граф с
х={x
1
,x
2
,...,x
n
}и с пронумерованным множеством ребер. Символы
вершин x
1
,x
2
,...,x
n
добавляются в качестве
новых образующих
ξ,
η, ζ, θ полукольца К, и расширенную таким образом систему
подчиним условиям
θ=1, 2=1, x
i
2
=x
i
, x
i
+1=1;
а также условиям коммутативности, ассоциативности и дистри-
бутивности.
Полученное полукольцо включает в себя булеву алгебру
В
х
=В{x
1
,x
2
,...,x
n
} многочленов от символов х
i
с коэффициентами
из B=B{0,1}.
Можно показать, что в К
х
имеет место закон поглощения:
∀a,b∈K
x
(a+ab)=a.
Например,
x
1
,x
2
+x
1
x
2
x
3
x
4
=x
1
x
2
(1+x
3
x
4
)=
=x
1
x
2
[(1+x
3
)+x
3
x
4
]=x
1
x
2
[1+(x
3
+x
3
+x
4
)]=
=x
1
x
2
[1+x
3
(1+x
4
)]=x
1
x
2
(1+x
3
)=x
1
x
2
.
Из матрицы инциденций А=||a
ij
|| (i=1,n; j=1,m) графа L на К
х
образуем новую матрицу А
x
=||a
ij
x
i
|| и составим произведение
П
L
= П
L
(x
1
,x
2
,...,x
n
)=
∏∑
= =
m
j
n
i
i
ij
x
a
1
1
.
Очевидно, что j-й сомножитель произведения есть сумма
двух слагаемых, представляющих те две вершины, которые в
графе L соединены j-ым ребром.
57
Подмножество вершин у
∈х порождает в L пустой подграф
тогда и только тогда, когда для системы {x
i
0
}значения перемен-
ных определены условиями:
x
i
∉y x
i
0
=1;
x
i
∈y x
i
0
=0.
Имеет место равенство П
L
(x
i
0
, x
2
0,
..., x
n
0
)=1.
В самом деле, для пустого подграфа с подмножеством вер-
шин у необходимо и достаточно, чтобы каждое ребро графа L
было инцидентно хотя бы одной вершине из х\у, т.е. чтобы в ка-
ждом сомножителе произведения П
L
(x
1
,x
2
,...,x
n
) по крайней мере
одно из двух слагаемых представляло вершину не из у; но в этом
и только этом случае подстановка единиц вместо переменных x
i
,
обозначающих вершины не из у, обратит все произведение П
L
в
единицу.
Итак, с помощью вычисления конкретных значений произ-
ведения П
L
в В{0,1} можно для любого заданного подмножества
у
∈х узнать, является ли порожденный им подграф пустым.
Далее, пользуясь дистрибутивным, ассоциативным и комму-
тативным законами, раскроем в произведении П
L
все скобки и в
каждом слагаемом устраним повторения сомножителей с помо-
щью x
i
=x
i
2
.
И наконец, применяя закон поглощения, приведем всю сум-
му к минимальной форме, которая, как известно из математиче-
ской логики, определяется однозначно, ибо в нашем случае нигде
не фигурирует операция логического отрицания в В{0,1}. Полу-
ченный многочлен обозначим через
Σ
L
=
Σ
L
(x
1
,x
2
,...,x
n
). Разумеется,
что при любой системе значений {x
i
} из B(0,1) имеет место:
П
L
(x
i
0
, x
2
0,
..., x
n
0
) =
Σ
L
(x
i
0
, x
2
0,
..., x
n
0
).
Каждому слагаемому в
Σ
L
отнесем подграф, порожденный
всеми теми вершинами графа L, которые не фигурируют в каче-
стве сомножителей этого слагаемого. Покажем, что все выбран-
ные таким образом подграфы М
1
,М
2
,...,М
К
− пустые и ни один из
них не есть подграф другого, а всякий пустой подграф графа L
содержится хотя бы в одном из них. Действительно, если все пе-
ременные в слагаемом, соответствующем M
j
(j=1,к), положить
равными единице, а остальные переменные положить равными
58
нулю, то
Σ
L
=П
L
=1, откуда M
j
– пустой. Если M
j
− подграф
M
l
(j=1,к; l=1,к; l
≠j), то все переменные слагаемого, соответст-
вующего M
l
, присутствовали бы также в слагаемом, отвечающем
М
j
, и тогда второе слагаемое поглощалось бы первым. Наконец,
если М=(у,
∅) – произвольный пустой подграф графа L, то со-
ставленная для него система значений {x
i
0
}
y
обращает П
L
в еди-
ницу, следовательно, в П
L
есть слагаемое, не имеющее сомножи-
телей x
i
из у, и соответствующий этому слагаемому подграф M
j
содержит М.
Следует заметить, что непосредственное раскрытие всех
скобок в П
L
дало бы 2
m(L)
слагаемых, что практически обесценило
бы алгоритм. Однако положение спасает то, что закон поглоще-
ния можно применять задолго до полного раскрытия.
Рассмотрим пример для графа на рисунке 2.5.4.
Чтобы не выписывать матрицы А и А
х
, заметим, что произ-
ведение П
L
можно представить в виде
П
L
=П(x
i
+ x
j
)
{x
i
x
j
∼
/J
L
x
i
x
j
};{ij/x
i
x
j
~
∈U},
где умножение идет по всем неупорядоченным парам смежных
вершин графа. В нашем случае
П
L
=(x
1
+x
2
)(x
1
+x
8
)(x
2
+x
3
)(x
2
+x
4
)(x
2
+x
5
)(x
3
+x
4
)(x
4
+x
5
)(x
4
+x
6
)
×
×(x
4
+x
7
)(x
4
+x
8
)(x
4
+x
9
)(x
5
+x
6
)(x
6
+x
7
)(x
8
+x
9
).
Полное раскрытие дает 2
14
слагаемых. Однако, замечая, что
в силу закона поглощения всегда
(a+b)(a+c)...(a+p)=a+bc...p,
можно записать
11
10
9
7
3
2
4
1
х1
х3
х2
х8
х9
х5
х7
х6
5
6
13
12
8
х4
Рис. 2.5.4
59
П
L
=(x
1
+x
2
x
8
)(x
2
+x
3
x
4
x
5
)(x
3
+x
4
)(x
4
+x
5
x
6
x
7
x
8
x
9
)(x
5
+x
6
)(x
6
+x
7
)(x
8
+x
9
)=
=(x
1
+x
2
x
8
)(x
2
+x
3
x
4
x
5
)(x
4
+x
3
x
5
x
6
x
7
x
8
x
9
)(x
6
+x
5
x
7
)(x
8
+x
9
).
Получить итоговую запись можно следующим образом: для
i =1,2... последовательно составляем сомножители вида x
i
+x
j
, x
k
,
..., x
p
, где x
j
,x
k
,..,x
p
все вершины смежные с x
i
и обладающие
большими номерами; после этого каждую пару сомножителей
вида (a+b)(a+c) заменяем сомножителем a+bc.
В полученном выражении для П
L
произведение первых двух
скобок равно
(x
1
+x
2
x
8
)(x
2
+x
3
x
4
x
5
)=x
1
x
2
+x
1
x
3
x
4
x
5
+x
2
x
8
+x
2
x
3
x
4
x
5
x
8
=
=x
1
x
2
+x
1
x
3
x
4
x
5
+x
2
x
8
.
Умножение на третью скобку дает
x
1
x
2
x
4
+x
1
x
2
x
3
x
5
x
6
x
7
x
8
x
9
+x
1
x
3
x
4
x
5
+x
1
x
3
x
4
x
5
x
6
x
7
x
8
x
9
+
+x
2
x
4
x
8
+x
2
x
3
x
4
x
5
x
7
x
6
x
8
x
9
=x
1
x
2
x
4
+x
1
x
3
x
4
x
5
+x
2
x
4
x
8
+x
2
x
3
x
5
x
6
x
7
x
8
x
9
.
Продолжая этот процесс, получим в итоге:
∑
L
=x
1
x
3
x
4
x
5
x
6
x
8
+x
2
x
3
x
3
x
6
x
7
x
8
x
9
+x
2
x
4
x
6
x
8
+x
1
x
3
x
4
x
5
x
7
x
8
+x
2
x
4
x
5
x
7
x
8
+
+x
1
x
3
x
4
x
5
x
6
x
9
+x
1
x
2
x
4
x
5
x
7
x
9
.
Максимально пустые подграфы графа L порождаются сле-
дующими подмножествами вершин:
{x
2
,x
7
,x
9
},{x
1
,x
4
},{x
1
,x
3
,x
6
,x
9
},{x
2
,x
6
,x
9
},{x
1
,x
3
,x
6
,x
9
},
{x
2
,x
7
,x
8
},{x
3
,x
5
,x
7
,x
8
},{x
2
,x
6
,x
8
},{x
3
,x
6
,x
8
}.
Максимально полные подграфы, т.е. такие полные, которые
не содержатся в больших полных подграфах, можно находить
аналогичным образом, с той лишь разницей, что вместо П
L
рас-
сматривать
}
(
/
~
,
~
{
),
(
)
,...,
,
(
2
1
j
i
j
i
n
L
L
x
x
J
jl
i
j
i
x
x
x
x
x
¬
≠
+
Π
=
Π
=
Π
,
распространенное на всевозможные пары несмежных различных
вершин.
Для графа на рисунке 2.5.4 максимальные полные подграфы
порождаются множествами вершин:
{x
4
,x
8
,x
9
},{x
4
,x
6
,x
7
},{x
4
,x
5
,x
6
},{x
2
,x
4
,x
5
},{x
2
,x
3
,x
4
},{x
1
,x
8
},{x
1
,x
2
}.
60
3
СВЯЗНОСТЬ
ГРАФОВ
3.1
Маршруты
,
цепи
и
циклы
Рассматриванию подлежат такие свойства графов, которые
не меняются при произвольной ориентации звеньев графа, пере-
ориентации или дезориентации дуг. Поэтому можно рассматри-
вать только неорграфы либо изучать только такие свойства гра-
фов общего вида L=(x,u,p), которые полностью определяются в
терминах полуинцидентора
P
~
.
P
~
(xuy)=P(xuy)VP(yux).
Конечная последовательность
x
0
u
1
x
1
u
2
x
2
...x
l–1
u
l
x
l
*/
l>=0 элементов графа L, для которой истинно высказывание
P
~
(x
0
u
1
x
1
)&
P
~
(x
1
u
2
x
2
)&...&(
P
~
(x
l–1
u
l
x
l
),
называется
маршрутом из вершины x
0
в вершину x
l
или маршру-
том, соединяющим x
0
c x
l
; в случае x
0
=x
l
имеем циклический
маршрут при вершине x
0
. Число носит название длины маршрута.
Маршрут
− это не просто часть графа, так как порядок его
обхода играет существенную роль.
Пусть на полукольцо К наложены соотношения
ξη=ηξ=ζ=θ
2
=1.
Рассмотрим l-ю степень матрицы смежности R графа L
R
l
=||r
(l)
ij
||.
Ее элемент r
(l)
ij
равен количеству различных маршрутов дли-
ны l из вершины с номером i в вершину j.
Это утверждение тривиально при l=1 и легко доказывается в
общем случае индукцией по l: если уже известно, что r
(l)
ik
равно
количеству различных маршрутов длины l из i-ой вершины в j-ю
с фиксированной предпоследней k-ой вершиной, получаем выра-
жение r
(l)
ik
, r
kj
, а для количества таких маршрутов, но без фикса-
ции предпоследней вершины имеем следующее выражение:
∑
+
+
⋅
=
n
k
kj
l
ik
l
ij
r
r
r
1
)
(
)
1
(
.
Интересуясь только достижимостью j-ой вершины из i-ой за
l шагов, можно к определяющим соотношениям в полукольце К