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

2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ

81

Îïðåäåëåíèå. Ñèñòåìà ôóíêöèé

{

f

1

, f

2

, . . . , f

n

, . . .

}

èç çàìêíóòî-

ãî êëàññà

K

íàçûâàåòñÿ åãî áàçèñîì , åñëè îíà ïîëíà â

K

, íî âñÿêàÿ åå

ñîáñòâåííàÿ ïîäñèñòåìà íå ÿâëÿåòñÿ ïîëíîé â

K

.

Òàê, ñèñòåìà

f

1

=

x

1

x

2

, f

2

= 0

, f

3

= 1

, f

4

=

x

1

+

x

2

ÿâëÿåòñÿ áàçèñîì â

P

2

. Ìîæíî ïîêàçàòü, ÷òî ñèñòåìà ôóíêöèé

{

0

,

1

, x

1

x

2

, x

1

∨

x

2

}

ÿâëÿåòñÿ

áàçèñîì äëÿ êëàññà

M

ìîíîòîííûõ ôóíêöèé.

Òåîðåìà 2.12. Êàæäûé çàìêíóòûé êëàññ èç

P

2

èìååò êîíå÷íûé áàçèñ.

Òåîðåìà 2.13. Ìîùíîñòü ìíîæåñòâà çàìêíóòûõ êëàññîâ â

P

2

ñ÷åòíàÿ.

Õîòÿ âòîðàÿ èç ïðèâåäåííûõ òåîðåì ëîãè÷åñêè âûòåêàåò èç ïåðâîé, îä-

íàêî â äîêàçàòåëüñòâàõ Ïîñòà ñíà÷àëà óñòàíàâëèâàåòñÿ âòîðîé ôàêò, à çà-

òåì  ïåðâûé.

82

ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ

Ãëàâà 3

Ýëåìåíòû òåîðèè ãðàôîâ

Íà÷àëî òåîðèè ãðàôîâ êàê ìàòåìàòè÷åñêîé äèñöèïëèíå áûëî ïîëîæåíî

Ýéëåðîì â åãî çíàìåíèòîì ðàññóæäåíèè î Ê¼íèãñáåðãñêèõ ìîñòàõ. Îäíàêî

ýòà ñòàòüÿ Ýéëåðà 1736 ãîäà áûëà åäèíñòâåííîé íà ýòó òåìó â òå÷åíèå ïî-

÷òè ñòà ëåò. Åñòåñòâåííûå íàóêè îêàçàëè ñâîå âëèÿíèå íà ðàçâèòèå òåîðèè

ãðàôîâ áëàãîäàðÿ èññëåäîâàíèÿì ýëåêòðè÷åñêèõ ñåòåé, ìîäåëåé êðèñòàë-

ëîâ è ñòðóêòóð ìîëåêóë. Ðàçâèòèå ôîðìàëüíîé ëîãèêè ïðèâåëî ê èçó÷åíèþ

áèíàðíûõ îòíîøåíèé â ôîðìå ãðàôîâ. Áîëüøîå ÷èñëî ïîïóëÿðíûõ ãîëî-

âîëîìîê ïîääàâàëîñü ôîðìóëèðîâêå íåïîñðåäñòâåííî â òåðìèíàõ ãðàôîâ,

è ýòî ïðèâîäèëî ê ïîíèìàíèþ, ÷òî ìíîãèå çàäà÷è òàêîãî ðîäà ñîäåðæàò

íåêîòîðîå ìàòåìàòè÷åñêîå ÿäðî, âàæíîñòü êîòîðîãî âûõîäèò çà ðàìêè êîí-

êðåòíîãî âîïðîñà. Íàèáîëåå çíàìåíèòàÿ èç ýòèõ çàäà÷  ïðîáëåìà ÷åòû-

ðåõ êðàñîê, âïåðâûå ïîñòàâëåííàÿ ïåðåä ìàòåìàòèêàìè Äå Ìîðãàíîì îêî-

ëî 1850 ã. Íèêàêàÿ äðóãàÿ ïðîáëåìà íå âûçûâàëà ñòîëü ìíîãî÷èñëåííûõ è

îñòðîóìíûõ ðàáîò â îáëàñòè òåîðèè ãðàôîâ. Áëàãîäàðÿ ñâîåé ïðîñòîé ôîð-

ìóëèðîâêå è ðàçäðàæàþùåé íåóëîâèìîñòè îíà äî 1973 ã. îñòàâàëàñü ìîù-

íûì ñòèìóëîì èññëåäîâàíèé ðàçëè÷íûõ ñâîéñòâ ãðàôîâ (ïðåäëîæåííîå â

1973 ãîäó ïîëîæèòåëüíîå ðåøåíèå ýòîé ïðîáëåìû äî ñèõ ïîð îñïàðèâàåòñÿ

íåêîòîðûìè ìàòåìàòèêàìè).

Íàñòîÿùåå ñòîëåòèå áûëî ñâèäåòåëåì íåóêëîííîãî ðàçâèòèÿ òåîðèè ãðà-

ôîâ, êîòîðàÿ çà ïîñëåäíèå äâàäöàòü ëåò âñòóïèëà â íîâûé ïåðèîä èíòåí-

ñèâíûõ ðàçðàáîòîê. Â ýòîì ïðîöåññå ÿâíî çàìåòíî âëèÿíèå çàïðîñîâ íî-

âûõ îáëàñòåé ïðèëîæåíèé: òåîðèè èãð, ïðîãðàììèðîâàíèÿ, îïòèìèçàöèè,

òåîðèè ïåðåäà÷è ñîîáùåíèé, ýëåêòðè÷åñêèõ è êîíòàêòíûõ ñåòåé, à òàêæå

ïðîáëåì áèîëîãèè è ïñèõîëîãèè.

83

84

ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ

Ïðåäìåòîì ïåðâûõ çàäà÷ â òåîðèè ãðàôîâ áûëè êîíôèãóðàöèè, ñîñòîÿ-

ùèå èç òî÷åê è ñîåäèíÿþùèõ èõ ëèíèé. Â ýòèõ ðàññìîòðåíèÿõ áûëî íåñó-

ùåñòâåííî, ïðÿìûå ëè ýòî ëèíèè èëè æå îíè ÿâëÿþòñÿ êðèâîëèíåéíûìè

íåïðåðûâíûìè äóãàìè, ñîåäèíÿþùèìè êîíöåâûå òî÷êè, ãäå ðàñïîëîæåíû

ýòè ëèíèè, ÿâëÿþòñÿ ëè îíè äëèííûìè èëè êîðîòêèìè. Ñóùåñòâåííî ëèøü

òî, ÷òî îíè ñîåäèíÿþò äâå äàííûå òî÷êè. Ýòî ïðèâîäèò â îïðåäåëåíèþ

ãðàôà êàê àáñòðàêòíîãî ìàòåìàòè÷åñêîãî ïîíÿòèÿ.

Îïðåäåëåíèå. Ãðàô

G

=

< V, E >

åñòü ñîâîêóïíîñòü ìíîæåñòâà âåð-

øèí

V

è ìíîæåñòâà ðåáåð (äóã)

E

, ïðè÷åì

E

⊆

V

×

V

åñòü ìíîæåñòâî

óïîðÿäî÷åííûõ ïàð

< x, y >

äëÿ îðèåíòèðîâàííîãî ãðàôà è

E

⊆ {{

x, y

}

:

(

x, y

∈

V

)

∧

(

x

6

=

y

)

}

äëÿ íåîðèåíòèðîâàííîãî ãðàôà (ïðè ýòîì äëÿ

íåîðèåíòèðîâàííîãî ãðàôà ñ÷èòàåì, ÷òî ðåáðà

{

a, b

}

è

{

b, a

}

ñîâïàäàþò

{

a, b

}

=

{

b, a

}

).

Îïðåäåëåíèå. Ãðàô íåîðèåíòèðîâàííûé, åñëè âñå åãî ðåáðà íå îðèåí-

òèðîâàíû, è ãðàô îðèåíòèðîâàííûé, åñëè âñå åãî ðåáðà îðèåíòèðîâàíû.

Ðåáðî îðèåíòèðîâàííîãî ãðàôà ìû îáîçíà÷àåì ñèìâîëîì

< x, y >

; ðåá-

ðî íåîðèåíòèðîâàííîãî ãðàôà îáîçíà÷àåòñÿ ñèìâîëîì

{

x, y

}

. Â ñëó÷àå,

êîãäà íåñóùåñòâåííî, î êàêîì ðåáðå èäåò ðå÷ü, èëè êîãäà ýòî ÿñíî èç êîí-

òåêñòà, áóäåì ïðîèçâîëüíîå ðåáðî ãðàôà îáîçíà÷àòü ñèìâîëîì

(

x, y

)

.

 ïðèëîæåíèÿõ ãðàô îáû÷íî èíòåðïðåòèðóåòñÿ êàê ñîâîêóïíîñòü òî÷åê

V

, â êîòîðîé òî÷êè

x

è

y

ñîåäèíåíû äóãîé ñî ñòðåëêîé åñëè

< x, y >

∈

E

è

äóãîé áåç ñòðåëêè åñëè

{

x, y

} ∈

E

. Â ñëó÷àå îðèåíòèðîâàííîãî ãðàôà äëÿ

ðåáðà

< x, y >

âåðøèíà

x

 íà÷àëüíàÿ âåðøèíà,

y

 êîíå÷íàÿ âåðøèíà

ðåáðà. Ìîæíî òàêæå ãîâîðèòü, ÷òî

e

=

< x, y >

åñòü ðåáðî, âûõîäÿùåå èç

âåðøèíû

x

(èñõîäÿùåå èç âåðøèíû

x

) è âõîäÿùåå â âåðøèíó

y

. Êàê â ñëó-

÷àå îðèåíòèðîâàííîãî, òàê è â ñëó÷àå íåîðèåíòèðîâàííîãî ðåáðà ãîâîðÿò,

÷òî ðåáðî

e

èíöèäåíòíî âåðøèíàì

x

è

y

, à òàê æå, ÷òî

x

è

y

èíöèäåíò-

íû ðåáðó

e

. Ãîâîðÿò, ÷òî äâå âåðøèíû

x

è

y

ãðàôà ñìåæíû, åñëè

(

x, y

)

ÿâëÿåòñÿ ðåáðîì. Äâà ðåáðà ñìåæíû, åñëè îíè èìåþò îáùóþ âåðøèíó.

Ïðè ôàêòè÷åñêîì èçîáðàæåíèè ãðàôà èìååòñÿ áîëüøàÿ ñâîáîäà â ðàç-

ìåùåíèè âåðøèí è â âûáîðå ôîðìû ñîåäèíÿþùèõ èõ äóã. Ïîýòîìó ìîæåò

îêàçàòüñÿ, ÷òî îäèí è òîò æå ãðàô ïðåäñòàâëÿåòñÿ ñîâåðøåííî ðàçëè÷íûìè

÷åðòåæàìè.

Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî äâà ãðàôà

G

=

< V, E >

è

G

◦

=

< V

◦

, E

◦

>

èçîìîðôíû, åñëè ñóùåñòâóåò òàêîå âçàèìíî-îäíîçíà÷íîå

ñîîòâåòñòâèå ìåæäó ìíîæåñòâàìè èõ âåðøèí

V

è

V

◦

, ÷òî âåðøèíû ñîåäè-

íåíû ðåáðàìè â îäíîì ãðàôå òîãäà è òîëüêî òîãäà, êîãäà ñîîòâåòñòâóþùèå

èì âåðøèíû ñîåäèíåíû â äðóãîì ãðàôå.

3.1. ÑÒÅÏÅÍÈ ÂÅÐØÈÍ

85

Òàêèì îáðàçîì, åñëè

V

⇔

V

0

è ïðè ýòîì ñîîòâåòñòâèè

x

⇔

x

0

,

y

⇔

y

0

,

òî

(

x, y

)

∈

E

òîãäà è òîëüêî òîãäà, êîãäà

(

x

0

, y

0

)

∈

E

0

;

((

x, y

)

∈

E

⇔

(

x

0

, y

0

)

∈

E

0

)

.

Çàäà÷à.

Äîêàçàòü, ÷òî ãðàôû, èçîáðàæåííûå íà ñëåäóþùåì ðèñóíêå 3.1, èçî-

ìîðôíû.

Ðèñ. 3.1

Âåðøèíà, íå èíöèäåíòíàÿ íèêàêîìó ðåáðó, íàçûâàåòñÿ èçîëèðîâàííîé.

Ïðè îïðåäåëåíèè ìíîæåñòâà âåðøèí

V

äàííîãî ãðàôà ÷àñòî èìååò ñìûñë

ó÷èòûâàòü òîëüêî íåèçîëèðîâàííûå âåðøèíû.

Âàæíûì ñëó÷àåì ÿâëÿåòñÿ íåîðèåíòèðîâàííûé ïîëíûé ãðàô

U

=

U

(

V

)

,

ðåáðàìè êîòîðîãî ÿâëÿþòñÿ âñåâîçìîæíûå ïàðû

{

x, y

}

äëÿ âñåõ ðàçëè÷-

íûõ âåðøèí

x

è

y

èç

V

. Â îðèåíòèðîâàííîì ïîëíîì ãðàôå

U

(

d

)

(

V

)

èìåþòñÿ

ïàðû ðåáåð

< x, y >

è

< y, x >

äëÿ âñåõ ðàçëè÷íûõ âåðøèí

x, y

∈

V

.

Ñôîðìóëèðîâàííîå îïðåäåëåíèå ãðàôà, âìåñòå ñ ñîîòâåòñòâóþùèì èçîá-

ðàæåíèåì, äîñòàòî÷íî äëÿ ìíîãèõ çàäà÷. Îäíàêî, äëÿ íåêîòîðûõ öåëåé

æåëàòåëüíî ïîíÿòèå ãðàôà íåñêîëüêî ðàñøèðèòü.

1. Ìîæíî äîïóñêàòü ð¼áðà, ó êîòîðûõ îáå âåðøèíû ñîâïàäàþò

l

= (

x, x

)

.

Òàêîå ðåáðî íàçûâàåòñÿ ïåòëåé.

U

0

 ïîëíûé ãðàô ñ ïåòëÿìè.

2. Ïàðà âåðøèí ìîæåò ñîåäèíÿòüñÿ íåñêîëüêèìè ðåáðàìè

e

i

= (

x, y

)

i

,

â ÷àñòíîñòè âåðøèíû

x

è

y

ìîãóò ñîåäèíÿòüñÿ íåñêîëüêèìè ðåáðàìè

â êàæäîì íàïðàâëåíèè.

3.1 Ñòåïåíè âåðøèí

Ãðàô íàçûâàåòñÿ êîíå÷íûì, åñëè ÷èñëî åãî ðåáåð êîíå÷íî. Ïðè òàêîì îïðå-

äåëåíèè êîíå÷íûé ãðàô ìîæåò èìåòü áåñêîíå÷íîå ÷èñëî âåðøèí, íî âñå

îíè, êðîìå êîíå÷íîãî ÷èñëà, èçîëèðîâàííûå.