Файл: Журавлев Флеров Дискретный анализ МФТИ 1991.pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.03.2021

Просмотров: 894

Скачиваний: 9

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

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 >

ìîæ-

íî ïîëó÷èòü ïðè ïîìîùè ñëåäóþùåé êîíñòðóêöèè.


background image

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. Ëþáîå íåòðèâèàëüíîå êîíå÷íîå äåðåâî èìååò õîòÿ

áû äâå êîíöåâûå âåðøèíû è õîòÿ áû îäíî êîíöåâîå ðåáðî.


background image

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

ôèêñèðîâàííûå âåðøèíû.

Îáðàòèìñÿ òåïåðü ê îáùåìó ðåçóëüòàòó.


background image

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]


background image

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

.


Смотрите также файлы