ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 894
Скачиваний: 9
96
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
Äîêàçàòåëüñòâî. Ïóñòü â ãðàôå
G
ñâÿçíàÿ êîìïîíåíòà
G
i
èìååò
n
i
âåð-
øèí. Òîãäà ìàêñèìàëüíîå ÷èñëî ðåáåð â
G
ðàâíî
N
=
1
2
k
P
i
=1
n
i
(
n
i
−
1)
. Ýòî
÷èñëî äîñòèãàåòñÿ, êîãäà êàæäûé èç ãðàôîâ
G
i
ïîëíûé è èìååò
n
i
âåðøèí.
Äîïóñòèì, ÷òî ñðåäè ãðàôîâ
G
i
íàéäóòñÿ õîòÿ áû äâà, êîòîðûå èìåþò áî-
ëåå îäíîé âåðøèíû, íàïðèìåð
n
2
≥
n
1
>
1
. Ïîñòðîèì âìåñòî
G
äðóãîé
ãðàô
G
0
ñ òåì æå ÷èñëîì âåðøèí è êîìïîíåíò, çàìåíÿÿ
G
1
è
G
2
ïîëíûìè
ãðàôàìè
G
0
1
è
G
0
2
ñîîòâåòñòâåííî ñ
n
1
−
1
è
n
2
+1
âåðøèíàìè. Ëåãêî âèäåòü,
÷òî ýòî óâåëè÷èò ÷èñëî ðåáåð. Òàêèì îáðàçîì ìàêñèìàëüíîå ÷èñëî ðåáåð
äîëæåí èìåòü ãðàô, ñîñòîÿùèé èç
k
−
1
èçîëèðîâàííûõ âåðøèí è îäíîãî
ïîëíîãî ãðàôà ñ
n
−
k
+ 1
âåðøèíàìè.
Èç òåîðåìû 3.3 ñëåäóåò äëÿ ñëó÷àÿ k = 2 ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 3.4. Ïðîñòîé íåîðèåíòèðîâàííûé ãðàô ñ
n
âåðøèíàìè è ñ ÷èñ-
ëîì ðåáåð, áîëüøèì, ÷åì
N
(
n,
2) =
1
2
(
n
−
1)(
n
−
2)
ñâÿçåí.
3.6 Äåðåâüÿ
Îïðåäåëåíèå. Ñâÿçíûé íåîðèåíòèðîâàííûé ãðàô íàçûâàåòñÿ äåðåâîì, åñ-
ëè îí íå èìååò öèêëîâ.
 ÷àñòíîñòè, äåðåâî íå èìååò ïåòåëü è êðàòíûõ ðåáåð. Ãðàô áåç öèê-
ëîâ åñòü ãðàô, ñâÿçíûå êîìïîíåíòû êîòîðîãî ÿâëÿþòñÿ äåðåâüÿìè; èíîãäà
òàêîé ãðàô íàçûâàåòñÿ ëåñîì. Ëþáàÿ ÷àñòü òàêîãî ãðàôà òàêæå áóäåò ãðà-
ôîì áåç öèêëîâ.
Òåîðåìà 3.5. Â äåðåâå ëþáûå äâå âåðøèíû ñâÿçàíû åäèíñòâåííûì ïðî-
ñòûì ïóòåì.
Äîêàçàòåëüñòâî. Ëþáîé ïóòü â ãðàôå áåç öèêëîâ ÿâëÿåòñÿ ïðîñòûì. Åñëè
áû áûëî äâà ñâÿçûâàþùèõ âåðøèíû ïðîñòûõ ïóòè, òî áûë áû è öèêë â
äåðåâå, ÷òî íåâîçìîæíî.
Íàãëÿäíîå ïðåäñòàâëåíèå äëÿ ïðîèçâîëüíîãî äåðåâà
T
=
< V, E >
ìîæ-
íî ïîëó÷èòü ïðè ïîìîùè ñëåäóþùåé êîíñòðóêöèè.
3.6. ÄÅÐÅÂÜß
97
Âûáåðåì ïðîèçâîëüíóþ âåðøèíó
a
0
è áóäåì ðàññìàòðèâàòü åå êàê êî-
ðåíü äåðåâà èëè âåðøèíó íóëåâîãî óðîâíÿ.
U
0
=
{
a
0
}
.
Îò
a
0
ïðîâåäåì âñå ðåáðà ê âåðøèíàì, íàõîäÿùèìñÿ íà ðàññòîÿíèè 1 îò
âåðøèíû
a
0
. Âåðøèíû, ñìåæíûå ñ
a
0
ñîñòàâÿò ìíîæåñòâî âåðøèí ïåðâîãî
óðîâíÿ:
U
1
=
{
a
(1)
i
|{
a
0
, a
(1)
i
} ∈
E
}
.
Îò ýòèõ âåðøèí ïåðâîãî óðîâíÿ ïðîâåäåì âñå ðåáðà ê ñìåæíûì ñ íèìè
âåðøèíàì, íàõîäÿùèìñÿ íà ðàññòîÿíèè 2 îò
a
0
, çà èñêëþ÷åíèåì ðåáåð, èí-
öèäåíòíûõ âåðøèíàì ïåðâîãî óðîâíÿ. Ïîëó÷èì ìíîæåñòâî âåðøèí âòîðîãî
óðîâíÿ
U
2
=
{
a
(2)
j
|{
a
(1)
i
, a
(2)
j
} ∈
E, a
(1)
i
∈
U
1
, a
(2)
j
/
∈
U
1
}
Èç âåðøèíû
a
(
n
)
i
íàõîäÿùåéñÿ íà ðàññòîÿíèè
n
îò
a
0
, âûõîäèò îäíî ðåá-
ðî ê åäèíñòâåííîé ïðåäøåñòâóþùåé âåðøèíå
a
(
n
−
1)
k
, à òàêæå íåêîòîðîå
ñåìåéñòâî ðåáåð ê âåðøèíàì
a
(
n
+1)
j
, íàõîäÿùèìñÿ íà ðàññòîÿíèè
n
+ 1
.
U
n
=
{
a
(
n
)
|{
a
(
n
−
1)
, a
(
n
)
} ∈
E, a
(
n
)
/
∈
U
n
−
1
}
.
Íè äëÿ êàêîé èç ýòèõ âåðøèí
a
(
n
)
íå ìîæåò áûòü ðåáåð, ñîåäèíÿþùèõ åå
ñ âåðøèíàìè ñ òåì æå èëè ìåíüøèì ðàññòîÿíèåì, êðîìå
{
a
(
n
−
1)
, a
(
n
)
}
.
Òàêèì îáðàçîì, äåðåâî ìîæåò áûòü ïðåäñòàâëåíî â ñëåäóþùåé ôîðìå:
Áóäåì íàçûâàòü âåðøèíó
a
äåðåâà êîíöåâîé, åñëè
ρ
(
a
) = 1
.
Áóäåì íàçûâàòü ðåáðî êîíöåâûì, åñëè õîòÿ áû îäíà èíöèäåíòíàÿ åìó
âåðøèíà ÿâëÿåòñÿ êîíöåâîé.
Óòâåðæäåíèå 3.6. Ëþáîå íåòðèâèàëüíîå êîíå÷íîå äåðåâî èìååò õîòÿ
áû äâå êîíöåâûå âåðøèíû è õîòÿ áû îäíî êîíöåâîå ðåáðî.
98
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
Äîêàçàòåëüñòâî ñîâåðøåííî ïðîñòî ìîæåò áûòü ïðîâåäåíî, íàïðèìåð,
èíäóêöèåé ïî ÷èñëó âåðøèí.
Óòâåðæäåíèå 3.7. Êàæäîå äåðåâî ñ
n
âåðøèíàìè èìååò
n
−
1
ðåáðî.
Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ëåãêî ïðîâîäèòñÿ èíäóêöèåé ïî ÷èñëó
âåðøèí. Äëÿ
n
= 1
óòâåðæäåíèå, î÷åâèäíî, ñïðàâåäëèâî. Ïóñòü
n >
1
. Òî-
ãäà â äåðåâå ñóùåñòâóåò êîíöåâàÿ âåðøèíà
v
. Óäàëÿÿ èç äåðåâà
v
è ðåáðî
(
u, v
)
, èíöèäåíòíîå
v
, ïîëó÷èì äåðåâî ñ
n
−
1
âåðøèíîé, êîòîðîå â ñèëó
èíäóêòèâíîãî ïðåäïîëîæåíèÿ èìååò
n
−
2
ðåáðà. Ñëåäîâàòåëüíî, ïåðâîíà-
÷àëüíîå äåðåâî èìååò
n
−
2 + 1 =
n
−
1
ðåáðî.
Îáðàòèìñÿ òåïåðü ê âîïðîñó î ïîäñ÷åòå ÷èñëà äåðåâüåâ, êîòîðûå ìîãóò
áûòü ïîñòðîåíû íà çàäàííîì ìíîæåñòâå âåðøèí. Ïîä÷åðêíåì, ÷òî ðå÷ü
èäåò íå î ïîäñ÷åòå ÷èñëà ðàçëè÷íûõ ïîïàðíî íåèçîìîðôíûõ äåðåâüåâ, à
èìåííî î ÷èñëå äåðåâüåâ, ãðàôû êîòîðûõ ðàçëè÷íû, òî åñòü ðàçëè÷àþòñÿ
õîòÿ áû îäíèì ðåáðîì (ìíîæåñòâî âåðøèí ôèêñèðîâàíî).
Ïðèìåð. Ïóñòü êîëè÷åñòâî âåðøèí
n
ðàâíî 4. Òîãäà íà ýòîì ìíîæåñòâå
âåðøèí ìîãóò áûòü ïîñòðîåíû ñëåäóþùèå ðàçëè÷íûå äåðåâüÿ.
Ïåðâûé êëàññ òàêèõ äåðåâüåâ ñîñòàâëÿþò äåðåâüÿ ñëåäóþùåãî âèäà:
Êîíöåâûå âåðøèíû äëÿ äåðåâüåâ òàêîãî êëàññà ìîãóò áûòü âûáðàíû
4
2
ñïîñîáàìè, ïðè êàæäîì òàêîì âûáîðå ïîðÿäîê âíóòðåííèõ âåðøèí ìîæåò
áûòü âûáðàí äâóìÿ ñïîñîáàìè. Ïîëó÷àåì 12 ðàçëè÷íûõ äåðåâüåâ, ñîñòàâ-
ëÿþùèõ óêàçàííûé êëàññ.
Âòîðîé êëàññ äåðåâüåâ èìååò âèä:
Öåíòðàëüíàÿ âåðøèíà ìîæåò áûòü âûáðàíà 4 ñïîñîáàìè, ÷òî äàåò 4
ðàçëè÷íûõ äåðåâà â ýòîì êëàññå.
Äðóãèõ äåðåâüåâ ñ 4 âåðøèíàìè, îòëè÷íûõ îò óêàçàííûõ â ïåðâîì è
âòîðîì êëàññàõ, íåò. Òàêèì îáðàçîì, ñóùåñòâóåò 16 äåðåâüåâ, èìåþùèõ 4
ôèêñèðîâàííûå âåðøèíû.
Îáðàòèìñÿ òåïåðü ê îáùåìó ðåçóëüòàòó.
3.6. ÄÅÐÅÂÜß
99
Òåîðåìà 3.8. ×èñëî ðàçëè÷íûõ äåðåâüåâ, êîòîðûå ìîæíî ïîñòðîèòü íà
çàäàííîì ìíîæåñòâå
V
, ñîäåðæàùåì
n
âåðøèí, ðàâíî
t
n
=
n
n
−
2
Äîêàçàòåëüñòâî. Îáîçíà÷èì ýëåìåíòû äàííîãî ìíîæåñòâà
V
, ðàñïîëîæåí-
íûå â íåêîòîðîì ôèêñèðîâàííîì ïîðÿäêå, ÷èñëàìè
V
=
{
1
,
2
, . . . , n
}
(3
.
1)
Äëÿ ëþáîãî äåðåâà
T
, îïðåäåëåííîãî íà
V
, ââåäåì íåêîòîðûé ñèìâîë, õà-
ðàêòåðèçóþùèé åãî îäíîçíà÷íî. Â
T
ñóùåñòâóþò êîíöåâûå âåðøèíû. Îáî-
çíà÷èì ÷åðåç
b
1
ïåðâóþ êîíöåâóþ âåðøèíó â ïîñëåäîâàòåëüíîñòè (3.1), à
÷åðåç
e
1
=
{
a
1
, b
1
}
ñîîòâåòñòâóþùåå êîíöåâîå ðåáðî. Óäàëèâ èç
T
ðåáðî
e
1
è âåðøèíó
b
1
, ìû ïîëó÷èì íîâîå äåðåâî
T
1
. Äëÿ
T
1
íàéäåòñÿ ïåðâàÿ â
ñïèñêå (3.1) êîíöåâàÿ âåðøèíà
b
2
ñ ðåáðîì
e
2
=
{
a
2
, b
2
}
. Ýòà ðåäóêöèÿ
ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà ïîñëå óäàëåíèÿ ðåáðà
e
n
−
2
= (
a
n
−
2
, b
n
−
2
)
íå îñòàíåòñÿ åäèíñòâåííîå ðåáðî
e
n
−
1
= (
a
n
−
1
, b
n
−
1
)
, ñîåäèíÿþùåå äâå
îñòàâøèåñÿ âåðøèíû.
Òîãäà ñïèñîê
σ
(
T
) = [
a
1
, a
2
, . . . , a
n
−
2
]
(3
.
2)
îäíîçíà÷íî îïðåäåëÿþòñÿ äåðåâîì
T
è äâóì ðàçëè÷íûì äåðåâüÿì
T
è
T
0
,
î÷åâèäíî, ñîîòâåòñòâóþò ðàçíûå ñèìâîëû òàêîãî âèäà. Êàæäàÿ âåðøèíà
a
i
ïîÿâëÿåòñÿ â (3.2)
ρ
(
a
i
)
1 ðàç.
Äëÿ ÿñíîñòè ïðèâåäåì íåñêîëüêî ïðèìåðîâ äåðåâüåâ è ñîîòâåòñòâóþùèõ
èì ïîñëåäîâàòåëüíîñòåé
σ
(
T
)
.
Ïðèìåðû.
1.
σ
(
T
) = [
n, n, . . . , n
|
{z
}
n
−
2
]
2.
σ
(
T
) = [2
,
3
, . . . , n
−
1]
100
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
3.
σ
(
T
) = [2
,
2
,
3
,
2
,
3]
Íàîáîðîò, êàæäàÿ ïîñëåäîâàòåëüíîñòü (3.2) îïðåäåëÿåò äåðåâî
T
ñ ïîìî-
ùüþ îáðàòíîãî ïîñòðîåíèÿ. Åñëè äàíà ïîñëåäîâàòåëüíîñòü (3.2), òî íà-
õîäèòñÿ ïåðâàÿ âåðøèíà
b
â ñïèñêå (3.1), êîòîðàÿ íå ñîäåðæèòñÿ â (3.2).
Ýòî îïðåäåëÿåò ðåáðî
e
1
=
{
a
1
, b
1
}
. Äàëåå óäàëÿåì âåðøèíû
a
1
èç ïî-
ñëåäîâàòåëüíîñòè (3.2) è
b
1
èç ñïèñêà (3.1) è ïðîäîëæàåì ïîñòðîåíèå äëÿ
îñòàâøèõñÿ ýëåìåíòîâ.
Ïîëó÷àþùèéñÿ â ðåçóëüòàòå ïîñòðîåíèÿ ãðàô ÿâëÿåòñÿ äåðåâîì, ÷òî
ìîæåò áûòü óñòàíîâëåíî, íàïðèìåð, ïî èíäóêöèè. Ïîñëå óäàëåíèÿ
e
1
ïî-
ñëåäîâàòåëüíîñòü (3.2) áóäåò ñîäåðæàòü
n
−
3
ýëåìåíòà. Åñëè îíà ñîîòâåò-
ñòâóåò äåðåâó
T
1
, òî ãðàô
T
, ïîëó÷àåìûé èç íåãî äîáàâëåíèåì
e
1
, òàêæå
åñòü äåðåâî, òàê êàê âåðøèíà
b
1
íå ïðèíàäëåæèò
T
1
.
B (3.2) êàæäàÿ âåðøèíà ìîæåò ïðèíèìàòü âñå
n
âîçìîæíûõ çíà÷åíèé.
Âñå îíè ñîîòâåòñòâóþò ðàçëè÷íûì äåðåâüÿì, îòêóäà è ïîëó÷àåòñÿ ôîðìóëà
t
n
=
n
n
−
2
.
3.6.1 Îñòîâíîå äåðåâî (êàðêàñ)
Îïðåäåëåíèå. Äëÿ ñâÿçíîãî íåîðèåíòèðîâàííîãî ãðàôà
G
=
< V, E >
áåç
ïåòåëü êàæäîå äåðåâî
< V, T >
, ñîäåðæàùåå âñå âåðøèíû ãðàôà
G
, ãäå
T
⊆
E
, áóäåì íàçûâàòü îñòîâíûì äåðåâîì (êàðêàñîì) ãðàôà
G
.
Íàïîìíèì, ÷òî äëèíà ïóòè åñòü êîëè÷åñòâî ñîñòàâëÿþùèõ åãî ðåáåð.
Ïðîöåäóðû ïîèñêà â ãëóáèíó è â øèðèíó ìîæíî ïðîñòûì ñïîñîáîì èñ-
ïîëüçîâàòü äëÿ íàõîæäåíèÿ îñòîâíûõ äåðåâüåâ.  îáîèõ ñëó÷àÿõ äîñòèæå-
íèå íîâîé âåðøèíû
u
èç âåðøèíû
v
âûçûâàåò âêëþ÷åíèå â äåðåâî ðåáðà
(
v, u
)
.
Ïðèâåäåì àëãîðèòì ïîñòðîåíèÿ îñòîâíîãî äåðåâà ìåòîäîì ïîèñêà â ãëó-
áèíó.
Àëãîðèòì ïîñòðîåíèÿ îñòîâíîãî äåðåâà ìåòîäîì ïîèñêà â ãëó-
áèíó.
Âõîäíûå äàííûå: ñâÿçíûé ãðàô
G
=
< V, E >
, çàäàííûé ñïèñêàìè èí-
öèäåíòíîñòè ÇÀÏÈÑÜ
[
v
]
,
v
∈
V
.
Ðåçóëüòàò: êàðêàñ
< V, T >
ãðàôà
G
.