GRAFU‘ TEORIJA
”RINKTINIAI MATEMATIKOS SKYRIAI”
(Informatikos spec., 2 srautas, magistrantūra, 1 semestras)

PROGRAMA
1. Pagrindinės sa‘vokos, pavyzdžiai. Grafu‘ veiksmai.
2. Grafo parametru‘ sa‘ryšiai.
3. Jungiantysis medis. Ekonomiško medžio algoritmas.
4. Cayley’io teorema.
5. Binariu‘ju‘ medžiu‘ kiekis.
6. Grafu‘ ir jungiu‘ grafu‘ su skaidžia savybe skaičiu‘ sa‘ryšis.
7. Grafo gretimumo ir incidentumo matricos.
8. Grafai ir elektros grandinės.
9. Vektorinės erdvės, asocijuotos su grafais.
10. Maksimaliojo srauto digrafe problema.
11. Maksimalaus srauto ir minimalaus pjūvio teorema.
12. Sveikaskaičio maksimalaus srauto algoritmas.
13. Grafo jungumas. Menger’io teorema.
14. Poravimas. Hall’o teorema.
15. Skirtingi šeimos poaibiu‘ atstovai.
16. Taku‘ ir ciklu‘ ilgiai. Ekstremalieji grafai.
17. Pilnu‘ju‘ pografiu‘ egzistavimas. Ramsey’io teorema.
18. Monochromatiniu‘ pografiu‘ egzistavimas.
19. Grafo viršūniu‘ spalvinimas. Chromatusis polinomas.
20. Grafo briaunu‘ spalvinimo uždaviniai.
21. Stabilieji grafo viršūniu‘ poaibiai.
22. Absorbuojantys poaibiai ir branduoliai.
Literatūra
1. P.Tannenbaumas, R.Arnoldas, Kelionė ‘i šiuolaikine‘ matematika‘ , TEV, Vilnius,
1995.
2. B.Bollobás, Graph Theory, Springer, 1979.
3. B.Bollobás, Modern Graph Theory, Springer, 1998.
4. R.Diestel, Graph Theory, Springer, 1997.
5. R.Wilson, Introduction to Graph Theory, Longman, 1985.
6. L.Volkmann, Fundamente der Graphentheorie. Springer, 1996.
7. C.Berge, Graphs, North-Holland, 1985.
8. V.N.Sačkov, ‘Ivadas ‘i Kombinatorinius Diskrečios Matematikos Metodus, Nauka,
Maskva, 1982 (rusu‘ k.).

1

0. Pratarmė.
Jūs paėmėte i‘ rankas autoriaus ”Grafu‘ teorijos” paskaitu‘, skaitytu‘ 1998 bei 1999
metu‘ rudens semestruose, konspekta‘. Sutelke‘s savo dėmesi‘ i‘ medžiagos atrinkima‘, literatūros paieškas, autorius nesuspėjo atlikti šio teksto kruopštesnės ir kritiškesnės analizės, i‘terpti iliustruojančiu‘ grafu‘ eskizu‘, todėl lieka vienintelė paguoda, kad skaitytojas
atliks ta‘ darba‘ savarankiškai ir pateiks mums savo pastabas. Vienok, manome, kad šis
pirmasis ir palyginti siauras konspektas bus pravartus laikantiems egzamina‘ dar šiemet.
Gilesnėms studijoms gali būti panaudotos pateikiamo sa‘rašo knygos.
1. Pagrindinės sa‘vokos.
Grafas - aibiu‘ pora G = (V, E), čia V - viršūniu‘ aibė, E - viršūniu‘ nesutvarkytu‘ju‘
poru‘ e := (x, y) =: xy = yx, x, y ∈ V arba briaunu‘ (lanku‘) aibė. Kai poros xy laikomos sutvarkytosiomis, G vadinamas digrafu. Viršūnės x ir y vadinamos xy briaunos
galais arba jai incidenčiomis viršūnėmis. Viena kitos atžvilgiu jos yra gretimosios
(kaimyninės) viršūnės. Viršūnės vaizduojamos taškais, briaunos - kreivėmis. Digrafo
atveju papildomai nurodomos ir briaunu‘ kryptys. Kada vietoje briaunu‘ aibės E imamas
briaunu‘ rinkinys (šeima) su galimais pasikartojimais, pora (V, E) vadinama multigrafu.
Ji‘ vaizduojant plokštumoje, dvi viršūnės jungiamos atitinkamu kiekiu briaunu‘. Geometrinis vaizdavimas dažnai yra klaidinantis, nes skirtingi brėžiniai gali atitikti ta‘ pati‘ grafa‘
(žr. 1 pav. dviem būdais pavaizduota‘ grafa‘ K3,3 ).
Grafai G = (V, E) ir G0 = (V 0 , E 0 ) vadinami izomorfiškais, jei egzistuoja bijekcija
φ : V → V 0 tokia, kad kiekvienai briaunai xy ∈ E yra patenkinta sa‘lyga:
xy ∈ E

φ(x)φ(y) ∈ E 0 .

⇐⇒

Multigrafu‘ atveju pastaroji sa‘lyga turi būti patenkinta kiekvienai iš kartotiniu‘ briaunu‘,
o digrafams – atvaizdis φ turi išlaikyti ir briaunos krypti‘.
Nagrinėsime tik baigtinius grafus, t.y. tik poras (V, E) su baigtinėmis aibėmis V ir
E. Šiu‘ aibiu‘ galias žymėkime |V | = n ir |E| = m. Jei nebus pasakyta priešingai, grafas
neturės kilpu‘, t.y. briaunu‘ xx. Kadangi grafas neturi kartotiniu‘ briaunu‘, tai m ≤ Cn2 .
Čia Cnk - binominis koeficientas. Dažnai tokie grafai vadinami paprastaisiais. Skaičius
n vadinams grafo G eile, o m - grafo G didumu. Reikalausime, kad n ≥ 1. Jei m = 0,
grafas G vadinamas tuščiuoju (tradiciškai žymimas E n ), o kai m = Cn2 , - pilnuoju.
Pilname grafe visos viršūnės yra tarpusavyje sujungtos, jis žymimas K n . Viršūnės x
laipsniu (valentingumu) δ(x) laikomas incidenčiu‘ jai briaunu‘ skaičius. Kai δ(x) = 0, x
- izoliuotoji viršūnė. Skaičiai
δ(G) = min{δ(x) : x ∈ G},

∆(G) = max{δ(x) : x ∈ G}

atitinkamai vadinami minimaliuoju bei maksimaliuoju grafo laipsniais. Kai δ(G) =
∆(G) =: k, grafas G vadinamas k reguliariuoju (k-valenčiu). Pvz., kubinis bei Petersen’o grafai (žr. 2 pav.) yra trivalenčiai.
2 pav.
2

Grafas G0 = (V 0 , E 0 ) vadinamas G = (V, E) pografiu, jeigu V 0 ⊂ V ir E 0 ⊂ E.
Jeigu pografio G0 briaunu‘ aibėje E 0 yra visos E briaunos, jungiančios V 0 viršūnes, tai G0
vadinamas V 0 indukuotoju pografiu, ji‘ žymėsime G[V 0 ].
Apibrėšime grafu‘ veiksmu‘. Tarkime, kad G = (V, E) - grafas, x ∈ V 0 ⊂ V ir
xy ∈ E 0 ⊂ E. Tada
G − V 0 := G[V \ V 0 ]
ir
G − E 0 := (V, E \ E 0 ).
Taigi, grafas G − x := G − {x} gaunamas iš G išmetant ne tik viršūne‘ x, bet ir jai
incidenčias briaunas, o G − xy := G − {xy} - išmetant tik briauna‘ xy. Atvirkščiai,
G + xy := G + {xy}, kai xy 6∈ E, būtu‘ naujas grafas su viena papildoma briauna. Kai
kada yra tikslinga, atėmus iš grafo briauna‘ xy, sutapatinti viršūnes x ir y. Ši operacija
vadinama grafo sutraukimu.
Grafas (V ∪ V 0 , E ∪ E 0 ) vadinamas G = (V, E) ir G0 = (V 0 , E 0 ) sa‘junga, žymima
G∪G. Be to, grafu‘ sa‘jungoje viršūniu‘ aibėms dar iškeliamas reikalavimas neturėti bendru‘
elementu‘. Grafu‘ G ir G0 suma G + G0 , kai V ∩ V 0 = ∅, apibrėžiama kaip ju‘ sa‘junga,
papildomai išvedant visas briaunas, jungiančias V viršūnes su V 0 viršūnėmis. Nubrėžkite
grafa‘ G + x, kai x 6∈ V .
Grafa‘ vaizdžiai charakterizuoja i‘vairios ”klajojimo” juo galimybės. Viršūniu‘ ir briaunu‘ seka‘ x0 , e1 , x1 , . . . , ek , xk su ej = xj−1 xj , xj ∈ V , j = 0, . . . , k vadiname keliu
(x0 − xk keliu), o k - jo ilgiu. Kai kelyje visos briaunos yra skirtingos, ji‘ vadiname trasa.
Uždara‘ trasa‘ (kai x0 = xk ir k ≥ 2) vadinsime grandine. Jeigu kelyje (arba trasoje)
visos vidinės viršūnės x1 , . . . , xk−1 yra skirtingos, ji‘ vadiname taku, ir uždara‘ taka‘, kai
k ≥ 2, - ciklu (grandimi). Takus bei ciklus žymėsime pereinamu‘ viršūniu‘ seka, pvz.,
P = x1 x2 x3 ...xk . Akivaizdžia‘ paskutine‘ briauna‘ xk x1 cikle galime ir nenurodyti. Jei grafe
egzistuoja grandinė, sudaryta iš visu‘ jo briaunu‘, tai jis vadinamas Euler’io vardu, o jei
jame yra ciklas, apimantis visas jo viršūnes, tai jis yra Hamilton’o grafas. Šios sa‘vokos
nėra ekvivalenčios. Pateikite pavyzdžiu‘. Savarankiškai perskaitykite P.Tannenbaumo ir
R.Arnoldo ”Kelionės i‘ šiuolaikine‘ matematika‘” skyrius apie Eulerio ir Hamiltono grafus.
Grafas G yra jungusis, jei bet kuria‘ pora‘ viršūniu‘ iš E jungia takas. Jei n ≥ 2, šis
grafas neturi izoliuotu‘ viršūniu‘.
Teorema. Grafas yra jungiu‘ pografiu‘ sa‘ junga.
Irodymas. Dvi viršūnes vadinkime ekvivalenčiomis, jeigu grafe yra jas jungiantis
‘
takas. Tai ekvivalentumo sa‘ryšis viršūniu‘ aibėje V. Ekvivalenčiu‘ viršūniu‘ klasės V1 , . . . , Vs
nesikerta, grafe nėra briaunu‘, jungiančiu‘ skirtingu‘ klasiu‘ viršūnes. Indukuotieji pografiai
G[V1 ], . . . , G[Vs ] ir sudaro ieškomos sa‘jungos pografius.
Teoremoje apibrėžtus pografius vadinsime grafo jungumo komponentėmis. Viršūnė, kurios atėmimas iš grafo keičia komponenčiu‘ skaičiu‘, vadinama iškarpos viršūne,
o briauna, - tiltu. Atstumu d(x, y) tarp viršūniu‘ x ir y vadinsime trumpiausio tako ilgi‘,
jei toks takas egzistuoja. Priešingu atveju, atstuma‘ laikysime begaliniu.
Grafas G = (V, E) vadinamas dvidaliu (bichromačiuoju, dvispalviu), jei V = V 0 ∪
00
V , V 0 ∩ V 00 = ∅, o bet kokia briauna iš E jungia viršūne‘ iš V 0 su viršūne iš V 00 . Dvidalis
grafas neturi nelyginio ilgio grandiniu‘. I‘ sitikinkite, jog ir priešingas teiginys yra teisingas!
3

2. Miškas ir medžiai.
Grafas, neturintis ciklu‘ (beciklis), vadinamas mišku, o jungusis miškas - medžiu.
1 teorema. Grafas yra miškas tada ir tik tada, kada bet kokia‘ viršūniu‘ pora‘ jungia
ne daugiau kaip vienas takas.
Irodymas. Jei grafas nėra miškas, jame egzistuoja ciklas x0 x1 ...xl x0 . Todėl turime
‘
du takus x0 x1 ...xl ir x0 xl .
Atvirkščiai, tarkime, kad P = x0 ...xl ir P 0 = x0 yl ...ys = xl - du takai, jungiantys x0
su xl . Tarkime, kad i + 1 - mažiausias indeksas, su kuriuo xi+1 6= yi+1 , o j ≥ i mažiausias
indeksas su kuriuo yj+1 jau priklauso P , t.y. yj+1 = xk . Tada xi ...xk yj ...yi+1 yra ciklas.
Todėl grafas nėra miškas.
2 teorema. Šie tvirtinimai yra ekvivalentūs:
a) G yra medis;
b) G yra minimalus jungus grafas, t.y. kiekviena jo briauna yra tiltas;
c) G yra maksimalus beciklis grafas, t.y. sujungiant bet kokias neincidenčias viršūnes
sukuriamas ciklas.
Irodymas. Pažymėkime V, E grafo G viršūniu‘ ir briaunu‘ aibes, xy ∈ E - bet kokia‘
jo briauna‘, o u, v - bet kokias dvi neincidenčias viršūnes.
Jei G - medis ir grafas G − xy būtu‘ jungus, tai G turėtu‘ du takus P = xx1 ...xk y ir
P = xy, vadinasi, todėl turėtu‘ cikla‘ P = xx1 ...xk yx. Tad, iš a) išplaukia b).
Jei G - medis, tai jame egzistuoja takas nuo u iki v. Išvestas naujasis takas uv su
senuoju sudarytu‘ cikla‘, ir grafas G + uv jau turėtu‘ cikla‘. Tad, iš a) išplaukia c).
Tarkime, G - minimalus jungus grafas. Jei G nebūtu‘ medis, o turėtu‘ cikla‘ xx1 ...yx,
tai išmetus briauna‘ xy, jo jungumas nepakistu‘. Prieštara i‘rodo, jog iš b) išplaukia a).
Panašiai i‘rodomi ir like‘ teiginiai.
‘

Pasinaudoje‘ b) savybe, apibrėžiame minimalu‘ji‘ jungianti‘ji‘ medi‘ arba karkasa‘.
Jungiojo grafo G = (V, E) karkasu vadiname minimalu‘ji‘ jungu‘ji‘ pografi‘ G0 = (V 0 , E 0 )
su V = V 0 ir E 0 ⊂ E.
Pagal b) iš jungiojo grafo atimant nuosekliai briaunas, bet nesugadinant jo jungumo,
gaunamas karkasinis medis. Nurodysime dar pora‘ karkasinio medžio išvedimo būdu‘.
1 būdas. Jungiame grafe G = (V, E) fiksuokime viršūne‘ x ∈ V ir viršūniu‘ aibe‘
suskaidykime i‘ nepersikertančias aibes
Vi = {y ∈ V : d(x, y) = i},

i = 0, 1, . . . , s < ∞.

Jei yi ∈ Vi , tai egzistuoja x − yi takas xz1 ...zi−1 yi . Pastebėkime, kad Vj 6= ∅, j =
0
0, 1, ..., i, kai i > 0. Taigi, bet kuriam yi ∈ Vi rasime yi−1
∈ Vi−1 . Iš, gal būt, keliu‘
0
galimybiu‘ pasirinkime viena‘. Kai y perbėgs V , priskirtieji y (artimesni pradiniam taškui)
ir y sudarys jungu‘ji‘ grafa‘
T = (V, E 0 ),

E 0 = {yy 0 : y ∈ V, y 6= x}.

Kadangi i‘ y patenkama tik iš vieno taško, jis neturi ciklu‘. Taigi, T - karkasinis medis.
4

2 (indukcinis) būdas. Imkime x ∈ V . Tada T1 := ({x}, ∅) - medis. Tarkime, kad jau
sukonstravome medžiu‘ seka‘
T1 ⊂ T2 ⊂ · · · ⊂ Tk ⊂ G
ir medžio Ti eilė yra i. Jei k < n = |V |, tai egzistuoja pora (y, z) tokia, kad z ∈ V (Tk ),
y ∈ V \ V (Tk ), čia V (Tk ) - Tk viršūniu‘ aibė, ir zy ∈ E. Priešingas atvejis prieštarautu‘
grafo G jungumui. Apibrėžkime
Tk+1 = (V (Tk ) ∪ {y}, E(Tk ) ∪ {zy}).
Baigtiniame grafe šis procesas baigtinis. Jis baigiasi, kai k = n.
Medi‘ galime charakterizuoti ir pagal jo skaitinius parametrus: eile‘ ir diduma‘.
3. Grafo parametru‘ ryšiai.
Pradėkime nuo paprastu‘ teiginiu‘.
1 (Euler’io) lema. Grafo viršūniu‘ laipsniu‘ suma yra lyginis skaičius.
Irodymas. Pakanka pastebėti, jog kiekviena briauna, turėdama du galus, i‘neša 2
vienetus i‘ suma‘
X
(1)
δ(G) = 2|E|
‘

x∈V


1 išvada. Nelyginio laipsnio viršūniu‘ kiekis grafe yra lyginis skaičius.
2 išvada. Tarkime
d(G) =

1 X
δ(x)−
|V |
x∈V

vidutinis grafo laipsnis, o ε = |E|/|V | – vidutinis briaunu‘ skaičius, tenkantis vienai
viršūnei. Tada ε(G) = d(G)/2.
Irodymas. (1) suma lygi |V |d(G).

‘

Susitarus, kad kilpos atveju viršūnės laipsnis laikomas lygiu 2, lema išlieka teisinga
ir bendresniems grafams.
2 lema. Tarkime, kad G0 = (V 0 , E 0 ) ir G00 = (V 00 , E 0 ), V 0 ∩ V 00 = ∅, - du pilnieji
grafai su
|V 0 | = n1 , |V 00 | = n2 , n1 + n2 = n.
Grafo G0 ∪ G00 didumas didžiausias, kai n1 = n − 1, o n2 = 1.
Irodymas. Dabar grafe G0 ∪ G00 turime

‘

n1 (n1 − 1) n2 (n2 − 1)
+
2
2
5

briaunu‘. Apskaičiuokime, kaip keičiasi bendras briaunu‘ skaičius, jei viena viršūne didesni‘
grafa‘ padidintume, o kita‘, mažesni‘ji‘, - sumažintume. Tegu n1 ≥ n2 . Gautasis briaunu‘
skaičius būtu‘ lygus
n1 (n1 + 1) (n2 − 1)(n2 − 2)
+
,
2
2
o skirtumas n1 + 1 − n2 ≥ 1.
Taigi, kartojant panašia‘ procedūra‘ pasieksime maksimalu‘ bendra‘ briaunu‘ skaičiu‘, kai
n1 = n − 1, n2 = 1. Lema i‘rodyta.
1 teorema. Jei n - grafo eilė, m - didumas, o k - jo komponenčiu‘ kiekis, tai
n−k ≤m≤

(1.1)

1
(n − k)(n − k + 1).
2

Irodymas. Pirma‘ja‘ nelygybe‘ i‘rodysime, taikydami matematine‘ indukcija‘ m ≥ 0
‘
atžvilgiu. Kai m = 0, turime nulini‘ grafa‘ su n jungumo klasiu‘. Tad, nelygybė triviali.
Tegu m1 < m2 < · · · - n eilės grafu‘ G, turinčiu‘ k jungumo klasiu‘, didumai su
savybe: išmetus dar viena‘ briauna‘ iš G, padidėtu‘ jo jungiu‘ komponenčiu‘ skaičius. Kai
mj−1 ≤ m < mj , kairioji iš (1.1) nelygybiu‘ išplauks iš nelygybės, kai m = mj−1 . Todėl
pakanka nelygybe‘ i‘rodyti tik šiai sekai.
Tarkime, jog nelygybė i‘rodyta grafui su mj−1 briauna, ir nagrinėkime atveji‘ |E| =
mj . Kadangi dabar kiekviena briauna yra tiltas, išmetus kažkuria‘ iš ju‘ gauname grafa‘,
kuriam galioja indukcijos prielaida. Tegu tai - grafas
G0 = (V 0 , E 0 ),
Jis turi k + 1 klase‘, todėl

|V 0 | = n,

|E 0 | = mj − 1.

n − (k + 1) ≤ mj − 1.

Iš čia išplaukia pirmoji iš (1.1) nelygybiu‘.
Vertindami m iš viršaus, nagrinėkime pati‘ ”blogiausia‘” atveji‘, kai kiekviena iš jungumo klasiu‘ yra pilnieji pografiai. Pritaike‘ lema‘ kiekvienai šiu‘ klasiu‘ porai, gauname,
kad bendras briaunu‘ kiekis m bus maksimalus, kai viena iš ju‘ yra labai didelė, o likusios
- tušti grafai. Todėl tada n-os eilės grafe su k jungumo klasiu‘, pografiu‘ eilės yra
n − k + 1,

, 1, . . . , 1.

Taigi, maksimalus briaunu‘ skaičius lygus
(n − k + 1)(n − k)
.
2
1 teorema i‘rodyta.
Išvada. Jei n eilės grafas turi daugiau nei
jungusis.
6

1
2 (n

− 1)(n − 2) briaunu‘ , tai jis yra

2 teorema. n-os eilės jungusis grafas yra medis tada ir tik tada, kada jo didumas
lygus n − 1.
Irodymas. Pagal kairia‘ja‘ (1.1) nelygybe‘ jungiajame n eilės grafe yra ne mažiau, negu
‘
n − 1 briauna. Jeigu ju‘ būtu‘ daugiau, grafas turėtu‘ turėti cikla‘. Taigi, teoremos sa‘lyga
yra būtina.
Jos pakankamumas akivaizdus.
1 išvada. n-os eilės grafo karkasinio medžio didumas lygus n − 1.
2 išvada. n-os eilės miško iš k medžiu‘ didumas lygus n − k.
4. Viena optimizavimo problema.
Karkasiniu‘ medžiu‘ savybėmis tenka naudotis sprendžiant kai kuriuos optimizavimo
uždavinius. Sakykime, reikia suprojektuoti pigiausia‘ vandentiekio tinkla‘, jungianti‘ visas
miestelio sodybas, kada žinomos visu‘ trasu‘ tarp namu‘ kainos. Jeigu gamtinės kliūtys yra
nei‘veikiamos, galima laikyti, kad trasos per šia‘ kliūti‘ kaina yra begalinė.
Formalizuojant galima i‘sivaizduoti, kad turime pilna‘ji‘ n grafa‘ G = (V, E) ir apibrėžta‘
funkcija‘
f : E → R+ .
Reikia išvesti karkasini‘ medi‘ (vesti kelias linijas i‘ ta‘ pačia‘ sodyba‘ visada bus brangiau)
T = (V, E 0 ) toki‘, kad bendra kaina
F (T ) =

X

f (xy)

xy∈E 0

būtu‘ mažiausia. Ši‘ medi‘ vadinkime ekonomišku. Pradžioje pateiksime tris šio uždavinio
sprendimo algoritmus.
1 algoritmas:
a) imame briauna‘ e = xy ∈ E su mažiausia kaina,
f (e) = min f (xy);
xy∈E

b) iš likusiu‘ briaunu‘ išrenkame pigiausia‘;
c) procesa‘ kartojame su sa‘lyga, kad išrenkamos briaunos nesudarytu‘ ciklo.
Procesas baigtinis, o gautasis grafas, kaip maksimalus beciklis grafas, pagal 2.2 teoremos c) punkta‘ bus karkasinis medis. Gautojo medžio ekonomiškuma‘ išnagrinėsime
vėliau.
2 algoritmas:
a) imame briauna‘ e = xy ∈ E su didžiausia kaina,
f (e) = max f (xy)
xy∈E

ir ja‘ atimame iš grafo G;
7

b) ta‘ pati‘ kartojame su grafu G − e;
c) procesa‘ baigiame, kai kitas briaunos atėmimas padidintu‘ grafo jungumo klasiu‘
skaičiu‘.
Gautasis grafas, kaip minimalus jungus grafas, pagal 2.2 teoremos b) punkta‘ bus
karkasinis medis.
3 algoritmas:
a) imame bet kokia‘ viršūne‘ x1 ∈ V ;
b) imame viena‘ iš pigiausiu‘ incidenčiu‘ x1 briauna‘ x1 x2 ∈ E, x2 ∈ V \ {x1 };
c) rade‘ x1 , . . . , xk ir briaunas xi xj ), i < j ≤ k ieškome x = xk+1 ∈ V \ {x1 , . . . , xk },
tokios, kad kaina f (xk+1 xi ) su kažkokiu i ≤ k būtu‘ minimali.
Procesas baigiasi, kai k = n, o briaunu‘ skaičius lygus n − 1. Taip gavome karkasini‘
medi‘.
1 teorema. Viršuje aprašytieji algoritmai duoda ekonomiškus medžius. Jei kainos
funkcija yra injektyvi, tai ekonomiškasis medis yra vienintelis.
Irodymas. Tarkime, jog T - ekonomiškas medis, turintis maksimalu‘ skaičiu‘ bendru‘
‘
briaunu‘ su T1 , medžiu, gautu naudojant 1 algoritma‘. Jei E(T ) 6= E(T1 ), imkime pirma‘
briauna‘ xy iš T1 , bet nepatekusia‘ i‘ T . Medyje T irgi yra x − y takas, sakykim P , kurio
bent viena briauna, tegu uv, nepatenka i‘ T1 . Renkant xy, ši briauna uv buvo viena iš
kandidačiu‘, todėl f (xy) ≤ f (uv). Sudarykime nauja‘ karkasini‘ medi‘
T 0 = T − uv + xy.
Jo kaina
F (T 0 ) = F (T ) − f (uv) + f (xy) ≤ F (T ),
todėl ir naujasis medis yra ekonomiškas. Bet jis turi dar daugiau bendru‘ briaunu‘ su T1 ,
nei T . Prieštara i‘rodo, kad T = T1 .
2 bei 3 algoritmais gautu‘ medžiu‘ ekonomiškumas i‘rodomas panašiais samprotavimais.
Nagrinėkime vienati‘, kai visos briaunu‘ kainos skirtingos. Taikome matematine‘ indukcija‘ grafo eilės atžvilgiu. Kai n = 2, 3, teiginys trivialus. Padare‘ prielaida‘, jog teorema
teisinga visiems n ≥ 4 eilės grafams, nagrinėdami (n + 1) eilės pilna‘ji‘ grafa‘, skelkime
viršūniu‘ aibe‘ i‘ dvi dalis V = V1 ∩ V2 , su n1 , n2 ≥ 2 viršūniu‘, n1 + n2 = n + 1 ir nagrinėkime indukuotosius pografius. Juose egzistuoja vieninteliai ekonomiški karkasiniai
medžiai T1 , T2 . Raskime
min f (xy).
x∈V1
y∈V2

Tarkime, ši minimali kaina i‘gyjama briaunoje xy, jungiančioje abu pografius. I‘ sitikinkime, kad medis
T4 := T1 ∪ T2 + xy
yra ekonomiškas.
8

Tarkime, T - ekonomiškas medis. Jei T4 6= T , tai vienintelė briauna iš T4 , nepatekusi
i‘ T , gali būti tik xy. Medyje T turi būti kita briauna uv, jungianti T1 su T2 . Bet tada
f (xy) < f (uv) ir medžio
T − uv + xy
kaina būtu‘ griežtai mažesnė, nei T . Prieštara i‘rodo ekonomiško medžio vienati‘.
Pastaba. Vienaties i‘rodymas duoda dar viena‘ karkasinio medžio konstravimo būda‘:
kai briaunu‘ kainos skirtingos, galima grafa‘ skaidyti i‘ mažesnius ir juose ieškoti karkasiniu‘
medžiu‘, o vėliau juos sujungti.
Grafai su funkcijomis, apibrėžtomis briaunu‘ arba viršūniu‘ aibėse, vadinami svoriniais grafais.
5. Cayley’io teorema.
Prisimename, kad grafai G = (V, E) ir G0 = (V 0 , E 0 ) vadinami izomorfiškais, jei
egzistuoja bijekcija φ : V → V 0 tokia, kad xy ∈ E tada ir tik tada, kada φ(x)φ(y) ∈ E 0 .
Multigrafu‘ atveju dar pridedamas reikalavimas, kad ši atitiktis galiotu‘ visoms kartotinėms
briaunoms. Grafa‘ su sunumeruota viršūniu‘ aibe vadinsime numeruotoju grafu. Tokiu‘
grafu‘ atveju izomorfizmas turi išlaikyti ir numeracija‘, t.y., jei x yra i-toji G grafo viršūnė,
tai izomorfiškame G0 grafe φ(x) turi būti irgi i-ta‘ja viršūne. 1889 metais Cayley apskaičiavo neizomorfišku‘ numeruotu‘ n tos eilės medžiu‘ kieki‘ T (n)? I‘ sitinkite, kad yra
4!
+ 4 = 16
2
skirtingu‘ 4-os eilės medžiu‘.
Cayley’io teorema. Iš viso galime sudaryti nn−2 neizomorfišku‘ numeruotu‘ n eilės
medžiu‘ .
1 -sis ‘irodymas (Prüfer’io). Tarkime G - nagrinėjamu‘ medžiu‘ aibė. Kadangi seku‘
aibės
{(a1 , . . . , an−2 ) : 1 ≤ ai ≤ n, 1 ≤ i ≤ n − 2} =: A
galia yra nn−2 , pakaks rasti bijektyvu‘ atvaizdi‘ A → G.
Kai n ≤ 2, teiginys akivaizdus.
Tegu toliau n > 2. Medžiui G = (V, E), kurios viršūniu‘ aibė sunumeruota, V =
{x1 , . . . , xn }, vienareikšmiškai priskirsime seka‘ α = (a1 , . . . , an−2 ) ∈ A, vadinama‘ medžio
Prüfer’io kodu. Pradėkime nuo medžio galinės viršūnės, kurios laipsnis lygus 1. Tokios
viršūnės egzistuoja, nes kiekviena briauna turi dvi viršūnes ir todėl
n
X

δ(xi ) = 2(n − 1).

i=1

Iš keliu‘ tokiu‘ viršūniu‘ išrinkime ta‘, kurios indeksas yra mažiausias. Tegu tai viršūnė
xb1 , o a1 - indeksas viršūnės, gretimos pirmajai. Grafas G − xb1 yra n − 1 eilės medis,
todėl procesa‘ galima kartoti, kol viršūniu‘, likusiu‘ grafe, skaičius yra didesnis už 2. Kai
šis skaičius lygus 2, mes jau esame sudare‘ vienintele‘ seka‘ (a1 , . . . , an−2 ).
9

Atvirkščiai, ar bet kokiai sekai α = (a1 , . . . , an−2 ) ∈ A galima vienareikšmiškai
priskirti medi‘? Atidėkime n viršūniu‘ ir brėžkime norima‘ medi‘, vadovaudamiesi žemiau
nurodytomis taisyklėmis:
a) jei b1 - mažiausias iš bent dvieju‘ natūraliu‘ju‘ skaičiu‘ (iš 1, ..., n), nepasirodžiusiu‘
sekoje α, tada junkime xb1 su xa1 ;
b) aibe‘ {1, . . . , n} pakeiskime {1, . . . , n} \ {b1 }, o α - seka (a2 , . . . , an−2 );
c) procesa‘ kartojame, kol išsemiame visa‘ seka‘ (tuo pačiu nubrėžiame n − 2 grafo
briaunas);
d) tarpusavyje sujungiame dvi likusias viršūnes.
Taip vienareikšmiškai gautasis grafas yra medis, nes jis jungia visas n viršūniu‘, o jo
didumas yra n − 1.
Kadangi abu nagrinėti atvaizdžiai yra vienas kito atžvilgiu yra atvirkštiniai, teorema
i‘rodyta.
Grafu‘ teorijai artimesnis kitas Cayley’io teoremos i‘rodymo būdas.
Antrasis teoremos ‘irodymas. Tarkime T (n, k) - kiekis n tos eilės medžiu‘, kuriuose
fiksuota viršūnė x ∈ V yra k-ojo laipsnio, 2 ≤ k ≤ n − 1. Viršūnės numeris nesvarbus, jo
neminėsime. Išvesime sa‘ryši‘ tarp T (n, k) ir T (n, k − 1).
Imame medi‘ G, kuriame d(x) = k − 1. Jame išmeskime briauna‘ uv, neincidenčia‘ su
x. Grafas skilo i‘ du pomedžius, viename iš ju‘ yra viršūnės x ir u arba x ir v. Tarkime, yra
pirmasis atvejis. Sujunge‘ dabar x su v, gauname vėl medi‘ G0 , kuriame d(x) = k. Pora‘
(G, G0 ) pavadinkime junginiu ir suskaičiuokime ju‘ kieki‘ dviem būdais. Kadangi grafui
G mes galime sudaryti tiek G0 , kiek yra briaunu‘ su aukščiau minėtomis savybėmis, tai
vienam G mes turime n−1−(k −1) = n−k partneriu‘. Taigi, iš viso yra (n−k)T (n, k −1)
junginiu‘.
Skaičiuokime ta‘ pati‘ skaičiu‘ kitu būdu, pradėdami nuo G0 , kuriame d(x) = k, k ≥ 2.
Tarkime x1 , . . . , xk - gretimos x viršūnės. Paeiliui išmesdami briaunas xxi , i = 1, . . . k,
mes ”atskeltume” pomedžius T1 , . . . , Tk , kuriu‘ eilės tegu bus n1 , . . . , nk ,
n1 + · · · + nk = n − 1.

(1)

Grafo G0 partneri‘ junginyje dabar konstruojame tokiu būdu:
a) išmetame xx1 , o vėliau viršūne‘ x1 sujungiame su bet kokia iš viršūniu‘, nepriklausančiu‘ T1 (turime n − 1 − n1 galimybiu‘);
b) ta‘ pati‘ kartojame su T2 , . . . , Tk .
Atsižvelge‘ i‘ grafu‘ G0 kieki‘ T (n, k) ir (1) iš viso gauname junginiu‘
n
X

T (n, k)(n − 1 − ni ) = (n − 1)(k − 1)T (n, k).

i=1

Sulygine‘ abi junginiu‘ skaičiaus formules, gauname
(n − 1)(k − 1)T (n, k) = (n − k)T (n, k − 1).
Kai k = 1, ši rekurenčioji formulė irgi teisinga. Jos nagrinėjimui galime panaudoti
akivaizdu‘ fakta‘, kad T (n, n − 1) = 1 (žvaigždinio grafo atvejis). Gauname


n−2
T (n, k) =
(n − 1)n−k−1 .
k−1
10

Sudėdami šias lygybes, išvedame medžiu‘ kiekio T (n) formule‘
T (n) =

n−1
X

T (n, k) =

k=1

n−1
X
k=1


n−2
(n − 1)n−k−1 = ((n − 1) + 1)n−2 = nn−2 .
k−1

Teorema i‘rodyta.
Numeruota‘ medi‘ su viena išskirta viršūne, šaknimi, vadinsime šakniniu medžiu.
Išvada. Yra nn−1 šakniniu‘ n eilės medžiu‘ .
Irodymas. Kiekvieno medžio, kuriu‘ kieki‘ nusako Cayley’io teorema, šaknimi gali būti
‘
bet kuri viršūnė.
6. Binariu‘ju‘ medžiu‘ kiekis.
Sprendžiant n duomenu‘ sutvarkymo pagal kokio nors požymio (rakto) didėjima‘
uždavini‘, naudojami binarieji medžiai. Jais vadiname medžius, kurie turi viena‘ 2ojo laipsnio viršūne‘, vadinama‘ šaknimi, o kitu‘ viršūniu‘ laipsniai yra 3 (jos vadinamos
vidinėmis viršūnėmis) arba 1 (šios viršūnės vadinamos lapais). Takas nuo šaknies iki
lapo atitiktu‘ kažkokio pradinio duomenu‘ kėlinio surūšiavima‘ (požymio didėjimo tvarkos
atpažinima‘). Todėl algoritma‘ aprašantis binarusis medis turi turėti n! lapu‘. Susitarkime
dar, kad briaunos, išvestos iš vidinės viršūnės kairiau ar dešiniau, skiriasi. Todėl grafus,
pavaizduotus (...) brėžinyje, laikysime skirtingais. Išvesime binariu‘ju‘ medžiu‘, turinčiu‘
N lapu‘, kiekio CN , vadinamo Katalano skaičiumi, formule‘.
Teorema. Teisingas rekurentusis sa‘ ryšis
CN =

N
−1
X

Ck CN −k ,

C1 = 1.

(6.1)

k=1

Be to,
CN



1 2N − 2
=
.
N N −1

(6.2)

Irodymas. Susitarkime, jog atveju N = 1, lapas sutampa su šaknimi, ir medi‘ sudaro
tik viena viršūnė. Kai N > 1, nagrinėkime grafa‘ G − v, kai v - binariojo medžio G šaknis.
Jis sudarytas iš dvieju‘ binariu‘ medžiu‘ - kairiojo, tarkime turinčio k lapu‘, ir dešiniojo,
turinčio eile‘ N − k lapu‘. Čia 1 ≤ k ≤ N − 1 gali būti bet kuris. Kairėje pusėje gali būti
bet koks iš Ck binariu‘ju‘ medžiu‘, o dešinėje – bet koks iš CN −k medžiu‘. Sudėje‘ pagal
k šiu‘ kiekiu‘ sandaugas, gauname visa‘ galima‘ binariu‘ju‘ medžiu‘ CN kieki‘. (6.1) formulė
i‘rodyta.
Išvedant (6.2) formule‘ naudojame generuojančias funkcijas. Pažymėkime
‘

F (t) =

X

CN tN ,

N ≥1

11

t ∈ R.

Tada
2

F (t) =

−1
X  NX

N ≥2



Ck CN −k tN .

k=1

Vadinasi,
F (t) = t + F (t)2 ,
arba
F (t) =



1
1 ± (1 − 4t)1/2 .
2

Kadangi F (0) = 0, tai paskutinėje lygybėje galimas tik pliuso ženklas. Naudodami
apibendrinta‘ja‘ Niutono binomo formule‘ ir lygindami koeficientus, gauname
CN

 
1 1/2
(2N − 2)!
(−4)N =
.
=−
2 N
(N − 1)!N !

Iš čia išplaukia (6.2) formulė.
Teorema i‘rodyta.
Vidutinis tako nuo šaknies iki lapo ilgis nusako algoritmo, pavaizduoto binariu medžiu, efektyvuma‘.
7. Grafu‘ ir jungiu‘ grafu‘ su skaidžia savybe kiekiu‘ sa‘ryšis.
Iki šiol turėjome jungiu‘ grafu‘ (numeruotu‘ medžiu‘, šakniniu‘ medžiu‘, binariu‘ medžiu‘)
kiekio skaičiavimo formuliu‘. Kaip skaičiuoti nebūtinai jungiu‘ n eilės grafu‘ kiekius?
Pradėkime nuo numeruotu‘ šakniniu‘ mišku‘ , kuriuos sudaro šakniniai numeruoti medžiai,
kiekio skaičiavimo.
1 teorema. Jei qn – n eilės numeruotu‘ šakniniu‘ mišku‘ kiekis, o dn – šakniniu‘
numeruotu‘ n eilės medžiu‘ kiekis, tai
qn =

dn+1
= (n + 1)n−1 .
n+1

Irodymas. Pavaizduokime nagrinėjama‘ n eilės miška‘. Jo medžiu‘ šaknis sujunkime
su papildoma šaknimi, kurios numeris, sakykime yra j, 1 ≤ j ≤ n + 1. Skaičiais 1, ..., j −
1, j +1, ...n+1 pernumeruokime miško viršūnes (jei j ≤ n, to daryti nereikia), nekeisdami
numeracijos tvarkos. Taip iš kiekvieno n eilės miško gauname n + 1 numeruota‘ medi‘,
kurio eilė yra n + 1. Atvirkščiai, turėdami toki‘ medi‘, galėtume atimti jo šakni‘, o vėliau
pernumeruodami viršūnes skaičiais 1, ..., n ir gretima‘sias viršūnes pavadindami gautu‘ju‘
medžiu‘ šaknimis, gautume n eilės šaknini‘ numeruota‘ miška‘. Todėl
‘

dn+1 = (n + 1)qn .
Dabar pakanka pasinaudoti Cayley’io teoremos išvada, jog dn = nn−1 .
1 teorema i‘rodyta.
12

Grafo savybe‘ vadinsime skaidžia, jei jis ja‘ turi tada ir tik tada, kada kiekviena jo
jungi komponentė turi ta‘ savybe‘. Pavyzdžiui, miškas turi šaknu‘ rinkini‘ (miško šakni‘)
tada ir tik tada, kada kiekvienas ji‘ sudarantis medis turi šakni‘. Panašiai, jei binaru‘ji‘
miška‘ sudarytume, apjungdami binarius medžius, gautume jo skaidžia‘ savybe‘.
Pažymėkime:
an – kieki‘ n eilės numeruotu‘ grafu‘ su skaidžia R savybe;
ank – kieki‘ n eilės numeruotu‘ grafu‘ su šia savybe ir turinčiu‘ k jungiu‘ komponenčiu‘;
bn – kieki‘ jungiu‘ n eilės grafu‘ su R savybe.
1 lema. Teisingas sa‘ ryšis
X
bn 1 · · · b n k
n!
.
ank =
k! n +···+n =n n1 ! · · · nk !
1

k

Čia sumuojama pagal visus natūraliu‘ ju‘ skaičiu‘ n1 , ..., nk rinkinius su sa‘ lyga n1 + · · · nk =
n.
Irodymas. Fiksuokime natūraliu‘ju‘ skaičiu‘ n1 , ..., nk rinkini‘ su sa‘lyga n1 + · · · nk = n
‘
ir sudarykime visus grafus, turinčius R savybe‘, ir n1 , ..., nk eiliu‘ komponentes. Aišku,
grafe komponenčiu‘ tvarka nesvarbi.
Viršūniu‘ n aibe‘ V galime suskaidyti V = V1 ∪ · · · ∪ Vk , Vi ∩ Vj = ∅, 1 ≤ i < j ≤ k,


n!
n!
=
n1 , . . . nk
n1 ! · · · nk !
būdais taip, kad j-oje aibėje būtu‘ nj elementu‘, 1 ≤ j ≤ k. Čia poaibiu‘ tvarka yra svarbi.
Turėdami atskiro j-ojo poaibio viršūnes, galime sudaryti bnj jungiu‘ grafo komponenčiu‘
su R savybe. Taigi, fiksuotam rinkiniui n1 , . . . nk tuo būdu gautume
b n 1 · · · bn k
n1 ! · · · nk !
grafu‘ su R savybe. Sudėje‘ pagal visus šiu‘ skaičiu‘ rinkinius ir atsižvelge‘ i‘ tai, kad grafo
komponenčiu‘ tvarka yra nesvarbi (padalydami iš k!), baigiame 1 lemos i‘rodyma‘.
Dabar galime išvesti i‘domu‘ numeruotu‘ grafu‘ ir jungiu‘ numeruotu‘ grafu‘, kurie turi
skaidžias savybes, kiekiu‘ eksponentiniu‘ generuojančiu‘ funkciju‘ sa‘ryši‘.
2 teorema. Pažymėkime
n!

∞
X
an n
A(t) = 1 +
t ,
n!
n=1

∞
X
bn n
B(t) =
t .
n!
n=1

Tada
A(t) = eB(t) .
Irodymas. Naudodami 1 lemos rezultata‘ ir lygybe‘ an = an1 + · · · ann , skaičiuojame

‘

∞
X

n
X
X
1
bn 1 · · · b n k
A(t) − 1 =
t
=
k! n +···+n =n n1 ! · · · nk !
n=1
k=1
1
k
X

∞
∞
n k
X
1
bn t
=
= eB(t) − 1.
k! n=1 n!
n

k=1

13

cija

2 teorema i‘rodyta.
Išvada. Šakniniu‘ n eilės medžiu‘ kiekio dn = nn−1 eksponentinė generuojanti funkD(t) =

tenkina funkcine‘ lygti‘

∞
X
dn n
t
n!
n=1

D(t) = teD(t) .

Irodymas. Kaip minėjome, mišku‘ savybė turėti šakni‘ yra skaidi. Todėl panaudoje‘ 1
teoremos žymenis ir jos rezultata‘, iš 2 teoremos gauname
‘

∞
∞
X
qn n X dn+1 n
1+
t =
t = t−1 D(t) = eD(t) .
n!
(n
+
1)!
n=1
n=0

2 teoremoje išvesta formulė patogi, jei viena iš generuojančiu‘ funkciju‘ yra paprasto
pavidalo. Pavyzdžiui, binariu‘ N -lapiu‘ mišku‘ kieki‘ mN galetume tirti naudodamiesi lygybe
∞
X
√
mN N
1
1+
t = exp{ (1 − 1 − 4t)},
N!
2
N =1

gauta iš Katalano skaičiu‘ generuojančios funkcijos ir 2 teoremos.
Visi n aibės atvaizdžiai i‘ ja‘ pačia‘ (ju‘ yra nn ) gali būti pavaizduoti n eilės funkciniais
grafais. Tai numeruoti digrafai, turintys skaidžia‘ savybe‘: iš kievienos viršūnės išeina tik
viena briauna. Raskite jungiu‘ funkciniu‘ n eilės grafu‘ kieki‘.
8. Matricos, asocijuotos su grafais.
Be Priūferio kodo, i‘vesto medžiu‘ žymėjimui, informacija‘ apie numeruotus grafus galime išreikšti matricomis. Tarkime, jog n-tos eilės orentuoto multigrafo (multidigrafo) G
viršūnės sumumeruotos skaičiais 1, ..., n ir aij – briaunu‘, išvestu‘ iš i-os i‘ j-a‘ viršūnes,
skaičius. Matrica‘ AG su elementais aij , 1 ≤ i, j ≤ n, vadiname gretimumo matrica.
Neorentuoto multigrafo atveju gretimumo matrica yra simetrinė, o kilpu‘ kiekis dvigubinamas.
Sunumeravus ir briaunas skaičiais 1, ..., m, čia m – grafo didumas, galime sudaryti
grafo incidentumo matrica‘ BG = B = (bij ), 1 ≤ i ≤ n, 1 ≤ j ≤ m, su


 1, jei i viršūnė yra incidenti j briaunai, kuri nėra kilpa,
bij = 2, jei i viršūnė yra incidenti j briaunai, kuri yra kilpa


0, jei i viršūnė nėra incidenti j briaunai.
Apibrėžiant digrafo incidentumo matrica‘, atsižvelgiama i‘ briaunos krypti‘. Dabar
bekilpiam digrafui

jei i yra pradinė j briaunos viršūnė,

 1,
bij = −1, jei i yra galinė j briaunos viršūnė,


0,
i viršūnė nėra incidenti j briaunai.
14

Jei i viršūnė yra incidenti kilpai, pažymėtai j numeriu, tai dažnai vartojamas žymuo
bij = −0.
Pateiksime viena‘ i‘vestu‘ju‘ matricu‘ sa‘ryši‘.
1 teorema. Tarkime G - numeruotas multidigrafas be kilpu‘ , A ir B – jo gretimumo
ir incidentumo matricos atitinkamai. Tada
BB 0 = D − A.
Čia 0 žymi matricos transponavima‘ , o D – diagonali matrica, kurios ‘istrižainėje yra iš
eilės surašyti viršūniu‘ laipsniai.
Irodymas. Jei cij – matricos BB 0 bendrasis narys, tai

‘

(1)

cij =

m
X

bil bjl .

l=1

Todėl, kai i 6= j, sandauga bil bjl lygi 0 arba -1. Pastaroji lygybė yra teisinga tik tuo
atveju, kai xi xj = el . Sudedant pagal l, -1 dauginsis iš tokio skaičiaus, kiek yra briaunu‘,
jungiančiu‘ xi ir xj .
Kai i = j, cii yra matricos i‘strižainės narys. Matrica A turi nuline‘ i‘strižaine‘. (1)
suma lygi briaunu‘, išvestu‘ iš xi skaičiui.
Teorema i‘rodyta.
Algebroje yra i‘prasta matricas susieti su tiesiniais vektoriniu‘ erdviu‘ atvaizdžiais.
Kokios vektorinės erdvės yra natūralios grafu‘ teorijoje? Iliustracijai panagrinėsime viena‘
elektrotechnikos problema‘.
9. Fizikiniai elektros grandiniu‘ dėsniai.
Elektros grandinės vaizduojamos multidigrafais. Grafu‘ teorija palengvina fizikiniu‘
uždaviniu‘ sprendima‘, ir atvirkščiai, elektros grandiniu‘ uždaviniai padarė i‘takos grafu‘
teorijos vystymuisi.
Prisiminsime pagrindinius fizikos dėsnius, veikiančius grandinėse. Naudosime elektrinio potencialo taške, potencialu‘ skirtumo tarp tašku‘, elektros srovės krypties bei
didumo, varžos bei laidumo sa‘vokas, o taip pat grafu‘ teorijoje priimtus terminus. Priimti
fizikoje matavimo vienetai: omai, amperai ar voltai, mūsu‘ nedomins.
Ohm’o dėsnis. Jei p = pxy = p(x) − p(y) - potencialu‘ briaunos xy (išvestos iš x ‘i
y) galiniuose taškuose skirtumas, o r - šios briaunos varža, tai elektros srovės, tekančios
iš x ‘i y didumas
p
w = wxy = .
r
Kirchhoff ’o potencialu‘ dėsnis. Jei x0 x1 . . . xk x0 - elektros grandinės ciklas, ir
pi,i+1 - potencialu‘ skirtumas tarp tašku‘ xi ir xi+1 , tai
p01 + p12 + · · · + pk0 = 0.
15

Aišku, nenuliniu‘ potencialu‘ (ar sroviu‘) atveju potencialu‘ (sroviu‘) ženklai bus tiek
teigiami, tiek ir neigiami. Visada laikoma, kad wxy = −wyx .
Kirchhoff ’o srovės dėsnis. Jei wxxi - sroviu‘ , ištekančiu‘ iš viršūnės x briaunomis
xxi , i = 1, . . . , k, didumai ir w∞,x = −wx,∞ - srovės, ‘itekančios ‘i viršūne‘ x, didumas,
tai
wxx1 + wxx2 + · · · + wxxk + wx,∞ = 0.
Briaunoje xy, esančioje realiojoje fizikinėje elektros grandinėje, svarbus tik potencialu‘ skirtumas pxy = px − py , o ne patys potencialai. Todėl dažniausiai srovės išėjimo
viršūnėje potencialas laikomas nuliniu. Tada potencialai kituose taškuose apibrėžiami
vienareikšmiškai. Pagri‘skite šia‘ minti‘!
Išnagrinėkite šiuos iliustracinius uždavinius:
1) iš aukščiau pateiktu‘ dėsniu‘ išveskite varžos ir laidumo nuosekliajame ir lygiagrečiame jungimuose savybiu‘;
2) raskite sroviu‘ didumus ir bendra‘ varža‘ rombo su viena i‘strižaine pavidalo grandinėje;
3) raskite kubo, kurio briaunos turi vienetines varžas, bendra‘ varža‘.
4) pakeiskite žvaigždini‘ 4 eilės grafa‘ trikampio grafu, kad varžos jungiant bet kurias
viršūniu‘ poras būtu‘ tos pačios;
5) apskaičiuokite trikampės piramidės briaunu‘ varža‘.
Egzistuoja i‘domus ryšys tarp elektros sroviu‘ grafo briaunose didumu‘ ir tam tikru‘
karkasiniu‘ medžiu‘ kiekio.
1 teorema. Tarkime, kad elektros grandinė yra jungus multidigrafas G, kurio
kiekviena briauna turi vienetine‘ varža‘ , be to, vienetinio didumo srovė ‘iteka viršūnėje
s ir išteka viršūnėje t 6= s. Jei N - grafo G karkasiniu‘ medžiu‘ kiekis, o N (xy) - kiekis
karkasiniu‘ medžiu‘ , kuriuose yra s − t takas, pereinantis briauna‘ xy nuo x link y. Tada
dydžiai kiekvienoje viršūnėje
wxy :=

N (xy) − N (yx)
N

tenkina Kirchhoff ’o srovės dėsni‘ .
Irodymas. Pradėkime vienu akcentu. Pastebėkime, kad s − t takas medyje yra
‘
vienintelis. Jis gali turėti ar neturėti briaunos xy. Pirmuoju atveju ši briauna pereinama
nuo x link y (tada ši‘ taka‘ i‘skaičiuojame i‘ N (xy)) arba atvirkščiai (takas i‘skaičiuojamas
dydyje N (yx)).
Nagrinėkime Kirchhoff’o srovės dėsni‘ taip vadinamoje elektros šaltinio viršūnėje
s. Tarkime, kad Γ(s) - jos kaimyniniu‘ viršūniu‘ aibė. Kiekvienas karkasinis medis eina
per tam tikra‘ viršūne‘ iš Γ(s), ir tuo pačiu, - per briauna‘ su, todėl
X
N (su) = N.
u∈Γ(s)

Be to, galim susitarti, kad visos briaunos yra išvestos iš šaltinio ir nei viena nenukreipta
i‘ ji‘. Tad, N (us) = 0 ir
X
wsu = 1.
u∈Γ(s)

16

To buvo ir tikėtasi.
Šis dėsnis viršūnėje t patikrinamas taip pat.
Tarkime y - bet kuri kita viršūnė. Karkasiniai medžiai, kuriuose esantys s − t takai
neina per y, nefiguruoja dydžiu‘ wxy apibrėžime. Toliau imkime medi‘ T ir jame esanti‘
s − t taka‘
PT = s . . . xyz . . . t,
einanti‘ per viršūne‘ y. Briaunos xy kryptis sutampa su tako kryptimi, todėl ji i‘neša i‘ dydi‘
N (xy) lygiai 1-a‘. Bet take yra ir briauna yz, kurios i‘našas, lygus 1, bus dydyje N (zy).
Bendras i‘našas i‘
X
wxy
x∈Γ(y)

lygus nuliui. Tad ši suma lygi nuliui. Srovės dėsnis patikrintas.
1 teorema i‘rodyta.
Kai briaunu‘ varžos nėra vienetinės, i‘rodomas bendresnis teiginys. Elektros grandinės
karkasinio medžio svoriu vadinama jo briaunu‘ laidumu‘ sandauga. Pažymėkime N ∗ visu‘
karkasiniu‘ medžiu‘ svoriu‘ suma‘, o N ∗ (xy) - karkasiniu‘ medžiu‘, turinčiu‘ s−t taka‘ , einanti‘
per xy šia kryptimi, svoriu‘ suma‘.
2 teorema. Tarkime, kad elektros grandinė yra jungus grafas G, ir vienetinio
didumo srovė ‘iteka viršūnėje s ir išteka viršūnėje t 6= s. Tada srovė briaunoje xy lygi
wxy :=

N ∗ (xy) − N ∗ (yx)
.
N∗

I‘ rodyma‘ paliekame skaitytojui.
Kirchhofo dėsniu‘ taikymas, kai elektros grandinėje yra daug viršūniu‘, – ilgas procesas. Imkime grandine‘, vaizduojama‘ kubiniu grafu, ir raskime sroves, tekančias dvylikoje jo briaunu‘, jei visu‘ briaunu‘ varžos yra vienetinės, o vienetinio didumo srovė i‘teka
vienoje viršūnėje ir išteka gretimoje pastarajai viršūnėje. Jei negalvodami i‘vestume 12
nežinomu‘ju‘ ir, turėdami 8 viršūnes, pritaikytume Kirchhofo srovės dėsni‘ kiekvienoje iš
ju‘, po to imtume visus galimus ciklus (pvz., ciklus sudaro kiekvieno iš 6 šonu‘ briaunos,
kiekvienos iš 12 poru‘ šonu‘, turinčiu‘ bendra‘ briauna‘, ”išorinės” briaunos ir t.t.) ir jiems
pritaikytume potencialo dėsni‘, tai gautume tiesiniu‘ lygčiu‘ sistema‘, kurioje labai daug
lygčiu‘. Aišku, tarp ju‘ bus daug tiesiškai priklausomu‘. Pasirodo, yra būdu‘ iš anksto
numatyti reikalingu‘ nepriklausomu‘ lygčiu‘ skaičiu‘.
10. Vektorinės erdvės, asocijuotos su grafais.
Tarkime G = (V, E) - n eilės ir m didumo grafas. Nagrinėkime funkciju‘ erdve‘
C0 (G) := {f : V → C}
funkciju‘ sudėties kiekviename taške bei daugybos iš skaliaro atžvilgiu. Funkcija‘ f nusako
jos reikšmės viršūnėse f (xj ) =: cj , 1 ≤ j ≤ n. Todėl C0 (G) izomorfiška Cn , o jos
17

dimensija lygi n. Jos standartinė bazė bus funkciju‘ rinkinys f1 , . . . , fn , kai funkcija fj
apibrėžiama lygybėmis
fj (xi ) = δij .
Čia δij - Kronekerio simbolis. Dabar lygybė
f (x) =

n
X

cj fj (x)−

j=1

funkcijos f išraiška standartine baze. I‘ vedus skaliarine‘ daugyba‘
0

00

< f , f >:=

n
X

c0j c¯00j

j=1

erdvė tampa kompleksine Euklido erdve (unitaria‘ja), šios daugybos atžvilgiu standartinė
bazė yra ortonormuota.
Panašiai i‘vedama ir m - matė erdvė funkciju‘, apibrėžtu‘ grafo briaunu‘ aibėje:
C1 (G) := {g : E → C}.
Ji yra izomorfiška erdvei Cm . I‘ domesnis ir svarbesnis digrafu‘ atvejis. Tegu toliau briaunos
sunumeruotos skaičiais nuo 1 iki m ir joms priskirtos kryptys. Turėdami cikla‘ L, sudaryta‘
iš briaunu‘ ei1 , . . . , eik , kur ei1 vienas galas sutampa su eik galu, ir fiksuodami ciklo
krypti‘ (sakysim, prieš laikrodžio rodykle‘ planariajame grafe), ciklui galime priskirti taip
vadinama‘ ciklo vektoriu‘ z̄L = (z1 , . . . , zm ), iš 1,-1 arba 0:


 1, jeigu ej priklauso ciklui ir eina ciklo kryptimi;
zj = −1, jeigu ej priklauso ciklui, bet jo kryptis priešinga;


0, jeigu ej nepriklauso ciklui.
Naudojamas ir kitas vaizdus vektoriaus z̄L užrašas
z̄L =

m
X

zj ej ,

j=1

neteikiant šioje sumoje jokios geometrinės prasmės, i‘prastos vektoriams, briaunoms ej ,
nors jos turi ir kryptis.
Sekant kitais autoriais, galima naudoti ciklui priskirta‘ funkcija‘ (ciklo funkcija‘):
gL (e) =

m
X

zj gj (e),

e∈E

j=1

su standartine funkciju‘ gj , 1 ≤ j ≤ m, baze. Aišku, vektoriniu‘ erdviu‘ izomorfizmo tikslumu, tai yra tas pats. Kadangi grandinė yra ciklu‘, neturinčiu‘ bendru‘ briaunu‘, sa‘junga,
18

tai jai galime irgi priskirti panašia‘ funkcija‘ - suma‘ funkciju‘, priskiriamu‘ atskiriems jos
ciklams. Kai L perbėgs visus grafo ciklus, gausime aibe‘ funkciju‘ {gL }, ju‘ tiesinis apvalkas
Z(G) erdvėje C1 (G) vadinamas ciklu‘ poerdviu. Jo dimensija dimZ(G) vadinama grafo
G ciklomačiuoju skaičiumi.
Sudarykime dar viena‘ erdvės C1 (G) poerdvi‘. Imkime viršūniu‘ aibės skaidini‘ P :
V = V1 ∪ V2 , V1 ∪ V2 = ∅.
Nagrinėkime tik tas briaunas, kurios eina iš V1 i‘ V2 arba atvirkščiai. Ši briaunu‘ aibė
vadinama pjūvio aibe. Sudarykime vektoriu‘ ūP = (u1 , . . . , um ) ∈ Rm


 1, jeigu ej eina iš V1 i‘ V2 ;
uj = −1, jeigu ej eina iš V2 i‘ V1 ;


0, jeigu ej nejungia V1 su V2 .
dažnai užrašoma‘ suma
ūP =

m
X

uj ej

j=1

arba funkcija
gP (e) =

m
X

uj gj (e),

e ∈ E,

j=1

čia - gj , 1 ≤ j ≤ m, standartinė funkciju‘ bazė. Imant visus i‘manomus skaidinius P ,
gaunama funkciju‘ gP sistema, jos tiesinis apvalkas U (G) erdvėje C1 (G) vadinamas pjūviu‘
poerdviu (kociklu‘ poerdviu).
1 teorema. Briaunu‘ funkciju‘ erdvė - tiesioginė tarpysavyje ortogonaliu‘ poerdviu‘
Z(G) ir U (G) suma. Jei grafas G turi n viršūniu‘ , m briaunu‘ ir k jungumo klasiu‘ , tai
dimZ(G) = m − n + k,

dimU (G) = n − k.

Irodymas. Tikriname teoremoje nurodytu‘ poerdviu‘ ortogonaluma‘. Imame bet koki‘
cikla‘ L ir bet koki‘ skaidini‘ P bei funkciju‘ koordinačiu‘ vektorius z̄L ir ūP ir skaičiuojame
< z̄L , ūP >. Nenuliniai šios skaliarinės sandaugos dėmenys atitiks tik L ciklo briaunoms,
priklausančioms ir P pjūviui. Ju‘ skaičius yra lyginis. Susitarkime laikyti, kad briauna
−ej , eina ciklo kryptimi, jei ej kryptis buvo priešinga ciklo krypčiai. Tada nagrinėjama
skaliarinė sandauga lygi kiekiui L ciklo briaunu‘, einančiu‘ iš V1 i‘ V2 minus kiekiui ciklo
briaunu‘, einančiu‘ iš V2 i‘ V1 . Vadinasi, ji yra lygi nuliui. Tuo pačiu poerdviu‘ ortogonalumas i‘rodytas.
Teoremoje nurodytos dimensiju‘ formulės išplauks iš nelygybiu‘
‘

(1)

dimZ(G) ≥ m − n + k,

dimU (G) ≥ n − k.

Tarkime pradžioje, kad G - jungus grafas, k = 1. Imkime karkasini‘ medi‘ T . Tarkime,
kad medyje panaudotos e1 , . . . , en−1 briaunos, o likusios en , . . . , em buvo nepanaudotos.
19

Prijungimas bet kurios iš šiu‘ briaunu‘ sukuria 1 cikla‘. Ji‘ vadinsime fundamentaliuoju
ciklu. Tegu Lj , n ≤ j ≤ m, vienas iš šiu‘ fundamentaliu‘ ciklu‘, o z̄j - jo vektorius. Atkreipkime dėmesi‘ i‘ paskutines m − (n − 1) koordinačiu‘. Kai j = n, pirmoji iš šiu‘ koordinačiu‘
lygi 1 ar -1, o kitos lygios nuliui. Panašiai, kai j = m, visos minėtos koordinatės , išskyrus
paskutine‘, lygios nuliui, o paskutinioji lygi 1 arba -1. Iš čia išplaukia vektoriu‘ sistemos
z̄j , n ≤ j ≤ m nepriklausomumas. Pirmoji iš (1) nelygybiu‘ i‘rodyta.
Nagrinėdami pjūvius irgi panaudokime karkasini‘ medi‘. Pastebėkime, kad bet kokios
T briaunos ej , 1 ≤ j ≤ n − 1, išmetimas duotu‘ pjūvi‘ Pj , (V = Vj0 ∪ Vj00 , Vj0 ∩ Vj00 = ∅), o
pati briauna ej jungtu‘ viena‘ viršūniu‘ aibe‘ su kita. Tarkime, kad ej pradžios viršūnė yra
aibėje Vj0 . Dabar šio pjūvio vektorius
ūj = (u1j , . . . , uij , . . . , un−1,j )
turės ujj = 1, o uij = 0, kai i 6= j, nes nejungia Vj0 su Vj00 . Akivaizdu, jog tiesiškai
nepriklausomu‘ tokiu‘ vektoriu‘ sudarytume ne mažiau, negu n − 1. Tuo būdu jungaus
grafo atveju (1) lygybės i‘rodytos.
Kai G grafas turi jungumo klases G1 . . . , Gk , funkciju‘ erdvė C1 (G) yra tiesioginė
suma ortogonaliu‘ tarpusavyje funkciju‘ erdviu‘ C1 (Gj ), 1 ≤ j ≤ k, kurios pagal i‘rodyta‘
dali‘ išsiskaido dvieju‘ ortogonaliu‘ poerdviu‘ sumomis. Be to, Z(G) ∩ C1 (Gj ) = Z(Gj ) bei
U (G) ∩ C1 (Gj ) = U (Gj ),
dim U (G) = dim U (G1 ) + · · · + dim U (Gk ) = (n1 − 1) + · · · + (nk − 1) = n − k.
Čia |Vi | = ni ir n1 + · · · + nk = n.
1 teorema i‘rodyta.
Pastebėkime, jog Kirchhofo srovės dėsnius visoms viršūnėms galima užrašyti naudojant incidentumo matrica‘ B. Tarkime w = (w1 , . . . , wm )0 – srovės vektorius stulpelis,
sudarytas iš sroviu‘, tekančiu‘ visomis briaunomis, tai matricu‘ lygybė
Bw = 0 = (0, . . . , 0)0
apima srovės dėsnius visose viršūnėse iš karto. Toliau nagrinėjant, aišku, imtume tik
tiesiškai nepriklausomos incidentumo matricos eilutes.
Panašiai elgiamasi ir potencialu‘ atveju. Jei z̄L - L ciklo vektorius, o p̄ = (p1 , . . . , pm )
- potencialu‘ skirtumu‘ vektorius, tai Kirchhoff’o potencialu‘ dėsnis teigia, jog
< z̄L , p̄ >= 0.
Kadangi grandinėje gali būti daug tarpusavyje priklausomu‘ ciklu‘, nebūtina juos visus
naudoti. Iš tiesu‘, vektoriai z̄L priklauso ciklu‘ poerdviui Z(G), kurio dimensija lygi m−n+
1 (I‘ vedus šaltinio bei išėjimo viršūne‘, grandinė yra jungi, k = 1), todėl pakanka naudoti
tik fundamentaliuosius ciklu‘ vektorius. Surade‘ karkasini‘ medi‘ T , išvesta‘ sakykim, per
briaunas e1 , ..., en−1 imkime paeiliui likusias briaunas en , ..., em . Tarkime gautu‘ju‘ ciklu‘
vektoriai z̄j , n ≤ j ≤ m surašyti eilutėmis, sudaro matrica‘ C, (m − n + 1) × m, tada visa
informacija apie potencialus užrašoma matricine lygybe.
20

Kirchhoff ’o potencialu‘ dėsnis. Jei C fundamentaliu‘ ju‘ ciklo vektoriu‘ sudaryta
matrica, o p̄ - potencialu‘ skirtumu‘ vektorius stulpelis, tai
C p̄ = 0.
Ir Ohm’o dėsniui galima suteikti matricine‘ vektorine‘ išraiška‘.
Gri‘žkite prie anksčiau minėtos elektros grandinės, vaizduojamos kubiniu grafu. Šio
grafo ciklomatusis skaičius lygus 5. Išveskite karkasini‘ medi‘ ir sudarykite 5 fundamentaliuosius ciklus. Užrašykite Kirchhoff’o potencialu‘ dėsni‘. Prijunge‘ lygčiu‘ sistema‘, gauta‘
iš srovės dėsnio, bei sroviu‘ ir potencialu‘ sa‘ryšius, gautus iš Ohm’o dėsnio, raskite sroves
šio grafo briaunose bei bendra‘ jo varža‘.
11. Srautu‘ uždaviniai digrafuose
Kaip ir elektros srovės atveju, nagrinėsime digrafus G = (V, E) su orentuotu‘ briaunu‘
aibe E. Šiame digrafe briaunos xy ir yx yra skirtingos, jos gali būti abi. Dėl šios
priežasties digrafas nelaikomas multidigrafu. Viršūniu‘ aibėje išskirsime šaltinio viršūne‘ s
bei išėjimo viršūne‘ t. Digrafus, kuriuose išskirtos šaltinio ir išėjimo viršūnės, o briaunoms
yra priskirti svoriai (talpos) dar vadinmai tinklais. Pažymėkime
Γ+ (x) = {y ∈ V : xy ∈ E}.
Tai gretimu‘ x viršūniu‘ aibė, kuriai egzistuoja briaunos einančios iš x i‘ y. Panašiai,
Γ− (x) = {y ∈ V : yx ∈ E}.
Srautu vadinsime neneigiama‘ funkcija‘ f : E → R+ , tenkinančia‘ Kirchhoff’o dėsni‘:
kiekvienoje digrafo G vidinėje viršūnėje x 6= s, t teisinga lygybė
X

X

f (xy) =

f (zx).

z∈Γ− (x)

y∈Γ+ (x)

Srauto reikšmes žymėsime f (e) = f (xy), kai briauna e eina iš x i‘ y.
Apibrėžime nurodytos reikšmiu‘ s sumos vadinamos išeinančio iš viršūnės x bei i‘ ja‘
i‘einančio srauto didumais. Trumpiau kalbant, laikome, kad vidinėse viršūnėse srautas
nesukuriamas. Digrafo viršūnėje s paleistas
v(f ) :=

X

f (sy) −

X

f (zs)

z∈Γ− (s)

y∈Γ+ (s)

didumo srautas išeina iš viršūnės t tokio pat didumo
X

y∈Γ− (t)

f (yt) −

X

y∈Γ+ (t)

21

f (ty).

Šia‘ reikšme‘ v(f ) vadinsime srauto kiekiu digrafe G. Ar bet kokio kiekio srautas gali būti
apibrėžtas digrafe? Praktikoje dažnai siekiama maksimalaus didumo srauto, tačiau briaunos turi ribotas talpas (pralaiduma‘). Viso digrafo talpa‘ nusako rinkinys neneigiamu‘
skaičiu‘ {c(xy); xy ∈ E}, t.y., funkcija c : E → R+ . Todėl tokiuose uždaviniuose atsiranda natūralios sa‘lygos
f (xy) ≤ c(xy)

(1)
bet kokiai xy ∈ E. Tuo pačiu,
(2)

v(f ) ≤

X

c(xy) < ∞.

xy∈E

Apibrėžimas. Srauta‘ f0 , tenkinanti‘ (1) sa‘ lyga‘ ir toki‘ , kad
(3)

maxf v(f ) = v(f0 ),

vadiname (suderintos) maksimalaus srauto problemos sprendiniu.
Šio sprendinio egzistavimas - netrivialus dalykas. Išsiaiškinkime, ar galima (3) lygybėje naudoti ”max” vietoje abejoniu‘ nekeliančio ”sup”.
1 teorema. Egzistuoja maksimalaus srauto problemos sprendinys.
Srautu‘, tenkinančiu‘ (1) sa‘lyga‘, egzistavimas akivaizdus.
Iš (2) išplaukia, jog egzistuoja baigtinis dydis v := supf v(f ). Čia supremumas
imamas pagal visus i‘manomus digrafo srautus. Todėl egzistuoja seka srautu‘ f1 , .., fN , ...
tokia, kad
(4)

lim v(fN ) = v.

N →∞

Imkime e1 = xy. Seka fN (e1 ) ≤ c(e1 ) aprėžta, tad galime išrinkti poseki‘ N = N 0 → ∞,
kuriam galioja (4) bei fN (e1 ) → f (e1 ). Pakartoje‘ procesa‘ keleta‘ kartu‘, gautume poseki‘
N = N 00 → ∞ toki‘, kad galiotu‘ (4) ir
(5)

fN (e) → f (e) ≤ c(e)

su kiekvienu e ∈ E. Funkcija f (e) neneigiama, (5) nelygybė rodo, kad ji patenkina (1)
talpos sa‘lyga‘, be to, v(f ) = v. Todėl f - maksimalus srautas.
1 teorema i‘rodyta.
Maksimalaus srauto problema‘ 1956-57 m. nagrinėjo L.R.Ford’as bei D.R.Fulkerson’as. Ju‘ siūlymu remsimės digrafo minimalaus pjūvio sa‘voka. Prieš i‘vesdami ja‘,
pažymėkime
E(X, Y ) = {xy : x ∈ X, y ∈ Y },
X, Y ⊂ V.
Tai - briaunu‘, išeinančiu‘ iš X i‘ Y , aibė. Bet kokiai funkcijai g : E → R pažymėkime
X
g(X, Y ) =
g(xy)
xy∈E(X,Y )

22

Kai g(xy) = c(xy), tai c(X, Y ) reiškia aibės E(X, Y ) talpa‘.
Apibrėžimas. Jei S ⊂ V bei S̄ = V \ S - netušti poaibiai ir s ∈ S, o t ∈ S̄, tai aibė
E(S, S̄) vadinama G digrafo pjūviu, atskiriančiu viršūnes s ir t.
Pastebėkime, jog išmetus iš digrafo briaunas, priklausančias pjūviui, jokio srauto iš
s i‘ t nėra. Atvirkščiai, kai išmetus kažkokios aibės F briaunas iš E, joks srautas iš s
nepatenka i‘ t, tai aibėje F turi būti poaibis, sudarantis digrafo pjūvi‘, atskirianti‘ s nuo
t. Minimalios talpos pjūvis E(S, S̄) vadinamas minimaliuoju pjūviu. Kadangi briaunu‘
kiekis baigtinis, minimalaus pjūvio egzistavimas yra akivaizdus.
2 teorema (Maksimalaus srauto arba minimalaus pjūvio t.). Maksimalaus
srauto iš viršūnės s ‘i viršūne‘ t reikšmė lygi minimaliojo pjūvio, atskiriančio s nuo t,
talpai.
Irodymas. Pagal 1 teorema‘ egzistuoja srautas su maksimalia reikšme v. Be to, aišku,
‘
kad bet kokio pjūvio, atskiriančio s nuo t talpa yra nemažesnė už v. Todėl turime i‘rodyti,
kad egzistuoja pjūvis, kurio talpa lygi v. I‘ rodinėdami 2 teorema‘, mes pateiksime ir būda‘,
kaip toki‘ pjūvi‘ rasti.
Rekursyviai apibrėžkime poaibi‘ S ⊂ V . Tegu s ∈ S ir, jei x ∈ S bei
(T1)

f (xy) < c(xy)

arba
(T2)

f (yx) > 0,

tada prie S prijunkime y. Šis procesas baigtinis, nes turime tik baigtini‘ viršūniu‘ skaičiu‘.
I‘ sitikinkime, jog t 6∈ S. Iš tiesu‘, jei būtu‘ priešingai, aibėje S turėtume s − t taka‘
P , einanti‘ per viršūnes x0 = s, x1 , . . . , xl = t. Ju‘ incidenčioms briaunoms xi xi+1 galiotu‘
sa‘lyga
εi := max{c(xi xi+1 ) − f (xi xi+1 ), f (xi+1 xi )} ≥ min εi := ε > 0
su kiekvienu 0 ≤ i ≤ l − 1. Apibrėžkime nauja‘ funkcija‘ f ∗ : E → R+ lygybėmis:

jei e 6∈ P,

 f (e),
∗
f (e) = f (e) + ε, jei e = xi xi+1 ∈ P ir jai patenkinta (T1) sa‘lyga,


f (e) − ε, jei e = xi+1 xi ∈ P ir jai patenkinta (T2) sa‘lyga.
Nesunku i‘sitikinti, jog funkcija f ∗ - srautas. Čia Kirchhoff’o dėsnis P tako viršūnėse
tikrinamas atsižvelgiant i‘ (T1) bei (T2) atvejus. Be to, v(f ∗ ) = v + ε ir f nebūtu‘
maksimalus. Prieštara i‘rodo, kad t ∈ S̄, o aibė E(S, S̄) atskiria s nuo t.
Pastebėkime, kad f (xy) = c(xy) bei f (yx) = 0 su kiekvienu x ∈ S ir y ∈ S̄. Todėl
X
X
(6)
v = f (S, S̄) − f (S̄, S) =
f (xy) −
f (yx).
x∈S,y∈S̄

y∈S̄,x∈S

Pagal anksčiau padaryta‘ pastaba‘, pirmoji suma lygi c(S, S̄), o antroji - lygi nuliui. Vadinasi, v = c(S, S̄) ir 2 teorema i‘rodyta.
23

Bendru atveju 2 teorema nepasako, kaip rasti maksimalu‘ji‘ srauta‘, t.y. pačia‘ funkcija‘
f . Ja remiantis žinome tik maksimaliojo srauto diduma‘ v = v(f ), nes pjūviu‘ aibė yra
baigtinė, perrinkus ja‘, rastume minimalu‘ji‘ pjūvi‘ ir jo talpa‘, lygia‘ v. Taip vadinamu‘
sveikaskaičiu‘ srautu‘ (ju‘ reikšmės briaunose - sveikieji skaičiai) atveju maksimaliojo srauto
problema‘ pavyksta išspre‘sti visiškai.
3 teorema. Jei talpos funkcija c(xy) kiekvienoje briaunoje xy ‘igyja tik natūralias
skaitines reikšmes, tai egzistuoja maksimaliojo sveikaskaičio srauto radimo algoritmas.
Irodymas. Konstruojame baigtine‘ didėjančia‘ sveikaskaičiu‘ srautu‘ seka‘ f0 , f1 , . . . ,
‘
pradėdami nuo f0 ≡ 0, ir besibaigsiančia‘ maksimaliuoju srautu. Jei fi jau apibrėžtas,
tai kaip ir 2 teoremos i‘rodyme, sudarykime aibe‘ Si , imdami s ∈ Si , ir toliau prijungus
x ∈ V , prijungiame y ∈ V , jei patenkinta bent viena iš (T1) arba (T2) sa‘lygu‘. Baige‘ ši‘
procesa‘, turime, jog fi (xy) = c(xy) ir fi (yx) = 0 kiekvienam x ∈ Si bei y ∈ S̄i .
Jei t 6∈ S, tai kaip ir (6) formulėje, turėtume
v(fi ) = fi (Si S̄i ) − fi (S̄i , Si ) =

X

c(xy) = c(Si , S̄i ).

x∈Si ,y∈S̄i

Kadangi rėžio c(Si , S̄i ) negalėtu‘ viršyti ir maksimaliojo srauto f didumas v(f ), tai iš čia
išplaukia, kad fi - maksimalus srautas.
Jei dabar t ∈ S, tai kaip ir 2 teoremos i‘rodyme, srauta‘ fi galime padidinti iki fi+1 ,
pakeisdami jo reikšmes atitinkamo s − t tako briaunose. Būtent, fi+1 (xy) = fi (xy) + 1,
kai patenkinta (T1) sa‘lyga, ir fi+1 (yx) = fi (yx) − 1, kai patenkinta (T2) sa‘lyga. Tada
v(fi+1 ) ≥ v(fi ) + 1.
Procesas baigsis, nes
v(fi+1 ) ≤

X

c(xy).

xy∈E

Paskutiniam sekos nariui fp turėsime t 6∈ Sp .
3 teorema i‘rodyta.
Intuityviai aišku, kad teoremose galėjome apsiriboti becikliais maksimaliaisiais
srautais, t.y. srautais, neturinčiais funkciju‘
f (x1 x2 ) > 0, f (x2 x3 ) > 0, . . . f (xk−1 xk ) > 0, f (xk x1 ) > 0
kada x1 , . . . , xk , x1 sudaro digrafo cikla‘.
Keliu‘ šaltiniu‘ si bei keliu‘ išėjimo viršūniu‘ tj atvejai susiveda i‘ jau nagrinėta‘ atveji‘.
Pakanka prijungti viena‘ viršūne‘ s, išvesti briaunas ssi iš s i‘ duota‘sias šaltiniu‘ viršūnes si
bei prijungti bendra‘ išėjimo viršūne‘ t ir briaunas tj t. Apibrėžiant pjūvius atskiriančius
šaltinius nuo išėjimo viršūniu‘, tikslinga nauju‘ju‘ briaunu‘ nei‘jungti i‘ juos.
Maksimaliu‘ju‘ srautu‘ uždaviniai kyla ir turint apribojimus arba talpas vidinėms digrafo viršūnėms. Bet ir pastarieji susiveda i‘ srautu‘ uždavinius, kai turimi briaunu‘ talpu‘
apribojimai. Pakanka vietoje viršūnės x digrafe i‘vesti dvi viršūnes x− , x+ bei orentuota‘
briauna‘ x− x+ , o visas buvusias briaunas yx pakeisti briaunomis yx− ir xy - briaunomis
24

x+ y. Viršūnės talpa c(x) natūraliai keičiasi briaunos x− x+ talpa. Anksčiau turėtu‘
briaunu‘ talpas galime laikyti net begalinėmis, jos neturės i‘takos skaičiuojant baigtine‘
minimalia‘ pjūvio talpa‘. Pjūviu, aišku, dabar laikoma išmetamu‘ viršūniu‘ aibė, neturinti
s ir t, ir reikalaujama, kad joks srautas nepatektu‘ iš s i‘ t. I‘ vedus papildomas briaunas,
ju‘ pjūvio minimali talpa sutampa su minimalia viršūniu‘ pjūvio talpa. Tokiu būdu
iš 2 teoremos išvedamas dar vienas teiginys.
4 teorema. Tarkime, kad G - digrafas su visose viršūnėse x ∈ V , x 6= s, t,
apibrėžta talpu‘ funkcija c(x). Tada maksimalus srauto f (x), x ∈ V , iš s ‘i t didumas,
esant patenkintai sa‘ lygai f (x) ≤ c(x), lygus minimaliai viršūniu‘ pjūvio, atskiriančio s
nuo t, talpai.
12. Grafu‘ jungumas. Menger’o teorema.
Nagrinėjant srautus grafuose išryškėjo pjūviu‘ svarba. Jungiojo grafo G = (V, E)
viršūniu‘ (briaunu‘) aibės poaibis V0 (atitinkamai E0 ) vadinamas atskiriančiuoju, jeigu
grafas G − V0 (arba atitinkamai G − E0 ) jau nebėra jungus arba yra sudarytas iš vienos
viršūnės (grafas K 1 = E1 ). Atskiriantieji poaibiai, kuriu‘ visi netrivialūs daliniai poaibiai
nėra atskiriantieji, vadinami pjūviais. Akreipkime dėmesi‘, kad šiame kontekste pjūvio
sa‘voka i‘gyja nauja‘ prasme‘. Dabar pjūviai yra minimalūs atskiriantieji poaibiai.
Jei iš jungaus G grafo atėmus ne daugiau bet kokiu‘ k−1, k ≤ n−1, viršūniu‘ jis išlieka
jungiu (išlikusiu‘ viršūniu‘ kiekis yra ne mažesnis negu 2), tai G vadinamas k jungiuoju
viršūniu‘ atžvilgiu arba prasme. Šiu‘ natūraliu‘ju‘ skaičiu‘ k maksimumas vadinamas
jungumo koeficientu ir žymimas κ(G). Kitaip tariant, κ(G) = k, jei atėmus bet
kokias k − 1 viršūniu‘, grafas lieka jungiu, o išmetus k viršūniu‘, jis turi bent dvi jungumo
klases arba lygus K 1 . Aišku, pirmuoju atveju turėjo būti n ≥ κ(G) + 2, o antruoju –
κ(G) = n − 1. Be to, šiuo atveju grafas G = K n , nes priešingu atveju egzistuotu‘ bent
dvi negretimos viršūnės, todėl išmetus likusias n − 2 viršūniu‘, liktu‘ nejungus grafas.
Panašiai, elgiamės ir briaunu‘ atveju. n, n ≥ 2, eilės grafas G vadinamas k jungiuoju
briaunu‘ atžvilgiu, k ≥ 1, jei atėmus bet kokias k − 1 ar mažiau briaunu‘ jis išlieka jungus. Šiu‘ natūraliu‘ju‘ skaičiu‘ k maksimumas vadinamas jungumo koeficientu briaunu‘
atžvilgiu ir žymimas λ(G).
Taigi, jei λ(G) = k (žinoma, grafo didumas m ≥ λ(G)), tai G bus k jungus briaunu‘
atžvilgiu su kiekvienu 1 ≤ k ≤ λ(G). Pavyzdžiui, pakankamai dideliam jungiam G grafui,
neturinčiam tiltu‘, gauname, λ(G) ≥ 2. Netrivialus (n ≥ 2) jungusis grafas visada yra 1jungis. Pilnajam grafui K n gausime λ(K n ) = κ(K n ) = n−1, tačiau jungumo koeficientai
gali ir labai skirtis savo didumais. Nubrėžkime toki‘ grafa‘.
Imkime du pilnus grafus K l , neturinčius bendru‘ viršūniu‘. I‘ veskime nauja‘ viršūne‘ v
ir ja‘ sujunkime su kiekviena ankstesne viršūne. Aišku, v išmetimas iš gautojo grafo G vėl
gra‘žins pirmykšte‘ situacija‘ su dviem jungiais grafais. Tad, κ(G) = 1, tačiau λ(G) = l.
1 teorema. Jei x ∈ V ir xy ∈ E, tai
κ(G) − 1 ≤ κ(G − x) ≤ κ(G),

λ(G) − 1 ≤ λ(G − xy) ≤ λ(G).

Irodymas išplaukia iš jungumo koeficientu‘ apibrėžimu‘.

‘

25

2 teorema. Jei δ(G) - minimalus G grafo, viršūnės laipsnis, tai
κ(G) ≤ λ(G) ≤ δ(G).

(1)

Irodymas. Kai G = K n , visi trys koeficientai lygūs n − 1.
Antroji iš (1) nelygybiu‘ lengvai patikrinama. Pakanka imti δ(G) laipsnio viršūnės
incidenčias briaunas ir jas atimti iš G. Gauname viena‘ izoliuota‘ viršūne‘ ir dvi jungumo
komponentes. Todėl λ(G) ≤ δ(G).
Jei λ(G) ≤ 1, tai λ(G) = κ(G).
Tarkime, kad λ(G) = k ≥ 2. Be to, tegu G0 = G − {x1 y1 , . . . , xk yk } - nejungus
grafas. Jei G00 = G − {x1 , . . . , xk } - irgi nejungus, tai κ ≤ k, ir pirmoji iš (1) nelygybiu‘
i‘rodyta. Jei G00 dar jungus (taip būtu‘, kai x1 , . . . , xk - kraštinės viršūnės), tai δ(x1 ) ≤ k.
Iš tiesu‘, šiai viršūnei gretimos viršūnės galėjo būti x2 , . . . , xk bei viena iš G00 viršūniu‘.
Jei pastaru‘ju‘ būtu‘ buve‘ daugiau, G0 būtu‘ buve‘s jungus. Dabar iš G atėme‘ viršūnes,
gretimas x1 , o ju‘ turime k, padidiname jungumo komponenčiu‘ skaičiu‘. Vadinasi, κ ≤ k.
2 teorema i‘rodyta.
Grafo jungumas priklauso nuo taku‘ iš vienos viršūnės i‘ kita‘ skaičiaus. s − t takai
vadinami nepriklausomais, jeigu jie neturi bendru‘ viršūniu‘, išskyrus s ir t. Panašiai,
naudosime ir takus, neturinčius bendru‘ briaunu‘, nors specialaus apibrėžimo ir nei‘vesime.
Jei W - atskirianti G grafo aibė (viršūniu‘ arba briaunu‘ aibės poaibis), o viršūnės s ir
t yra skirtingose grafo G − W jungiose komponentėse, tai W vadinamas atskiriančiu
viršūnes s ir t. Mus domins mažiausias galimas tokios aibės W elementu‘ kiekis. Jis
rišasi su nepriklausomu‘ s − t taku‘ skaičiumi. Visa, kas pasakyta šiame skyrelyje, tinka ir
multigrafams.
Menger’o teorema (1927).
(I) Tegu s ir t - negretimos viršūnės. Mažiausias kiekis viršūniu‘ , atskiriančiu‘ s nuo
t, lygus didžiausiam nepriklausomu‘ s − t taku‘ skaičiui.
(II) Tegu s ir t skirtingos grafo viršūnės. Mažiausias kiekis briaunu‘ , atskiriančiu‘ s
nuo t, lygus didžiausiam neturinčiu‘ bendru‘ briaunu‘ s − t taku‘ skaičiui.
(I) teiginio ‘irodymas. Kiekviena‘ xy briauna‘ pakeiskime dviem orentuotom briaunom
xy
¯ ir yx.
¯ Be to, visoms viršūnėms, išskyrus s ir t, suteikime vienetine‘ talpa‘. Tada maksimalus srauto iš s i‘ t didumas lygus maksimaliam nepriklausomu‘ s − t taku‘ skaičiui. Pagal
9.4 teorema‘ jis lygus minimaliai viršūniu‘ pjūvio talpai. Bet pastaroji lygi atskiriančiu‘
viršūniu‘ kiekiui.
(II) teiginio ‘irodymas. Vėl apibrėžkime digrafa‘, visoms briaunoms suteikdami vienetines talpas. Dabar (II) tvirtinimas yra specialus 9.2 teorems atvejis.
Menger’o teorema i‘rodyta.
Žinoma, autorius nesinaudojo vėlesne (Fordo ir Fulkersono) teorema, todėl ir mes
pateiksime paties Menger’o samprotavimus. Jie tinka ir bendresniu multigrafu‘ atveju.
Antrasis (II) teiginio ‘irodymas. Aišku, jog maksimalus s − t taku‘, neturinčiu‘ bendru‘
briaunu‘, skaičius negali viršyti briaunu‘ kiekio atskiriančiame pjūvyje. Atvirkščiai nelygybei i‘rodyti taikysime matematine‘ indukcija‘.
Kai grafo didumas m = 1, teiginys teisingas. Tarkime, kad jis teisingas visiems
multigrafams, kuriu‘ didumai mažesni už m. Nagrinėkime jungu‘ G grafa‘, kurio didumas
‘

26

yra m, turinti‘ minimalu‘ pjūvi‘ E 0 ⊂ E, atskirianti‘ s nuo t, iš k briaunu‘. Matosi du
atvejai:
1) nei s, nei t nėra incidenčios visoms briaunoms iš E 0 ;
2) s arba t yra incidenti visoms E 0 briaunoms.
Pirmuoju atveju, grafo G−E 0 abi likusios jungiosios komponentės G1 ir G2 turi bent
po dvi viršūnes ir bent po viena‘ briauna‘. Sudarykime du naujus grafus (gal, multigrafus,
nors pradinis grafas ir būtu‘ paprastasis). Sutraukime G1 jungia‘ja‘ komponente‘, kurioje
yra s, i‘ viena‘ ši‘ taška‘ ir iš jo išveskime E 0 briaunas. Tuo būdu gavome grafa‘ F1 su
viršūniu‘ aibe {s} ∪ V (G2 ) bei briaunu‘ aibe E 0 ∪ E(G2 ). Panašiai, sutrauke‘ G2 i‘ viena‘
taška‘ t ir E 0 briaunomis ji‘ prijunge‘ prie G1 , sudarome grafa‘ F2 . Abu naujieji grafai F1 ir
F2 turi mažiau negu m briaunu‘, juose E 0 išlieka pjūviu, atskiriančiu s ir t. Jiems teisinga
indukcinė prielaida: F1 ir F2 grafe egzistuoja k taku‘ iš s i‘ t. Šiuos F1 grafo takus pratese‘
takais F2 grafe gauname k taku‘ iš s i‘ t pradiniame G grafe.
Antruoju atveju, kai s arba t yra incidenti visoms iš k bet kokio pjūvio E 0 briaunu‘,
galima laikyti, kad visos E briaunos priklauso tam tikram minimaliam pjūviui, atskiriančiam s ir t. Iš tiesu‘, priešingu atveju, galėtume atimti pjūviui nepriklausančias briaunas,
sutraukti grafa‘ ir pritaikyti indukcijos prielaida‘. Rade‘ k taku‘ mažesnėje briaunu‘ aibėje,
juo labiau juos turėsime ir didesnėje aibėje. Tuo pačiu išsimeta ir kiekvieno s − t tako
tarpinės briaunos, kurios yra neincidenčios su s ir t. Likusiame grafe kiekvienas s − t
takas turi 1 ar dvi briaunas, o viena iš ju‘ priklauso E 0 pjūviui. Atėme‘ viena‘ taka‘ iš
G likusiame grafe turėtume mažesni‘ skaičiu‘ briaunu‘ ir tik k − 1 briaunos pjūvi‘. Jam
pritaike‘ indukcijos prielaida‘, gautume k − 1 taka‘. Todėl pradiniame grafe buvo k taku‘ iš
s i‘ t.
(II) Menger’o teoremos teiginys i‘rodytas.
Dabar galime atsakyti i‘ klausima‘, kada grafas yra k jungus viršūniu‘ arba briaunu‘
atžvilgiu.
3 teorema. Grafas yra k jungus, k ≥ 2, viršūniu‘ atžvilgiu tada ir tik tada, kada
bet kokias jo dvi viršūnes jungia bent k nepriklausomu‘ keliu‘ . Grafas yra k jungus, k ≥ 2,
briaunu‘ atžvilgiu tada ir tik tada, kada bet kokias jo dvi viršūnes jungia bent k keliu‘ ,
neturinčiu‘ bendru‘ briaunu‘ .
Irodymas. Pritaikyti Menger’o teorema‘.

‘

13. Parinkimas. Hall’o teorema
Parinkimo problemos turi ir gyvenimišku‘ variantu‘. Tarkime, kad baigtinė aibė
vaikinu‘, paži‘stančiu‘ po keleta‘ merginu‘, nusprendė vesti. Keli vaikinai gali pažinoti ta‘
pačia‘ mergina‘. Kokios sa‘lygos turi būti patenkintos, kad kiekvienas iš ju‘ galėtu‘ vesti jau
paži‘stama‘ mergina‘? Panaši problema gali susidaryti, kai keletas darbininku‘, turinčiu‘ po
kelias, gal būt, bendras specialybes, pretenduoja i‘ keleta‘ darbo vietu‘. Kaip juos i‘darbinti,
kad kiekvienas dirbtu‘ pagal savo specialybe‘? Pradžioje pateiksime kombinatorini‘ vedybu‘
problemos sprendima‘, kuri‘ 1935 metais pasiūlė P.Hall’as, vėliau tai susiesime su grafais.
1 (Hall’o) teorema. Visi m vaikinu‘ , paži‘ stančiu‘ po keleta‘ merginu‘ , galės vesti savo
paži‘ stama‘ tada ir tik tada, kada bet kuris k, poaibis vaikinu‘ , 1 ≤ k ≤ m, kartu paėmus
paži‘ sta ne mažiau kaip k merginu‘ .
27

Irodymas. Būtinumas yra beveik akivaizdus. Jei kažkoks k rinkinys vaikinu‘ nepaži‘s‘
ta, bendrai paėmus, k merginu‘, tai ju‘ negalėtume apvesdinti su paži‘stamomis.
Pakankamuma‘ galime i‘rodyti matematinės indukcijos metodu. Kai m = 1, problemos sprendimas akivaizdus. Tarkime vedybu‘ problema išsprendžiama bet kokiai aibei
vaikinu‘, kuriu‘ skaičius mažesnis negu m. Pradžioje išnagrinėkime atveji‘, kai bet koks
būrys k vaikinu‘, k < m, bendrai paėmus paži‘sta k + 1 mergina‘. Išnaudodami ši‘ pažinčiu‘
rezerva‘, apvesdiname bet kuri‘ iš vaikinu‘ su jo paži‘stama, o likusiai aibei iš m − 1 vaikino
pritaikome indukcijos prielaida‘.
Tarkime dabar, kad k < m yra toks, kad k vaikinu‘ būrys kartu paži‘sta lygiai k
merginu‘. Pagal indukcijos prielaida‘ šie vaikinai gali būti apvesdinti su savo paži‘stamomis
iš šiu‘ k merginu‘. Nagrinėkime likusius m − k viengungiu‘. Bet kuris ju‘ h poaibis, h ≤
m − k, kartu paėmus turi pažinoti h iš likusiu‘ merginu‘. Priešingu atveju, kartu su jau
apsivedusiais jie būtu‘ nepažinoje‘ k + h merginu‘. Vadinasi, ir likusiai aibei m − k vaikinu‘
patenkinta teoremos sa‘lyga. Kadangi antrajai vaikinu‘ aibei irgi tinka indukcinė prielaida,
teorema i‘rodyta.
Pavaizduokime Hall’o teoremos situacija‘ dvidaliu grafu. Tarkime, kad G = (V1 ∪
V2 , E) - dvidalis grafas, t.y., E briaunos jungia tik V1 viršūnes su V2 viršūnėmis. Tarkime,
kad |V1 | ≤ |V2 |. Sakome, kad G grafe yra galimas visiškasis parinkimas, jei aibėje V2
egzistuoja poaibis V20 , toks, kad |V1 | = |V20 |, ir V1 viršūnės yra sujungtos E briaunomis
su V20 viršūnėmis. Kyla klausimas, kada egzistuoja visiškas parinkimas.
2 teorema. Tegu G = (V1 ∪ V2 , E) - dvidalis grafas, φ(A) ⊂ V2 - aibė viršūniu‘ ,
sujungtu‘ E briaunomis su A ⊂ V1 viršūnėmis. Visiškas parinkimas egzistuoja tada ir tik
tada, kada kiekvienam poaibiui A ⊂ V1 teisinga nelygybė |A| ≤ |φ(A)|.
Irodymas. Interpretuokime V1 Hall’o teoremos vaikinu‘ aibe, o V2 - merginu‘ aibe.
‘
Akivaizdu, kad 2 teorema išplaukia iš anksčiau i‘rodytos teoremos.
14. Skirtingi poaibiu‘ atstovai
Matematikai svarbi ir kita Hall’o teoremos interpretacija. Spre‘skime toki‘ uždavini‘.
Tarkime A = {A1 , . . . , Am } - aibės X netuščiu‘ poaibiu‘ šeima. Kada egzistuoja rinkinys
(x1 , . . . , xm ) skirtingu‘ X elementu‘ tokiu‘, kad xi ∈ Ai , 1 ≤ i ≤ m ? Toki‘ x-u‘ poaibi‘ iš
X vadinsime poaibiu‘ Ai skirtingu‘ atstovu‘ rinkiniu. Sutinkamas ir A transversalės
terminas.
1 teorema. X aibės poaibiu‘ šeimos A = {A1 , . . . , Am } skirtingu‘ atstovu‘ rinkinys
egzistuoja tada ir tik tada, kada
(1)

∪i∈F Ai ≥ |F |

su kiekvienu poaibiu F ⊂ {1, . . . , m}.
1 ‘irodymas. Sudarykime dvidali‘ grafa‘ G(V1 , V2 ) su V1 = A, o V2 = X. Be to,
išveskime briaunas Ai xj , jei xj ∈ Ai . Ka‘ reikštu‘ visiškas parinkimas šiam dvidaliui
grafui? Tai būtu‘ X poaibio, turinčio m elementu‘ bei sujungtu‘ briaunomis su A, radimas.
28

Akivaizdu, kad toks poaibis ir būtu‘ A skirtingu‘ atstovu‘ rinkinys. Vadinasi, 2 teorema
yra 1 teoremos išvada.
R.Rado ‘irodymas. I‘ rodymo idėja: jei (1) sa‘lyga yra patenkinta su aibe Ai , |Ai | ≥ 2,
tai ji išlieka patenkinta ir atėmus atėmus iš jos kažkuri‘ elementa‘. Šia‘ savybe‘ i‘rodysime
vėliau. Dabar iš jos išvedame teoremos teigini‘.
Pasinaudoje‘, jeigu reikia, minėta savybe keleta‘ kartu‘ ir išmėte‘ iš Ai joje minimus
elementus, vietoje visu‘ aibiu‘ Ai galime gauti vieno elemento poaibius. Bet tada (1) sa‘lyga
reiškia, kad visi like‘ Ai elementai yra skirtingi X elementai. Todėl jie sudaro ieškoma‘
skirtingu‘ atstovu‘ rinkini‘. Tuo būdu, teorema būtu‘ i‘rodyta.
Gri‘žtame prie minėtos savybės. Tarkime, kad i = 1, |A1 | ≥ 2, x, y ∈ A1 , ir bet kurio
iš ju‘ atėmimas iš A1 pakeistu‘ (1) sa‘lyga‘. Tai reiškia, jog turime du indeksu‘ poaibius
F1 , F2 ⊂ {2, ..., m} tokius, kad
(2)

|P | := ∪i∈F1 Ai ∪ (A1 \ {x}) ≤ |F1 |

ir
(3)

|Q| := ∪i∈F2 Ai ∪ (A1 \ {y}) ≤ |F2 |.

Tada
P ∪ Q = ∪i∈F1 ∪F2 Ai ∪ A1 ⊂ X
ir ji patenkina (1) sa‘lyga‘, tad
(4)

|P ∪ Q| ≥ |F1 ∪ F2 | + 1.

Be to,
(5)

|P ∩ Q| ≥ ∪i∈F1 ∩F2 Ai ≥ |F1 ∩ F2 |,

nes ir paskutinė sa‘junga tenkina (1) sa‘lyga‘. Dabar iš (2), (3), (4) ir (5) nesunkiai išvedame
prieštara‘:
|F1 | + |F2 | ≥ |P | + |Q| = |P ∪ Q| + |P ∩ Q| ≥
≥ |F1 ∪ F2 | + 1 + |F1 ∩ F2 | = |F1 | + |F2 | + 1.
1 teorema i‘rodyta.
Prisiminsime viena‘ viduramžiu‘ žaidima‘ – lotynišku‘ju‘ kvadratu‘ sudaryma‘. n eilės
lotyniškuoju kvadratu vadinama skaičiu‘ 1, 2, ..., n matrica, kurios eilutėse ir stulpeliuose yra skirtingi elementai. Ar su kiekvienu n tokia matrica egzistuoja?
2 teorema. Tegu n ≥ 1 – natūralusis skaičius. Egzistuoja n eilės lotynniškasis
kvadratas.
29

Irodymas. I‘ rodysime net daugiau: kiekviena‘ stačiakampe‘ matrica‘, vadinama‘ lo‘
tyniškuoju stačiakampiu, m × n, 1 ≤ m < n, su skirtingais elementais (iš skaičiu‘
1, ..., n) eilutėse ir stulpeliuose galime papildyti iki lotyniškojo stačiakampio su didesniu
skaičiumi eilučiu‘. Kadangi bet kuris skaičiu‘ 1, ..., n kėlinys sudaro vienos eilutės lotyniška‘ji‘ stačiakampi‘, kartodami papildymo procedūra‘, sudarytume lotyniška‘ji‘ kvadrata‘.
Tarkime, turime m × n lotyniška‘ji‘ stačiakampi‘, m < n. Kartu paėmus, šiame
stačiakampyje kiekvienas elementas pakartotas m kartu‘, po viena‘ kiekvienoje eilutėje.
Pažymėkime A1 , ..., An skaičiu‘, nepatekusiu‘ i‘ matricos stulpelius, aibes. Pastebėkime,
kad |Aj | = n − m, o kiekvienas skaičius iš X = {1, ..., n} jose pasikartoja n − m kartu‘.
Pastara‘ji‘ teigini‘ nesunku i‘žvelgti nagrinėjant matricos stulpelius, papildytus aibėmis Aj .
Taip susidarytu‘ n kėliniu‘, kuriuose bet kuris iš skaičiu‘, neviršijančiu‘ n, pasikartotu‘ n
kartu‘. Kadangi lotyniškajame stačiakampyje šis sakičius pakartotas m kartu‘, todėl visose
aibėse Aj jis pasikartoja n − m kartu‘.
Ar egzistuoja skirtingu‘ atstovu‘ rinkinys poaibiu‘ šeimai A = {A1 , ..., An }? Patikriname (1) sa‘lyga‘. Bet koks k poaibiu‘ iš Ai rinkinys turės (n−m)k, galbūt, pasikartojančiu‘
elementu‘. Jei šiu‘ poaibiu‘ sa‘junga turėtu‘ mažiau negu k skirtingu‘ elementu‘, tai bent
vienas skaičius turėtu‘ pasikartoti daugiau negu n − m kartu‘. Tai prieštarauja ankstesnei
pastabai. Tad (1) sa‘lyga yra patenkinta. Egzistuojantis skirtingu‘ atstovu‘ rinkinys gali
sudaryti nauja‘ lotyniškojo stačiakampio eilute‘. Pakartoje‘ tai keleta‘ kartu‘ baigiame 2
teoremos i‘rodyma‘.
Kai kada pasiseka išrinkti tik t ≤ m skirtingu‘ atstovu‘ rinkini‘ (daline‘ transversale‘).
Jo egzistavimo sa‘lyga šiek tiek silpnesnė.
3 teorema. Tegu A = {A1 , ..., Am } – netuščiu‘ aibės X elementu‘ poaibiu‘ šeima.
Skirtingu‘ atstovu‘ rinkinys iš t elementu‘ , priklausančiu‘ kažkurioms iš Ai aibiu‘ po viena‘ ,
egzistuoja tada ir tik tada, kai
(6)

∪i∈F Ai ≥ |F | + t − m,

F ⊂ {1, ..., m}.

Irodymas. Kai |F | + t − m ≤ 0, sa‘lyga triviali. Tegu t < m, imkime bet kokia‘
‘
aibe‘ D, |D| = m − t ir nesikertančia‘ sy X. Sudarykime aibės X ∪ D = X 0 poaibiu‘
šeima‘ A0 = {A1 ∪ D, ..., Am ∪ D}. I‘ sitikinkime, jog A dalinis t skirtingu‘ atstovu‘ rinkinys
egzistuoja tada ir tik tada, kada A0 turi skirtingu‘ X 0 atstovu‘ rinkini‘.
Iš tiesu‘, rade‘ dalini‘ rinkini‘ x1 , ..., xt galėtume prirašyti visus D elementus ir tuo būdu
gauti A0 skirtingu‘ X 0 atstovu‘ rinkini‘, jau turinti‘ m elementu‘. Atvirkščiai, turėdami
pastara‘ji‘ rinkini‘, ir išmete‘ iš jo visus D atstovus, kuriu‘ bus ne daugiau negu m − t,
gautume bent t skirtingu‘ aibiu‘ iš A atstovu‘, t. y., dalini‘ rinkini‘.
Lieka i‘sitikinti, kad (6) sa‘lyga yra ekvivalenti Hall’o teoremos sa‘lygai, pritaikytai
šeimai A0 . Tai išplaukia iš sa‘ryšio
∪i∈F (Ai ∪ D) = ∪i∈F Ai + m − t ≥ |F |.
3 teorema i‘rodyta.
30

Jei dvidaliame grafe G = G(V1 ∪ V2 , E) egzistuoja bent t briaunu‘, jungiančiu‘ skirtingas V1 viršūnes su skirtingomis V2 viršūnėmis, tai sakome, kad grafe yra dalinis t < |V1 |
parinkimas. Tegu, |V1 | = m bei kaip ir anksčiau Φ(xi ) ⊂ V2 – viršūniu‘, sujungtu‘
briaunomis su xi , aibė.
Išvada. Dvidaliame G(V1 ∪ V2 , E) grafe yra dalinis t < |V1 | parinkimas tada ir tik
tada, kada
∪i∈F Φ(xi ) ≥ |F | + t − m,

F ⊂ {1, ..., m}.

Užduotis. Prie kokiu‘ sa‘lygu‘ egzistuoja dalinis skirtingu‘ atstovu‘ iš A rinkinys
išrinktu‘ iš X0 ⊂ X?
15. (0,1) matricos
Hall’o teoremos sa‘lygos tikrinima‘ palengvina matricu‘, kuriu‘ elementai yra tik nuliai
arba vienetai, nagrinėjimas. Tokios matricos vadinamos (0,1) matricomis. Tarkime,
kad A = {A1 , ..., Am } – netuščiu‘ aibės X = {x1 , ..., xn } elementu‘ poaibiu‘ šeima. Matrica‘
M = (mij ), 1 ≤ i ≤ m, 1 ≤ j ≤ n, su mij ∈ {0, 1} ir mij = 1 tada ir tik tada, kada
xj ∈ Ai vadiname šeimos A incidenčia‘ja matrica. Dvidaliame G(V1 ∪ V2 , E) grafe,
V1 = {x1 , ...xm }, V2 = {y1 , ..., yn }, imdami kaip ir anksčiau aibe‘ V2 viršūniu‘, kurios buvo
sujungtos su xi ∈ V1 , gautume, jog mij = 1 tada ir tik tada, kai xi yj ∈ E.
(0,1) matricos elementu‘ rangu (nelygu matricos rangui!) vadiname didžiausia‘
skaičiu‘ vienetu‘, kurie yra skirtingose eilutėse ir skirtinguose stulpeliuose.
1 teorema. Aibės X poaibiu‘ šeima A = {A1 , ..., Am } turi didžiausia‘ t skirtingu‘
atstovu‘ rinkini‘ tada ir tik tada, kai jos incidenčios matricos elementu‘ rangas lygus t.
Irodymas išplaukia iš apibrėžimu‘.
‘
Kita teorema, skirta palengvinti (0,1) matricos elementu‘ rangui skaičiuoti.
2 teorema (König, Egerváry, 1931). (0,1) matricos elementu‘ rangas lygus
mažiausiam skaičiui eilučiu‘ ir stulpeliu‘ , kuriuose yra visi matricos vienetiniai elementai.
Irodymas. Tarkime, kad visi vienetiniai elementai yra r eilučiu‘ ir s stulpeliu‘, r ir s
‘
yra minimalūs, o µ = r + s. Aišku, jog elementu‘ rangas neviršija µ.
I‘ rodysime, kad matricoje yra µ vienetu‘, išsidėsčiusiu‘ skirtingose eilutėse ir skirtinguose stulpeliuose. Patogumo sumetimais, perstatykime eilutes ir stulpelius taip, kad visi
vienetai būtu‘ viršutinėse r eilučiu‘ ir paskutiniuose s stulpeliu‘. Gauname tokia‘ matrica‘:


P S
M=
.
0 Q
Čia kairiajame apatiniame kampe yra dalinė nulinė matrica, kurios matavimai yra (m −
r) × (n − s). Atkreipkime dėmesi‘ i‘ dalines matricas P ir Q. Nei viena matricos P eilutė
negali būti nulinė. Priešingu atveju visus M vienetus būtume sutalpine‘ i‘ mažiau negu r
eilučiu‘ ir s stulpeliu‘. Panašiai samprotaudami gautume, kad Q stulpeliai yra nenuliniai.
Tegu Ai , i ≤ r, - pirmu‘ju‘ n − s stulpeliu‘ indeksu‘ j, kai mij = 1, poaibis. Ši
poaibiu‘ šeima A = {A1 , ..., Ar } tenkina Hall’o teoremos sa‘lyga‘. Iš tiesu‘, jei koks nors k
31

šiu‘ poaibiu‘ rinkinys turės mažiau negu k elementu‘, tai matricoje M šias eilutes galime
pakeisti mažiau negu k stulpeliu‘ ir, tuo būdu, sutalpinti visus vienetus i‘ mažiau negu
µ eilučiu‘ ir stulpeliu‘. Pagal Hall’o teorema‘ galime išrinkti skirtingu‘ atstovu‘ rinkini‘ iš r
elementu‘. Jis nurodys skirtingus indeksus stulpeliu‘, kuriuose yra M matricos r vienetu‘,
kurie be to bus ir skirtingose eilutėse. Panašiai pasielge‘ su matrica Q, gausime dar
s vienetu‘ skirtingose M eilutėse ir stulpeliuose. Todėl M elementu‘ rangas yra lygus
r + s = µ.
2 teorema i‘rodyta.
16. Taku‘ ir ciklu‘ ilgiai
Susipažinsime su paprasčiausiais grafu‘ parametru‘ vertinimo uždaviniais. Jeigu G
grafe i‘vertine‘ jo parametra‘ f (G), sakykime per grafo eile‘ n, diduma‘ m, mažiausia‘ ar
didžiausia‘ viršūnės laipsni‘ δ bei ∆ atitinkamai, gauname, kad f (G) ≤ C(n, m, δ, ∆), čia
C - kažkokia parametru‘ funkcija, tai G grafas, kuriam būtu‘ tenkinama lygybė, vadinamas
ekstremaliuoju grafu. Ju‘ aprašymas – aktuali problema.
Pradžioje išspre‘skime uždavini‘: kiek mažiausiai reikia turėti viršūniu‘, kad G grafe
būtu‘ ciklas, kurio ilgis yra ne didesnis už g?
1 teorema. Tegu δ = δ(G) ≥ 3 - mažiausias grafo laipsnis. Jei grafo mažiausias
ciklo ilgis yra g ≥ 3, tai jo eilė n tenkina nelygybes



δ
(g−1)/2


−1 ,
kai g yra nelyginis,
 1 + δ−2 (δ − 1)


n ≥ n0 (g, δ) :=


2
g/2
 δ−2 (δ − 1) − 1 ,
kai g yra lyginis.
Irodymas. Tarkime, jog g = 2d + 1 su d ≥ 1. Imkime bet kokia‘ viršūne‘ x ir
‘
skaičiuokime viršūnes, esančias nuo jos atstumu k = 1, ..., d. Pastebėkime, kad arti nuo
x esančios viršūnes ir x gali jungti tik vienas takas. Iš tiesu‘, jei z ir x jungtu‘ du skirtingi
ne ilgesni negu d takai, tai turėtume ne ilgesni‘ negu 2d ilgio cikla‘. Dabar galime i‘vertinti
kieki‘ viršūniu‘, esančiu‘ netoli nuo x.
Visu‘ pirma, x turi ne mažiau negu δ gretimu‘ viršūniu‘. Atstumas iki ju‘ yra vienetas.
Kiekviena iš šiu‘ kaimyniniu‘ viršūniu‘ turi bent po δ − 1 savo nauju‘ gretimu‘ju‘ viršūniu‘.
Iki ju‘ atstumas nuo x yra 2, nes yra tik vienas kelias nueiti nuo x prie bet kurios iš ju‘.
Taigi iš viso yra ne mažiau negu δ(δ − 1) viršūniu‘, atstumas iki kuriu‘ yra 2.
Samprotavimus galime pakartoti, kol atstumas iki nauju‘ viršūniu‘ yra ne didesnis
už d. Taip gauname, kad viršūniu‘, iki kuriu‘ atstumas yra k ≤ d yra ne mažiau negu
δ(δ − 1)k−1 . Vadinasi, grafas turi ne mažiau negu
n ≥ 1 + δ + δ(δ − 1) + · · · + δ(δ − 1)d−1
viršūniu‘. Kadangi sudėje‘ dešinėje pusėje stovinčius geometrinės progresijos narius gauname n0 (g, δ), nelyginio g atveju teoremos teiginys yra i‘rodytas.
Tarkime, kad g = 2d yra lyginis natūralusis skaičius. Imkime dabar dvi gretimas
viršūnes x ir y. Jos abi turi ne mažiau negu 2(δ − 1) kaimyniu‘, t.y., viršūniu‘, iki kuriu‘
32

atstumas nuo x ar y yra 1. Panašiai, 2 atstumu rasime nemažiau negu 2(δ − 1)2 viršūniu‘
ir k ≤ (d − 1) atstumu – 2(δ − 1)k viršūniu‘. Ir vėl sudėje‘ pagal k = 1..., d − 1 gauname
n0 (g, δ) lyginio g atveju.
1 teorema i‘rodyta.
Iš šios teoremos žinodami grafo eile‘ bei minimalu‘ laipsni‘, galėtume išvesti grafo
ciklo mažiausio ilgio i‘verti‘ iš viršaus. Teoremos i‘rodymas nurodo būda‘, kaip nusakyti
ekstremaliuosius grafus. Tai bus tokie grafai, kad kiekviename mūsu‘ i‘rodymo žingsnyje
gausime nurodyta‘ skaičiu‘ viršūniu‘. Pvz., kai g yra nelyginis, jame turi būti δ viršūniu‘ 1
atstumu, δ(δ − 1) - 2 atstumu, ir taip toliau, δ(δ − 1)d−1 - d atstumu. Iš viso ekstremaliajame grafe turi būti n0 (g, δ) viršūniu‘. Ir toks pat vaizdas turi būti pradedant nuo bet
kokios viršūnės. Todėl toks grafas turi būti δ reguliarus. Maksimalus atstumas tarp
dvieju‘ viršūniu‘ (grafo skersmuo) turi būti d. 1 teoremos ekstremalieji grafai vadinami
Moore vardu.
I‘ rodyta teorema nusako sa‘lygas, kada grafas turi trumpo ilgio cikla‘. O kada jis turi
ilgus ciklus ar takus?
n eilės grafas vadinamas Hamiltono, jeigu jame yra n ilgio ciklas. Jame bus ir n − 1
ilgio (neuždaras) takas.
2 teorema. Tegu G - jungus ne Hamiltono grafas, turintis maksimalaus l ilgio cikla‘
(grafo apskritima‘). Tada jis turi ir l ilgio neuždara‘ taka‘ .
Irodymas. Ciklui C = x1 ...xl , l < n, nepriklauso bent viena viršūnė y, kuri jungiame
‘
grafe turi būti gretima vienai iš ciklo viršūniu‘, tarkime x1 -ai. Tada yx1 ...xl yra l ilgio
takas. 2 Teorema i‘rodyta.
Išvada. Jei jungiame ne Hamiltono grafe yra maksimalaus l ilgio takas, tai jo
apskritimo ilgis irgi neviršija l.
3 teorema. Tegu G - jungus n ≥ 3 eilės grafas ir yra patenkinta sa‘ lyga
deg(x) + deg(y) ≥ k.
Čia x ir y - bet kurios negretimos viršūnės. Jei k = n, tai grafas yra Hamiltono. Jei
k < n, tai G yra k ilgio takas ir nemažesnio už (k + 2)/2 ilgio ciklas, jei tik k ≥ 2.
Irodymas. Tarkime G nėra Hamiltono grafas, o P = x1 ...xl maksimalaus l − 1 ilgio
‘
takas. Matome, kad x1 ir xl gretimos viršūnės priklauso tik takui. Be to, jos tarpusavyje
nėra gretimos, nes priešingu atveju, paėme‘ dar jas jungiančia‘ briauna‘ gautume l ilgio
cikla‘. Tai prieštarautu‘ ankstesnei išvadai. Pastebėkime, kad P take nėra viršūniu‘ xi ir
xi+1 , tokiu‘, kad 1 ≤ i ≤ l−1 ir xi būtu‘ gretima xl , o xi+1 - viršūnei x1 . Iš tiesu‘, priešingu
atveju galėtume sudaryti l ilgio cikla‘ x1 ...xi xl xl−1 ...xi1 x1 . Taigi, aibės
Γ+ (xl ) = {xi+1 : xi xl ∈ E}

Γ(x1 ) = {xj : x1 xj ∈ E}
yra nesikertantys {x2 , ..., xl } poaibiai. Todėl

k ≤ deg(x1 ) + deg(xl ) ≤ l − 1 ≤ n − 1.
Kai k = n, tai prieštarautu‘ mūsu‘ prielaidai, kad G nėra Hamiltono grafas. Tuo
pirmasis teoremos teiginys i‘rodytas.
33

Kai k < n, jau turime P taka‘ l − 1 ≥ k ilgio. Tai yra antrasis tvirtinimas.
Ieškokime ilgo ciklo. Tegu deg(x1 ) ≥ deg(xl ). Tada deg(x1 ) ≥ k/2. Be to,
t := max{i : x1 xi ∈ E} ≥ deg(x1 ) + 1 ≥ k/2 + 1.
Kadangi x1 ...xt x1 sudaro cikla‘, ir trečiasis teiginys i‘rodytas.
4 teorema. Tegu G - n ≥ 3 eilės grafas, neturintis k ≥ 1 ilgio neuždaro tako. Tada
grafo didumas
(k − 1)n
m≤
.
2
Grafas yra ekstremalusis tada ir tik tada, kada kiekviena jo komponentė yra yra pilnasis
k eilės grafas.
Irodymas. Taikome matematine‘ indukcija‘ n atžvilgiu. Jei n ≤ k, teiginys akivaizdus,
‘
kadangi net pilnasis grafas turi tik n(n − 1)/2 briaunu‘.
Jei G grafas nėra jungusis, pritaikome indukcijos prielaida‘ kiekvienai iš jungumo
klasiu‘. Ekstremalu‘ji‘ grafa‘ gausime, kai kiekviena iš šiu‘ komponenčiu‘ yra K k grafai.
Tarkime, kad G yra jungus, n > k ir teiginys teisingas mažesnės eilės grafams. Jei
n ≥ 3, pagal 3 teorema‘ egzistuoja viršūnė x su deg(x) ≤ (k − 1)/2. Nei G grafas, nei
G − x neturi K k pilnojo pografio. Priešingu atveju, rastume k ilgio taka‘. Kadangi G − x
neeekstremalus grafas, jo m(G − x) didumas mažesnis už (k-1)(n-1)/2. Todėl
m =≤ deg(x) + m(G − x) < (k − 1)/2 + (k − 1)(n − 1)/2 = (k − 1)n/2.
4 teorema i‘rodyta.
17. Pilnu‘ju‘ pografiu‘ egzistavimas
Išreiškime žinoma‘ fakta‘, jog šešiu‘ studentu‘ draugijoje visada egzistuoja trejetas,
kurie paži‘sta vienas kita‘ arba nei vienas nepaži‘sta kito, grafu‘ teorijos terminais. Vaizduokime studentus šeštos eilės grafo viršūnėmis ir junkime briauna viršūnes, jei atitinkami
studentai pažinojo vienas kita‘. Šalia nubrėžkime grafo papildini‘, t.y., grafa‘ su šešiomis
viršūnėmis, kurios sujungtos briaunomis, jei atitinkami studentai nepažinojo vienas kito.
Uždėjus abu grafus viena‘ ant kito, gautume pilna‘ji‘ K 6 grafa‘. Taigi, minėtas faktas teigia,
kad bet kaip perskyrus pilnojo grafo briaunas i‘ dvi dalis (pvz., nudažius jas dviem skirtingomis spalvomis), arba viename, arba kitame pografyje bus pilnasis K 3 pografis. Deja,
penkiu‘ studentu‘ draugija tokios savybės jau nebeturi.
Apibendrinant galime kelti klausima‘, koks turi būti n, kad G grafe būtu‘ K s pilnasis
pografis arba jo papildinyje Ḡ iki pilnojo grafo būtu‘ K t pilnasis pografis. Mažiausias toks
n, žymimas R(s, t), vadinamas Ramsey’io skaičiumi. Aišku, kad tikslinga apsiriboti
grafais, turinčiais bent viena‘ briauna‘, todėl ateityje laikysime, kad s, t ≥ 2. Pastebėkime,
kad
R(s, t) = R(t, s), s, t ≥ 2,
o
R(s, 2) = R(2, s) = s,
34

s ≥ 2.

Iš tiesu‘, dažant K s grafo briaunas juodai ir baltai, arba visos briaunos bus juodos, arba
bent viena balta.
Ramsey’io teorema (1928). Kai s, t > 2, teisinga nelygybė
R(s, t) ≤ R(s − 1, t) + R(s, t − 1).
Be to, kai s, t ≥ 2,
R(s, t) ≤




r+s−2
.
s−1

Irodymas. Pirma‘ja‘ nelygybe‘ i‘rodinėjant, galime laikyti, kad dešinėje esantys dėmenys yra baigtiniai. Tegu n := R(s − 1, t) + R(s, t − 1) =: n1 + n2 . Dažykime K n grafo
briaunas juodai ir baltai. Reikia rasti juodai nudažyta‘ pografi‘ K s arba balta‘ pografi‘ K t .
Fiksuokime K n viršūne‘ x. Jos laipsnis deg(x) = n − 1 = n1 + n2 − 1. Todėl ši viršūnė
yra incidenti nemažiau negu n1 juodu‘ briaunu‘ arba – nemažiau negu n2 baltu‘ briaunu‘.
Simetriškumo dėka galime teigti, kad yra teisingas pirmasis atvejis. Nagrinėkime pilna‘ji‘
K n1 grafa‘, kurio viršūnės yra incidentinės x ir kurias su x jungia juodos briaunos. Jei
K n1 turi balta‘ K t pografi‘, tai pirmoji nelygybė i‘rodyta.
Priešingu atveju, pagal pažymėjima‘ n1 = R(s − 1, t), pilnasis K n1 grafas turi juoda‘
s−1
K
pilna‘ji‘ pografi‘, kuris kartu su x ir juodosiomis briaunomis, incidenčiomis x, sudaro
pilna‘ji‘ pografi‘ K s . Pirmoji teoremos nelygybė i‘rodyta.
Antra‘ja‘ teoremos nelygybe‘ i‘rodome matematinės indukcijos metodu. Kaip esame
pastebėje‘, kai s = 2 arba t = 2, antroji nelygybė virsta lygybe. Tarkime, kad s, t > 2, o
s0 , t0 ≥ 2 kita pora natūraliu‘ skaičiu‘, s0 + r0 < s + t, kuriai antroji teoremos nelygybė jau
yra teisinga pagal indukcine‘ prielaida‘. Iš anksčiau i‘rodytos nelygybės išplaukia
‘

R(s, t) ≤ R(s − 1, t) + R(s, t − 1) ≤

 
 

t+s−3
t+s−3
t+s−2
≤
+
=
.
s−2
s−1
s−1
Teorema i‘rodyta.
Ramsey’io skaičiu‘ i‘vertinimas iš apačios - žymiai sudėtingesnė problema.
16. Kitu‘ vienspalviu‘ pografiu‘ egzistavimas.
Apibendrinkime praeitame skyrelyje spre‘sta‘ uždavini‘. Tegu H1 , H2 – bet kokie
grafai. Kada nuspalvinus pilnojo K n grafo briaunas juodai ir baltai, jame rasime juoda‘
H1 pografi‘ arba balta‘ H2 pografi‘ ? Grubu‘ n i‘verti‘ iš apačios duoda jau turėta medžiaga.
Kadangi Hi , tarkim, si eiliu‘ grafai gali būti papildyti iki pilnu‘ju‘ K si grafu‘ , o ju‘
egzistavima‘ jau ištyrėme, tai suformuluoto uždavinio teigiamas atsakymas bus, jei
n ≥ R(s1 , s2 ).
Atskirais atvejais, žinant Hi savybiu‘, galima gauti geresnius i‘verčius.
Apibendrintuoju Ramsey’io skaičiumi r(H1 , H2 ) vadinamas mažiausias natūralus skaičius n toks, kad bet kaip juoda ir balta spalvomis spalvinant K n briaunas,
35

šiame grafe rasime juoda‘ pografi‘ H1 arba balta‘ pografi‘ H2 . Palygine‘ su anksčiau turėtu
Ramsey’io skaičiumi, matome, jog
r(K s1 , K s2 ) = R(s1 , s2 ).
Iš apibendrinto Rasey’io skaičiaus apibrėžimo išplaukia, kad egzistuoja r(H1 , H2 ) − 1
eilės G grafas toks, kad H1 6⊂ G ir H2 6⊂ Ḡ. I‘ rodysime pora‘ teiginiu‘, iš kuriu‘ matysis
apibendrintu‘ Ramsey’io skaičiu‘ kitimas, keičiant grafus Hi .
1 teorema. Tegu T – t eilės medis, s, t ≥ 2. Tada
r(K s , T ) ≥ (s − 1)(t − 1) + 1.
Irodymas. Nagrinėkime (s − 1)K t−1 grafa‘, t.y., (s − 1)-o K t−1 grafo sa‘junga‘. Jame
nėra T medžio. Jo papildinys iki pilnojo (s − 1)(t − 1) eilės grafo yra (s − 1)-dalis grafas,
kurio kiekviena viršūniu‘ aibė turi po t − 1 elementa‘. Jis neturi K s savo pografiu. Todėl
‘

r(K s , T ) ≥ (s − 1)(t − 1) + 1.
Teorema i‘rodyta.
Galima būtu‘ i‘rodyti, kad teoremos teiginys yra teisingas, nelygybe‘ pakeitus lygybe.
Specialiu atveju panagrinėkime galima‘ r(H1 , H2 ) didėjima‘, kai pografiu‘ Hi eilės didėja.
Lema. Teisinga nelygybė
r(G, H1 ∪ H2 ) ≤ max{r(G, H1 ) + |H2 |, r(G, H2 )}.

(1)

Čia |H| – poggrafio eilė.
Irodymas. Dešinėje (1) nelygybės pusėje esanti‘ dydi‘ pažymėkime n ir nagrinėkime
‘
K n . Jei šio grafo kažkoks nuspalvinimas juoda ir balta spalva duoda juoda‘ G pografi‘,
nelygybė i‘rodyta. Jeigu ne, tai iš nelygybės
n ≥ r(G, H2 )
išplaukia, jog egzistuoja baltas H2 . Toliau nagrinėkime K n − H2 grafa‘. Iš nelygybės
n − |H2 | ≥ r(G, H1 )
matome, kad pastarasis grafas turi balta‘ H1 . Vadinasi, pilnasis K n grafas turi balta‘
H1 ∪ H2 pografi‘.
Lema i‘rodyta.
Išvada. Su bet kokiu s ≥ 1 teisinga nelygybė
r(H1 , sH2 ) ≤ r(H1 , H2 ) + (s − 1)|H2 |.
Irodymas matematinės indukcijos metodu. I‘ sitikinkite tuo!

‘

36

2 teorema. Jei s ≥ t ≥ 1, tai
r(sK 2 , tK 2 ) = 2s + t − 1.
Irodyma‘ pradėkime pastaba. Atkreipkime dėmesi‘, kad K 2 grafas – tiesiog viena
briauna, o sK 2 – s negretimu‘ (nepriklausomu‘) briaunu‘. Teorema teigia, kad tam, kad
bet kokiame n eilės G grafe būtu‘ s nepriklausomu‘ briaunu‘, arba jo papildinyje ju‘ būtu‘
t, yra būtina ir pakankama nelygybė n ≥ 2s + t − 1.
Surasime 2s + t − 2 eilės G grafa‘, kuris neturi šios savybės. Imkime
‘

G = K 2s−1 ∪ E t−1 .
Jis neturi s nepriklausomu‘ briaunu‘. Jo papildinys lygus
Ḡ = E 2s−1 + K t−1 .
Prisimenant grafu‘ sumos apibrėžima‘, atkreipkime dėmesi‘, kad visos E 2s−1 viršūnės yra
sujungtos briaunomis su visomis K t−1 viršūnėmis. Bet viršūniu‘ skaičius yra nedidelis,
todėl ir Ḡ neturi t − 1 nepriklausomos briaunos. Taigi,
(2)

r(sK 2 , tK 2 ) ≥ (2s − 1) + (t − 1) = 2s + t − 1

ir i‘vertinys iš apačios arba minėtos sa‘lygos būtinumas i‘rodytas.
I‘ vertinimas iš viršaus remiasi tuo, kad
r(sK 2 , K 2 ) = 2s
ir nelygybe
(3)

r((s + 1)K 2 , (t + 1)K 2 ) ≤ r(sK 2 , tK 2 ) + 3,

kurios i‘rodyma‘ pateiksime vėliau.
Turėdami (3), galime pritaikyti indukcija‘ ir gauti
r((s + 1)K 2 , (t + 1)K 2 ) ≤ r(sK 2 , tK 2 ) + 3 ≤
≤ r((s − 1)K 2 , (t − 1)K 2 ) + 6 ≤
≤ r((s − t + 1)K 2 , K 2 ) + 3t = 2(s − t + 1) + 3t = 2s + t + 2.
Tuo i‘vertinys iš viršaus yra i‘rodytas.
Gri‘žtame prie (3) nelygybės i‘rodymo. Tegu n - natūralus skaičius, esantis dešinėje
jos pusėje. Pasinaudoje‘ (2) matome, jog n ≥ 2s + t − 1 + 3 = 2(s + 1) + t. Nagrinėkime
n eilės G grafus.
Jei G = K n , tai jis turi s + 1 nepriklausoma‘ briauna‘, nes s + 1 ≤ n/2. Jei G = E n ,
tai juo labiau jo papildinys, lygys K n , ju‘ turi t + 1.
37

Jeigu G nėra nei pilnas, nei tuščias grafas, tai egzistuoja trys viršūnės x, y, z tokios,
kad xy ∈ E(G) ir xz ∈ E(Ḡ). Grafe G − {x, y, z} yra n − 3 = r(sK 2 , tK 2 ) viršūniu‘.
Pagal apibendrintojo Ramsey’io skaičiaus apibrėžima‘, arba jame yra s nepriklausomu‘
briaunu‘, arba jo papildinyje ju‘ yra t. Pirmuoju atveju pridėjus xy, o antruoju atveju –
xz, gauname, kad arba pats G turi s + 1 nepriklausomu‘ briaunu‘ arba jo papildinyje ju‘
yra t + 1. Iš čia išplaukia (2) nelygybė.
2 teorema i‘rodyta.
Panašiu būdu galima i‘rodyti, jog
r(sK 3 , tK 3 ) = 3s + 2t,
jei tik s ≥ t ≥ 1, s ≥ 2.
17. Grafo viršūniu‘ spalvinimas.
Išreiškime grafu‘ teorijos terminais toki‘ uždavini‘. Reikia sudaryti laisvai pasirenkamu‘
paskaitu‘ tvarkarašti‘, kuris užimtu‘ mažiausiai laiko, bet kad kiekvienas studentas galėtu‘
išklausyti kiekviena‘ ji‘ dominančia‘ paskaita‘. Paskaitu‘, skaitymas lygiagrečiose auditorijose
neribojamas.
Tegu paskaitos žymi grafo viršūnes. Dvi viršūnes junkime briauna, jei atsiras bent
du studentai, norintys išklausyti abi šias paskaitas. Aišku, kad tokios paskaitos turi
būti skaitomos skirtingu laiku. Vaizdumo dėlei šias viršūnes nuspalvokime skirtingomis
spalvomis. Tuo būdu grafo viršūniu‘ aibė išsiskaido i‘ V1 , ..., Vk poaibius viršūniu‘, turinčiu‘
vienoda‘ spalva‘. Vieno poaibio paskaitos gali būti skaitomos vienu laiku skirtingose auditorijose, tačiau skirtingu‘ poaibiu‘ paskaitos - tik kitu laiku. Skaičius k parodys bendra‘
visu‘ paskaitu‘ trukme‘. Viršuje suformuluota užduotis reikalauja minimizuoti ši‘ k.
Bendra grafo viršūniu‘ spalvinimo problema formuluojama panašiai. Kiek reikia
skirtingu‘ spalvu‘ nudažyti G grafo viršūnėms, kad gretimosios viršūnės būtu‘ skirtingu‘
spalvu‘? Minimalus spalvu‘ kiekis χ(G) vadinamas chromačiuoju grafo skaičiumi. Formalizuojant spalvinima‘ galėtume išreikšti atvaizdžiu‘ terminais. Reiktu‘ spalvas sužymėti
skaičiais 1, ..., k ir ieškoti atvaizdžio c : V → {1, ..., k} tokio, kad viršūniu‘ aibės c−1 (i)
poaibis būtu‘ nepriklausomas, t.y., bet kokiu‘ dvieju‘ jo viršūniu‘ nejungtu‘ briauna. Chromatusis skaičius χ(G) priklauso nuo grafo struktūros. Bet kokios eilės tuščiajam grafui
jis lygus vienam, n eilės pilnajam grafui jis lygus n, o n eilės T medžiui χ(T ) = 2.
Grafo spalvinima‘ galima atlikti naudojant ”godu‘ji‘” algoritma‘. Juo remiantis,
pakanka sunumeruoti viršūnes ir spalvas, sakykime x1 , ..., xn bei c1 , ..., cn . Tiek spalvu‘
tikrai pakaks! Dažyma‘ pradedame x1 , tada dažome x2 ta pačia spalva, jei x1 nėra gretima x2 , ir – kita spalva, jei jos yra gretimos. Nudažius i viršūne‘, sekančia‘ xi+1 dažome
spalva su mažiausiu galimu indeksu taip, kad anksčiau nudažytos ir gretimos su xi+1
būtu‘ skirtingu‘ spalvu‘.
Išnagrinėkime G(V, E) grafa‘ su V = {x1 , ..., x8 } ir
E = {x1 x4 , x1 x6 , x1 x8 , x2 x3 , x2 x5 , x2 x7 , x3 x6 , x3 x8 , x4 x5 , x4 x7 , x5 x8 , x6 x7 }.
Godusis algoritmas reikalauja 4 spalvu‘, tačiau tai - dvidalis grafas, todėl jis yra dvispalvis.
Algoritma‘ galima pataisyti, kitaip sunumeruojant viršūnes. Viena‘ iš geresniu‘ numeracijos
būdu‘ gautume iš žemiau pateikiamos teoremos i‘rodymo.
38

G = G(V, E) grafo generuotuoju pografiu vadinsime pografi‘ G = G(V 0 , E 0 ),
V ⊂ V, E 0 ⊂ E, toki‘, kad i‘ briaunu‘ E 0 poaibi‘ patenka visos E briaunos, jungiančios
viršūnes iš V 0 . Šis poaibis viršūniu‘ ir jas jungiančiu‘ E briaunu‘ poaibis nusako generuota‘ji‘
pografi‘. Todėl ji‘ galime žymėti G[V 0 ]. Pografis G − {x1 , ..., xs } yra generuotasis su bet
kokiomis viršūnėmis x1 , ...xs ∈ V . Jam V 0 = V \ {x1 , . . . , xs }.
0

1 teorema. Tegu δ(H) yra minimalus pografio Hlaipsnis, k = maxH δ(H), čia
maksimumas imamas pagal visus G grafo generuotus pografius. Tada χ(G) ≤ k + 1.
Irodymas. Egzistuoja xn viršūnė su deg(xn ) ≤ k. Pažymėkime Hn−1 = G − {xn }.
‘
Šiame pografyje irgi yra xn−1 viršūnė, kurios laipsnis neviršija k. Toliau imkime Hn−2 =
G − {xn , xn−1 } ir xn−2 viršūne‘ jame. Po n žingsniu‘ gauname viršūniu‘ numeracija‘.
Pastebėkime, kad xj turi ne daugiau negu k gretimu‘ jai viršūniu‘ iš {x1 , ..., xj−1 }.
Panaudojus joms dažyti k spalvu‘ dar turime rezerve viena‘ dėl xj . Todėl k + 1 spalvos ir
pakanka.
1 teorema i‘rodyta.
Išvada. Jei ∆ = ∆(G) - maksimalus G grafo laipsnis, tai χ(G) ≤ ∆ + 1.
Patikslinkime šia‘ išvada‘.
2 teorema (R.L.Brooks, 1941). Tegu G - jungus, nepilnas ir nesutampantis su
nelyginio ilgio ciklu grafas, o ∆ = ∆(G) - maksimalus laipsnis. Tada χ(G) ≤ ∆.
Irodymas. Jei ∆ ≤ 2, grafas yra takas ar ciklas. Jo nudažymui pakanka 2 spalvu‘.
‘
toliau taikome matematine‘ indukcija‘ n atžvilgiu. Mažiems n teiginys yra betarpiškai
patikrinamas. Nauju‘ briaunu‘ i‘vedimas tik pasunkina užduoti‘, todėl gr-afa‘ galima papildyti iki ∆ reguliaraus grafo. Jame visu‘ viršūniu‘ laipsniai bus ∆. Kadangi grafas nėra
pilnas, tai ∆ < n − 1.
Pagal indukcijos prielaida‘ G − {x} yra ∆ spalvis. Raskime ”atliekama‘” spalva‘
nudažyti x viršūnei. Jei v1 , ..., v∆ gretimos jai viršūnės ir joms nudažyti pakako ∆ − 1
spalvos, galime panaudoti atlikusia‘ spalva‘.
Tarkime toliau, kad v1 , ..., v∆ – skirtingu‘ c1 , ..., c∆ spalvu‘ viršūnės. Tegu Hij – grafo
generuotas pografis, kurio viršūnės nudažytos ci ir cj spalvomis, 1 ≤ i < j ≤ ∆. Jei vi ir
vj yra skirtingose Hij pografio jungumo klasėse, tai vienos iš šiu‘ klasiu‘ viršūnes galime
perdažyti priešinga spalva (ci ar cj ) negu kad buvo. Tada vi ir vj taps vienspalvėmis.
Kaip jau buvome pastebėje‘, tada lieka viena spalva nudažyti x viršūnei.
Lieka atvejis, kad vi ir vj yra vienoje Hij jungumo Cij klasėje ir yra skirtingu‘ spalvu‘.
Tarkim, kad spalvu‘ indeksai sutampa su vi ir vj indeksais. Šias viršūnes jungia takas,
kurio tarpinės viršūnės paeiliui turi spalvas ci ar cj . Jei vi turėtu‘ dvi gretimas viršūnes,
kuriu‘ spalvos būtu‘ cj , tai jos kitos kaimynės neužimtu‘ kažkokios spalvos ck 6= ci . Tada
galėtume vi perdažyti ck spalva, palikdami ci dėl x.
Panašiai pasielkime ir tuo atveju, kai egzistuoja w ∈ Cij šalia vi vj tako. Jei u viršūnė ant tako ir gretima w, tai w spalva ir dar vienos viršūnės ant tako spalva sutampa.
Taigi, u kaimynės sutaupo viena‘ iš spalvu‘, nelygiu‘ u spalvai, kuri yra ci ar cj . Perdažius
u sutaupyta‘ja spalva, nutraukiamas vi vj takas ir vėl sugri‘žtama i‘ jau išnagrinėta‘ atveji‘,
kada vi ir vj buvo skirtingose jungumo klasėse.
Dabar jau lieka atvejis, kai Cij yra vi vj takas. Nagrinėkime kita‘ taka‘ Cjl , l 6= i.
Jei jie persikerta viršūnėje u 6= vj , taip pat cj spalvos, tai tarp u gretimu‘ viršūniu‘ yra
39

dvi ci spalvos ir dvi cl spalvos, todėl atsiras atliekama spalva jos perspalvojimui, taip
nutraukiant takus. Ir vėl turėtume jau išnagrinėta‘ atveji‘.
Taigi, turime tik takus Cij ir Cjl , turinčius bendra‘ taška‘ vj , 1 ≤ i < j < l ≤ ∆.
Grafas G nėra pilnas, tai bent vienas takas turi bent tris viršūnes. Tegu w 6= vi , vj
ir priklauso vi vj takui. Tarkime w spalva yra cj . Cil tako viršūnes galime perdažyti
priešingai, naudojant šio tako ci ir cl spalvas ir nesugadinant mūsu‘ susitaimo, jog gretimos
viršūnės turi turėti skirtingas spalvas. Ta‘ atlike‘ matome, jog w viršūnė yra ir vi vj take,
ir vl vj take, kas prieštarauja mūsu‘ taku‘ atskyrimo susitarimui.
Brooks’o teorema i‘rodyta.
Kai grafo viršūniu‘ laipsniai artimi, pvz., grafas yra reguliarus, ši teorema duoda
tikslu‘ chromačiojo skaičiaus i‘verti‘. Tačiau žvaigždiniam grafui, kai visos briaunos
išvestos iš vienos viršūnės, ji labai netiksli.
Pabandysime atsakyti i‘ klausima‘, keliais būdais galima nuspalvinti grafo viršūnes
turint 1, ..., x spalvas. Dabar x – patogus kintamojo žymuo. Pažymėkime pG (x) spalvinimo variantu‘ kieki‘. Aišku, pG (x) = 0, kai x < χ(G). Koks yra pG (x) augimas, kai x
didėja, ir be to, yra žinomos kitos grafo charakteristikos.
Lema. Tarkime, kad G – netuščias grafas ir G0 = G − e, e ∈ E, o G00 – grafas,
gautas iš G, sutraukiant e. Tada
pG (x) = pG0 (x) − pG00 (x).
Irodymas. Tegu e = uv. Visi G0 grafo viršūniu‘ nuspalvinimai, kai u ir v yra skirtingu‘
spalvu‘, sutampa su G nuspalvinimais. Ju‘ kiekis lygus pG (x). Toliau, G0 grafo nuspalvinimai, kai u ir v yra vienos spalvos, sutampa su visais galimais G00 nuspalvinimais. Šis
kiekis lygus pG00 (x). Iš šiu‘ pastabu‘ išplaukia lemos tvirtinimas.
3 teorema. Tarkime, kad G grafo eilė yra n ≥ 1 , didumas – m ≥ 0, o k ≥ 1 – jo
jungiu‘ komponenčiu‘ kiekis. Tada
‘

n

n−1

pG (x) = x − mx

+

n−k
X

(−1)i ai xn−i .

i=2

Čia ai > 0 , kai 2 ≤ i ≤ n − k.
Irodymas. Ši‘kart matematinė indukcija taikoma n + m atžvilgiu. Jei ši suma lygi 1,
‘
tai turime tuščia‘ pirmos eilės grafa‘. Jo viena‘ viršūne‘ galime spalvinti x būdu‘. Jei m = 0,
tai n = k, ir yra xn spalvinimo variantu‘.
Tarkime, kad teiginys teisingas bet kokiam grafui su mažesne negu n + m eilės ir
didumo suma. Turėdami netuščia‘ G grafa‘, ir uv ∈ E, nagrinėkime lemoje apibrėžtus
grafus G0 , bei G00 , kuriu‘ didumai lygūs m − 1. Jiems galioja indukcinė prielaida, todėl
(1)

n

n−1

pG0 (x) = x − (m − 1)x

+

0
n−k
X

(−1)i bi xn−i .

i=2

Čia k 0 - G0 grafo jungumo klasiu‘ skaičius, k 0 ≥ k; bi > 0.
40

Pastebėkime, kad G00 grafo eilė yra n − 1. Todėl indukcinės prielaidos išvada yra
lygybė
pG00 (x) = xn−1 − (m − 1)xn−2 +

(2)

n−1−k
X

(−1)i ci xn−1−i .

i=2

Kadangi k 0 ≥ k, tai (1) lygybe‘ galime papildyti nuliniais dėmenimis, o tada iš (1) atimti
(2). Tuo būdu, iš lemos gauname 3 teoremos teigini‘.
Polinomas pG (x) vadinamas chromačiuoju grafo polinomu.
18. Grafo briaunu‘ spalvinimas.
Atsakykime i‘ klausima‘, kiek reikia spalvu‘, kad gretimos briaunos būtu‘ nudažytos
skirtingai. Minimalus spalvu‘ kiekis – grafo briaunu‘ chromatusis skaičius arba chromatusis indeksas. Ji‘ žymėkime χ0 (G). Iš karto matyti, kad χ0 (G) ≥ ∆(G) := ∆. Čia
kaip ir anksčiau ∆(G) – maksimalus grafo laipsnis. Dvidaliu‘ grafu‘ atveju šis i‘vertinys
yra tikslus. I‘ sitikinkite tuo! Nagrinėkime pilna‘ K n grafa‘.
1 teorema. Jei n – nelyginis natūralus skaičius, tai χ0 (K n ) = n. Jei n – lyginis,
tai χ0 (K n ) = n − 1.
Irodymas. Nelyginio n atveju K n galime i‘sivaizduoti, kaip taisyklinga‘ n kampi‘, kurio
visos viršūnės yra sujungtos tarpusavyje. Nuspalvinkime išorines briaunas, panaudodami
visas leistinas n spalvas. I‘ sižiūrėje‘ pastebime, kad bet kokia vidinė briauna yra lygiagreti
vienai negretimai jai išorinei briaunai. Tad ir vidine‘ briauna‘ nudažykime ta pačia spalva.
Vadinasi, pakanka n spalvu‘. O gal pakaktu‘ (n − 1)-os? Pakanka pastebėti, kad viena
spalva nudažytu‘ briaunu‘ kiekis negali viršyti (n − 1)/2. Iš tiesu‘, kiekvienai nudažytai
briaunai tenka pora viršūniu‘, ir kitai ta spalva nudažytai briaunai turi tekti kita pora
viršūniu‘. Vadinasi, viena spalva nudažytu‘ briaunu‘ kiekis, padaugintas iš 2, neturi viršyti
n. Kadangi šis skaičius yra nelyginis, gauname minėta‘ nelygybe‘. Taigi, χ0 (K n ) = n.
Tegu dabar n – lyginis skaičius. K n grafa‘ pavaizduokime, kaip K n−1 + xn su xn 6∈
V (K n−1 ). Iš K n−1 grafo xj viršūnės išeina tik n−2 skirtingu‘ spalvu‘ briaunu‘, todėl viena
spalva iš leistinu‘ n − 1 yra sutaupoma. Jei tai cj spalva, tai briauna‘ xn xj ir nudažykime
ja. Taigi n − 1 spalvos pakanka. Prisimine‘, jog χ0 (K n ) ≥ ∆ = n − 1, baigiame i‘rodyma‘.
‘

Atkreipkime dėmesi‘, kad i‘rodant 1 teorema‘, buvo galima panaudoti ir K n skaidyma‘
Hamiltono takais ar ciklais, neturinčiais bendru‘ briaunu‘. Išnagrinėti pavyzdžiai rodo,
kad briaunu‘ chromatusis skaičius nedaug skiriasi nuo maksimalaus laipsnio.
2 teorema (V.G.Vizing, 1964). ∆ := ∆(G) ≤ χ0 (G) ≤ ∆(G) + 1.
Irodymas. Tarkime, kad mums jau pavyko nuspalvinti visas, išskyrus viena‘, grafo
briaunas ir panaudojome ∆ + 1 spalva‘. Ieškome galimybiu‘ nuspalvinti likusia‘ briauna‘.
Sakykime, kad spalva c sutaupoma viršūnėje x, jei visos briaunos, incidenčios x, jau
nudažytos kitomis, negu x, spalvomis. Kadangi x yra incidenti deg(x) ≤ ∆ briaunu‘,
tai visada viena iš ∆ + 1 spalvu‘ yra sutaupoma. Reikia dažyma‘ atlikti taip, kad nenuspalvintos briaunos abu galai sutaupytu‘ ta‘ pačia‘ spalva‘. O tada ja nudažyti ir pačia‘
briauna‘.
‘

41

Tarkime xy1 yra nenudažytoji briauna, o c – x viršūnėje sutaupyta spalva. Konstruokime seka‘ briaunu‘ xy1 , xy2 , ... ir seka‘ spalvu‘ t1 , t2 , ... taip, kad tj spalva būtu‘ sutaupyta yj viršūnėje, o xyj+1 briauna būtu‘ nuspalvinta tj spalva. Tarkime, jau parinkome
i seku‘ nariu‘, ti spalva yra sutaupyta viršūnėje yi . Iš x gali išeiti tik viena ti spalvos briauna xy. Jei y 6∈ {y1 , ..., yi }, tai, aišku, imtume yi+1 = y ir ti+1 pažymėtume spalva‘,
sutaupyta‘ y viršūnėje. Jei y jau buvo patekusi tarp pirmu‘ju‘ yj , 1 ≤ j ≤ i, tai seku‘
rinkima‘ nutraukiame. Taip pat pasielgiame, ir kai iš viso nėra ti spalvos briaunos xy.
Taigi pabaige‘ išrinkima‘, turime seka‘ briaunu‘
xy1 , xy2 , ..., xyh
ir spalvu‘ seka‘

t1 , t2 , ..., th

su minėtomis savybėmis. Aišku, h ≤ ∆.
Nagrinėsime i‘vairius atvejus, nulėmusius posekiu‘ rinkimo sustabdyma‘.
1) Tegu th spalva nebuvo panaudota dažant xy briaunas ir tai lėmė rinkimo proceso
nutraukima‘. Šiuo atveju xy1 nudažykime t1 spalva, xyj , 2 ≤ j < h, perdažykime tj
spalva, o xyh – th spalva. Tuo užsibrėžta‘ tiksla‘ pasiekėme.
2) Tegu th spalva‘ turėjo briauna, xyj , 2 ≤ j < h. Dabar vėl xy1 nudažome t1
spalva, xyi – ti spalva, 2 ≤ i < j, o xyj briauna‘ paliekame nenuspalvinta‘. Pažymėkime
H(c, th ) pografi‘, generuota‘ c ir th spalvu‘ briaunu‘. Jo viršūniu‘ laipsniai neviršija 2.
Taigi H(c, th ) jungiosios komponentės yra tik ciklai arba takai. x viršūnės laipsnis šiame
pografyje lygus vienam, nes tik briauna xyj−1 , dabar th spalvos, priklauso jam. Taip pat
yj laipsnis neviršija 1, nes ji nėra incidenti th spalvos briaunai. Taip pat viršūnė yh nėra
incidenti th spalvos briaunai. Vadinasi, šiame pografyje visos trys nagrinėjamos viršūnės
negali prikalusyti vienai jungumo klasei ir turime atvejus:
a) x ir yj priklauso skirtingoms H(c, th ) jungumo komponentėms. Klasėje, kurioje
yra yj , perkeiskime spalvas priešingomis. Tai nesugadina spalvinimo reikalavimo, kad
gretimos briaunos būtu‘ skirtingu‘ spalvu‘. Gauname, kad x ir yj viršūnės turi ta‘ pačia‘
sutaupyta‘ c spalva‘. Ja ir nudažome xyj .
b) x ir yh priklauso skirtingoms H(c, th ) jungumo komponentėms. Dabar ankstesni‘
perdažyma‘ prate‘skime iki h − 1 briaunos, t.y., nuspalvindami xyi ti spalva, 1 ≤ i < h,
o xyh palikdami bespalve‘. Šiam spalvinimui nenaudojamos c ir th spalvos. Vadinasi
pografis H(c, th ) nepakinta. Dabar jungumo klasėje, kurioje yra yh perkeiskime spalvas.
Gausime, kad c spalva yra sutaupyta x bei yh viršūnėse. Nudaže‘ šia spalva xyh , baigiame
teoremos i‘rodyma‘.
Teoremos i‘rodymas buvo konstruktyvus, ji‘ galima naudoti kaip algoritma‘ dažant
grafo briaunas ∆ + 1 spalvomis.
Grafo briaunu‘ spalvinimas rišasi ir su jo viršūniu‘ spalvinimu. Ta‘ rodo ir sekanti
teorema.
3 teorema. Keturiu‘ spalvu‘ teorema yra ekvivalenti teiginiui, kad χ0 (G) = 3 kiekvienam kubiniam G grafui.
Irodymas. Prdžioje pastebėkime, kad spalvinant žemėlapius, pakanka apsiriboti ku‘
biniu atveju. Pagal apibrėžima‘ tokio žemėlapio kiekviena viršūnė turi laipsni‘ lygu‘ 3. Iš
42

tiesu‘, bet kokio žemėlapio antrojo laipsnio viršūnė valstybiu‘ spalvinimui i‘takos neturi,
nes jai incidenčios briaunos neapriboja valstybės. Kai viršūnės laipsnis yra nemažesnis
už 4, apie kiekviena‘ iš ju‘, tegu x su δ(x) ≥ 4, galime apvesti maža‘ δ kampi‘, kurio viduje
yra tik ši viršūnė. ”Išvalykime” šiu‘ daugiakampiu‘ vidus. Gauname kubini‘ žemėlapi‘ su
didesniu skaičiumi valstybiu‘. Jei ji‘ mokame nudažyti, ta‘ ir atlikime. Po to sutraukime
išvestuosius daugiakampius i‘ anksčiau turėtas viršūnes išlaikydami dažyma‘.
Tarkime, jog turime kubinio žemėlapio veidu‘ nuspalvinima‘ naudojant spalvas užkoduotas simboliais
α = (1, 0),

β = (0, 1),

γ = (1, 1),

δ = (0, 0).

Jei e briauna yra tarp veidu‘, nudažytu‘ c, t iš nurodytu‘ spalvu‘, tai e spalvinkim spalva,
kurios žymuo būtu‘ c + t(mod2). Aišku, δ spalva nepasirodys šitame briaunu‘ dažyme.
Gavome kubinio grafo briaunu‘ spalvinima‘ trimis spalvomis.
Atvirkščiai, jei turime kubinio grafo nudažyma‘ trimis spalvomis α, β, γ, tai jo pografiu‘, generuotu‘ briaunu‘, turinčiu‘ spalvas α ir β, veidus galime nuspalvinti dviem spalvom.
Tai duoda šiu‘ veidu‘ pažymėjima‘ 0 ir 1. Toliau taip dažykim pografio, generuoto α ir γ
spalvu‘ briaunu‘ veidus. Ir vėl turime veidu‘ žymenis 0 ir 1. Sujunge‘ abu žymenis, galime
duoto kubinio grafo veidus sužymėti pora (.,.) iš nuliu‘ ir vienetu‘. Prisimine‘ mūsu‘ spalvu‘
kodus, gauname kubinio žemėlapio keturspalvi‘ nudažyma‘.
3 teorema i‘rodyta.
Iliustruokite pavyzdžiais.
Jei grafas nėra reguliarus, chromačiojo briaunu‘ skaičiaus ieškojimas yra sunki problema, net plokščiu‘ grafu‘ atveju. Štai vienas iš neatsakytu‘ aktualiu‘ klausimu‘:
Hipotezė. Bet kokio plokščio grafo su maksimaliuoju laipsniu ∆ ≥ 6 chromatusis
briaunu‘ skaičius lygus ∆.
Egzistuoja plokšti grafai su ∆2, 3, 4, 5, kuriems χ0 (G) = ∆ + 1. Tačiau V.G.Vizing’as
1965 mmetais i‘rodė hipotezės teigini‘, kai ∆ ≥ 8.
19. Grafo stabilieji poaibiai.
Pradėkime nuo uždavinio:
Ar galima šachmatu‘ lentoje išdėstyti aštuonias valdoves, kad jos nekirstu‘ viena kitos?
1854 metais C.F.Gauss’as jis pateikė 40 tokio išdėstymo būdu‘, nors pradžioje jis
tikėjo ju‘ esant 76. Iš tiesu‘, minėtu‘ valdoviu‘ išdėstymo galimybiu‘ yra 92.
Panaši problema, tačiau turinti neigiama‘ atsakyma‘, yra tokia:
Ar galima 64 šachmatu‘ lentos langelius padengti plokštelėmis, ju‘ nekarpant ir neužkeičiant, jei turime viena‘ kvadratine‘ , turinčia‘ 4 langelius 2 × 2, plokštele‘ ir 15 vienodu‘
plokšteliu‘ , sudarytu‘ iš keturiu‘ langeliu‘ , ”su užlenktu galu”, t.y., paskutinis langelis yra
prijungtas prie trečiojo šono ?
Abu šiuos uždavinius galima interpretuoti grafu‘ teorijos terminais. Tegu G =
G(V, E) – grafas. Poaibis S ⊂ V yra vadinamas stabiliuoju, jeigu bet kokios dvi viršūnės
x, y ∈ S yra negretimos. Pažymėkime S visu‘ stabiliu‘ poaibiu‘ aibe‘. Aišku, ∅ ∈ S, be to,
jei S1 ⊂ S ir S ∈ S, tai ir S1 ∈ S. Grafo stabiliuoju skaičiumi vadinamas dydis
α(G) = max |S|,
S∈S

43

o S su savybe |S| = α(G)| vadinamas maksimaliuoju stabiliu poaibiu.
Tegu šachmatu‘ lentos langeliai žymi grafo viršūnes, o jo briaunos jungia viršūnes,
esančias vienoje eilutėje, stulpelyje ar i‘strižainėje. Dabar matome, kad pirmasis uždavinys
reikalauja rasti aštuoniu‘ langeliu‘ stabilu‘ poaibi‘. Jis bus maksimalus. Antra‘ji‘ uždavini‘
panagrinėkite savarankiškai.
Poaibis C ⊂ V vadinamas G grafo klika, jeigu bet kurios dvi skirtingos, jei tokiu‘
yra, šio poaibio viršūnės yra gretimos. Izoliuota viršūnė sudaro vieno elemento klika‘,
tuščio grafo klikos turės tik po viena‘ elementa‘. Visada V galima išskaidyti kliku‘ sa‘junga.
Jei
V = C1 ∪ ... ∪ Ck −
tokia kliku‘ aibė, tai žymėsime

C = (C1 , ..., Ck )

ir sakysime, kad V yra išskaidyta klikomis C. Pilname grafe bet koks V skaidinys
netuščiais poaibiais duos skaidini‘ klikomis. Mus domins minimalus kliku‘ skaičius, t.y.,
dydis
Θ(G) := min |C|.
C

Skaidinys C su savybe |C| = Θ(G) - minimaliuoju skaidiniu klikomis.
Nustatykime stabilumo skaičiaus ir minimaliojo kliku‘ skaičiaus sa‘ryšiu‘.
1 teorema. Bet kokiam G grafui
(1)

α(G) ≤ Θ(G).

Be to, jei S yra stabilus poaibis, o C – skaidinys klikomis toks, kad |S| = |C|, tai S yra
maksimalus stabilus poaibis, o C – minimalus skaidinys klikomis.
Irodymas. Bet kuriam stabiliam poaibiui S ir skaidiniui klikomis C = (C1 , ..., Ck )
‘
turime
|S ∩ Ci | ≤ 1, i = 1, ..., k.
Be to, bet kuri viršūnė patenka i‘ kažkuria‘ iš aibiu‘ Ci . Todėl pagal Dirichlet principa‘
|S| ≤ |C|
ir
α(G) = max |S| ≤ min |C| = Θ(G).
Jei |S0 | = |C0 |, tai |S0 | = max |S| = α(G) ir |C0 | = min |C| = Θ(G).
1 teorema i‘rodyta.
Atskiroms grafu‘ klasėms (1) virsta lygybe. Sugalvokite pavyzdi‘!
Stabiliu‘ poaibiu‘ ieškojimas siejasi su grafu‘ parinkimo problemomis. Sakysime, kad
viršūniu‘ poaibis S yra i‘dedamas i‘ B, S, B ⊂ V , S ∩ B = ∅, jeigu dvidalis pografis,
generuotas viršūniu‘ poaibio S ∪ B, turi visiška‘ji‘ parinkima‘.
2 teorema. B ⊂ V yra maksimalus stabilus poaibis tada ir tik tada, kada bet koks
stabilus poaibis S, S ∩ B = ∅, yra ‘idedamas ‘i B.
44

Būtinumo ‘irodymas. Tegu B - maksimalus stabilus poaibis. Stabilus poaibis S bus
i‘dedamas i‘ B tada ir tik tada, kada bus patenkinta Hall’o parinkimo teoremos sa‘lyga.
Jei A ⊂ S - bet koks poaibis, Γ(A) - aibė viršūniu‘, gretimu‘ A viršūnėms, tai ši sa‘lyga
turi pavidala‘
|Γ(A) ∩ B| ≥ |A|.
Reikia i‘sitikinti, kad ši sa‘lyga yra patenkinta. Tarkime priešingai, ši nelygybė yra nepatenkinta dėl A ⊂ S. Nagrinėkime aibe‘


B1 := B \ Γ(A) ∩ B ∪ A.
Ji yra stabili ir |B1 | > |B|. Tai prieštarauja B maksimalumui.
Pakankamumo ‘irodymas. Tarkime, B nėra maksimalus stabilus poaibis, bet tada
egzistuoja kitas, sakykim, B 0 , |B 0 | > |B|. Tada
|B 0 \ B| > |B \ B 0 |
ir stabilus poaibis S = B 0 \ B negali būti i‘dedamas i‘ B.
2 teorema i‘rodyta.
20. Grafo absorbcijos skaičius.
Tipinis šios temos uždavinys yra klausimas:
Kiek šachmatu‘ lentoje reikia išdėstyti valdoviu‘ , kad kiekvienas langelis būtu‘ pasiekiamas bent vienos iš valdoviu‘ ėjimu? Šiuo atveju atsakymas yra stebėtinai mažas skaičius
- 5.
Atsakingesnė užduotis būtu‘ išdėstyti minimalu‘ kieki‘ radaru‘ taip, kad visas grafo
viršūnes kontroliuotu‘ bent vienas iš ju‘. Kontrolė reikštu‘ briaunu‘, išvestu‘ iš viršūniu‘,
kuriuose išdėstyti radarai, egzistavima‘ grafe.
Formaliai kalbant G = G(V, E) grafe viršūniu‘ A aibė vadinama absorbuojančia,
jeigu su kiekvienu x ∈ A
Γ(x) ∩ A 6= ∅.
Pagal apibrėžima‘ izoliuotos viršūnės turi priklausyti absorbuojančiai aibei.
Pažymėkime A visu‘ absorbuojančiu‘ aibiu‘ šeima‘. Aišku, jog V ∈ A ir
A ∈ A, A ⊂ A0

⇒ A0 ∈ A.

Dydis
β(G) = min |A|
A∈A

vadinamas grafo absorbcijos skaičiumi, o pati aibė A su savybe |A| = β(G) - minimalia
absorbuojančia aibe.
Teorema. Jei G = G(V, E) grafo eilė yra n, m - jo didumas ir ∆(G) - maksimalus
laipsnis, tai
n − m ≤ β(G) ≤ n − ∆(G).
45

Irodymas. Tegu A - minimali absorbuojanti aibė, t.y., |A| = β(G). Kiekviena viršūnė
‘
iš poaibio V \ A yra sujungta su A viršūne bent viena briauna. Tad,
n − |A| = |V \ A| ≤ m.
Iš čia išplaukia kairioji teoremos nelygybė.
Tegu x ∈ V yra ∆(G) laipsnio viršūnė, o Γ(x) - x gretimu‘ viršūniu‘ poaibis. Pastebėkime, jog aibė A = V \ Γ(x) yra absorbuojanti. Todėl
β(G) ≤ |A| = n − ∆(G).
Teorema i‘rodyta.
21. Grafo branduolys.
Susipažinsime su sa‘voka, kilusia lošimu‘ teorijoje. Grafo G = G(V, E) branduoliu
vadinsime aibe‘ S ⊂ V , jeigu ji yra kartu ir absorbuojančia, ir stabilia. Pagal pastaru‘ju‘
aibiu‘ apibrėžimus S branduolys tenkina sa‘lygas:
(1)

x∈S

⇒

Γ(x) ∩ S = ∅,

(2.)

x 6∈ S

⇒

Γ(x) ∩ S 6= ∅.

Nustatykime branduolio kriteriju‘. S aibės funkcija φS , apibrėžta lygybėmis

1, kai x ∈ S,
φS (x) =
0, kai x 6∈ S,
vadinama jos charakteristine funkcija. Ateityje susitarkime, kad maxy∈∅ φS (y) = 0.
Teorema. Tam, kad S ⊂ V aibė būtu‘ branduolys, yra būtinma ir pakankama, kad
jos charakteristinė funkcija φS tenkintu‘ sa‘ lyga‘
φS (x) = 1 − max φS (y),
y∈Γ(x)

x ∈ S.

Irodymas. Jei S yra branduolys, tai remiantis (1) sa‘lyga, gauname

‘

φS (x) = 1

⇒

x∈S

⇒

max φS (y) = 0.

y∈Γ(x)

Panašiai, remiantis (2) sa‘lyga, gauname
φS (x) = 0

⇒

x 6∈ S

⇒

max φS (y) = 1.

y∈Γ(x)

Tarkime teoremos sa‘lyga yra patenkinta. Tada
x∈S

⇒

φS (x) = 1

⇒

x 6∈ S

⇒

φS (x) = 0

⇒

max φS (y) = 0

⇒

Γ(x) ∩ S = ∅

max φS (y) = 1

⇒

Γ(x) ∩ S 6= ∅.

y∈Γ(x)

ir
y∈Γ(x)

Taigi patikrinome (1) ir (2) sa‘lygas, S yra branduolys.
Teorema i‘rodyta.
Sugalvokite pavyzdžiu‘ grafu‘, kuriu‘ branduoliai turi ta‘ pati‘ skaičiu‘ viršūniu‘, kuriu‘
branduoliai yra vieninteliai.
46