Составители:
Рубрика:
73
åñëè v
j
∉Ãv
i
(ò. å. âåðøèíû íåñìåæíûå), òî α
ij
=0,
÷òî ñîîòâåòñòâóåò ìàòðèöå ñìåæíîñòè.
Äëÿ ëþáîé ïàðû âåðøèí v
i
è v
j
(ñ ó÷åòîì S∩ÃS=∅) ñïðàâåäëèâî óò-
âåðæäåíèå :
(i≠j ; v
i
∈Ãv
j
èëè v
j
∈Ãv
i
) ⇒ (v
i
∉S èëè v
j
∉S),
(çäåñü èëè îçíà÷àåò îïåðàöèþ íåèñêëþ÷àþùåå èëè), ò. å. òîëüêî
îäèí èç êîíöîâ äóãè ìîæåò âõîäèòü â S, ëèáî îáà íå âõîäÿò. Ýòî ìîæíî
çàïèñàòü òàê äëÿ âåðøèí, íå âõîäÿùèõ â S (ïðè i≠j):
()
()
1,
èëè 1.
ij ji i j
ij ji i j
x
õ
x
õ
α∨α ∨ ∨ =
αα ∨ ∨ =
Âûïîëíèâ áóëåâî óìíîæåíèå ïî âñåì âåðøèíàì ãðàôà, ïðèõîäèì ê
óðàâíåíèþ
()
Ô1,
Sijjiij
iji
x
õ
≠
=αα∨∨=
∏∏
çäåñü ∨ çíàê äèçúþíêöèè;
∏
çíàê áóëåâà óìíîæåíèÿ (êàæäûé ÷ëåí
ó÷èòûâàåòñÿ îäèí ðàç).
Èìåÿ â âèäó, ÷òî S ∩ Ã
1
S = ∅, ò. å. ìíîæåñòâî âåðøèí èç âíóòðåííå
óñòîé÷èâîãî ïîäìíîæåñòâà è âíå åãî íå ïåðåñåêàþòñÿ, ìîæíî óïðîñ-
òèòü ýòî óðàâíåíèå, çàìåíèâ âûðàæåíèå
ij ji
αα
íà
ij
α
()
()
Ô1,
èëè Ô 1.
Sijij
iji
Si ijj
iji
x
õ
x
õ
≠
≠
=α∨∨=
=∨α∨=
∏∏
∏∏
(4.1)
Äëÿ äàëüíåéøåãî óïðîùåíèÿ óðàâíåíèÿ íåîáõîäèìî ðàñêðûòü ñêîá-
êè è ïðèâåñòè ïîäîáíûå ÷ëåíû ñ ó÷åòîì îïåðàöèè ïîãëîùåíèÿ : x∨x⋅y=x
è îïåðàöèè ïðèâåäåíèÿ ïîäîáíûõ ÷ëåíîâ x⋅x=x.
 ðåçóëüòàòå óïðîùåíèÿ ïîëó÷èì, ÷òî äëÿ êàæäîãî ÷ëåíà óðàâíåíèÿ
Ô
S
ñîâîêóïíîñòü âñåõ âåðøèí, ñîîòâåòñòâóþùèõ ïåðåìåííûì, íå ïðåä-
ñòàâëåííûì â íåì, îáðàçóåò ìàêñèìàëüíîå âíóòðåííå óñòîé÷èâîå ïîä-
ìíîæåñòâî ãðàôà.
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
