MEGOLDÁS:

Vegyünk egy tetszőleges embert, legyen ő A₁. Legyen egy ismerőse A₂, legyen továbbá A₂-nek egy A₁-tol különböző ismerőse A₃, és általában legyen A_k+1-nek egy A_k-tól különböző ismerőse A_k+2. Ilyen van, hiszen mindenkinek van legalább két ismerőse. Így kapjuk az embereknek egy A₁A₂…A_m… végtelen sorozatát, ahol mindenki ismeri az előtte és utána következőt. Ez a sorozat azonban egy idő után biztosan tartalmaz ismétlődést, hiszen a társaságnak csak véges sok tagja van. Legyen A_m+1 az első olyan ember, aki már szerepelt a sorozatban előbb is, mondjuk az n-edik helyen: A_m+1=A_n (n<m). Ekkor A_n-et,  A_n+1-et,  A_n+2-et, …, A_m-et ilyen sorrendben leültetve az asztal köré mindenki két ismerőse között fog ülni. (Ez igaz A_m-re is, mert A_m+1=A_n.)

A feladatot és megoldását átfogalmazhatjuk gráfelméleti nyelvre.

Az 1. feladat gráfelméleti nyelven a következőképpen szól:

Vagy átfogalmazva az állítást:

Ha egy körmentes gráfból elhagyjuk az izolált pontokat, akkor is körmentes marad. Ha nem csupa izolált pontból áll, akkor marad még pont benne, s ezek között is kell lennie izolált pontnak vagy elsőfokú pontnak. De az izolált pontokat már elhagytuk, tehát van elsőfokú pont a gráfban. A következő állítást kapjuk:

A feladat állítását teljes indűkcióval bizonyítjuk.

n=1 esetén a gráfnak nincs éle, n=2 esetén a gráfnak legfeljebb egy éle van.

Tegyük fel, hogy n–1 pontú gráfokra már tudjuk az állítást és legyen G egy n pontú egyszerű, körmentes gráf. Az 1’ állítás szerint G-ben van egy legfeljebb elsőfokú pont (különben G nem körmentes), legyen ez a pont x. Hagyjuk el a G gráfból az x pontot és a belőle (esetleg) induló élt.

A maradó n–1 pontú gráfban továbbra sincs kör, így legfeljebb n–2 éle van az indukciós feltevés szerint. Ha ehhez hozzávesszük az x-bol induló egyetlen élt (ha van egyáltalán), megkapjuk, hogy G-nek legfeljebb n–1 éle van.

AZ (A) ÁLLÍTÁS BIZONYÍTÁSA:

Tegyük fel, hogy a gráf A és B pontja között két különböző út indul. Ha e két útnak csak a végpontjaik, A és B a közös pontja, akkor a két utat összerakva máris találtunk egy kört. Ha van a két útnak közös belső pontja is, akkor induljunk el az egyik úton A-ból B-be és menjünk addig, amíg először találunk a másik útnak belső pontjára. Legyen ez a pont C. Forduljűnk vissza a C pontból a másik úton A-ba. Útközben biztosan nem fogjuk az első AC út pontjait érinteni, mert akkor nem C volna az első közös pont. Tehát egy körhöz jutunk.

(B) ÁLLÍTÁSAINAK BIZONYÍTÁSA:

Az első állításhoz elég meggondolnunk, hogy a két pont közötti legrövidebb sétában nem lehet pontismétlődés, hiszen ha egy pontot többször is érintenénk, akkor a két érintése közötti részt nyugodtan elhagyhatnánk a sétánkból, s továbbra is a két pont közötti sétát kapnánk. (Az ábrán – ahol az élek sorrendjét számozással jelöltük – a kékkel jelölt „hurok” például elhagyható, de a többi él már nem.) Beláttuk tehát, hogy ha két pont között van séta, akkor a legrövidebb séta egyben út is.

Valójában egy kicsit többet is beláttunk. Legyen a két végpont A és B és vegyünk egy tetszőleges sétát e két pont között. Ha tekintjük azokat a sétákat A és B között, amelyek csak ennek a sétának az éleit tartalmazzák, és kiválasztjuk közülük a legrövidebbet, már az is biztosan út. Ugyanis a fenti eljárással mindaddig hagyhatunk el az eredeti sétából „hurkot”, amíg megszűnnek a pontismétlődések.

Ebből a megjegyzésből viszont már következik (B) második állítása: tekintsük azt a sétát A és C között, amelyet az A-t B-vel összekötő útból, majd a B-t C-vel összekötő útból teszünk össze. Az előbb mondottak szerint A és C közötti út lesz a legrövidebb olyan séta, amely csak ennek a sétának az éleiből áll (tehát csak a két út éleit „használja”).

A második állítás bizonyítására bemutatunk egy másik bizonyítást is, amely egyrészt nagyon hasonlít az előző bizonyításra, másrészt nagyon hasonló a 3. feladat bizonyításához is. Induljunk el az A-ból B-be vezető úton és menjünk addig, amíg az első olyan ponthoz nem érünk, amely rajta van a B-t C-vel összekötő úton is. (Legkésőbb a B pont ilyen lesz.) Ebből a pontból folytassuk az utunkat a B-bol C-be vezető úton C-ig. Útközben biztosan nem találkozunk már érintett ponttal, hiszen D volt az első közös pont. Így kaptunk egy A-t C-vel összekötő utat.

BIZONYÍTÁS:

Nyilvánvaló, hogy ha egy gráfra teljesül az összefüggőség első definíciója (azaz bármely pontból bármely pontba vezet út), akkor bármely pontja megfelel X-nek a második definícióban: bármely X pontjából vezet út az összes többi ponthoz. Másrészt ha a gráfban van egy X pont, amelyből az összes többi pontba vezet út, akkor legyen Y és Z a gráf két további pontja. X-bol vezet út Y-ba és vezet út Z-be, tehát (B) szerint Y és Z között is vezet út (X játssza B szerepét, Y és Z játssza A és C szerepét).

A (C) ÁLLÍTÁS BIZONYÍTÁSA:

A gráf valóban pontosan akkor fa, ha bármely két pontja között pontosan egy út vezet. Ugyanis pontosan akkor fa, ha összefüggő és körmentes. Az összefüggőség megköveteli, hogy bármely két pontja között vezessen út, a körmentességből pedig (A) szerint következik, hogy nem vezethet két út. Másrészt ha egy gráfban bármely két pont között pontosan egy út vezet, akkor nyilván összefüggő és kört sem tartalmazhat, hiszen a kör bármely két pontja között maga a kör két utat jelent.

A (D) ÁLLÍTÁS BIZONYÍTÁSA:

Legyen először a gráf összefüggő és bontsuk a gráf csúcsainak halmazát két nem üres részre: legyen a két rész A és B. Legyen a és b a két részhalmaz egy-egy csúcsa. Az összefüggőség miatt vezet közöttük út. Az út kezdőpontja és végpontja különböző részhalmazokban van, tehát van olyan él is, amelynek egyik végpontja az egyik halmazban van, másik végpontja a másikban. Ezt akartuk bizonyítani.

A (D’) ÁLLÍTÁS BIZONYÍTÁSA:

Ha van két nem üres ponthalmaz, A és B, amelyek között nem fut él, akkor a gráf nem lehet összefüggő, mert A semelyik pontjából nem vezet út B egyik pontjába sem. Ha viszont a gráf nem összefüggő, akkor van két pontja, amely között nem vezet út. Legyen ez a két pont a és b. Ekkor az a-ból úttal elérhető pontok halmaza és a komplementere sem üres (az előbbibe mindenképp beletartozik a, az utóbbiba b). E két halmaz között pedig nem vezet él.

AZ (E) ÁLLÍTÁS BIZONYÍTÁSA

először egy eljárást definiálunk, amely a G fa egy G’ részgráfját választja ki:

I. ELJÁRÁS:

1. LÉPÉS:

Válasszűk ki a G gráf egy tetszőleges x₁ pontját, ez a pont pontja lesz a G’ részgráfnak.

2. LÉPÉS:

Ha a gráfnak x₁-en kívül nincs több pontja, befejezzük az eljárást.

Ha a gráfnak x₁-en kívül is van pontja, akkor keressünk egy olyan x₂ pontot, amely össze van kötve x₁-gyel. Ilyen pontnak kell lennie, különben a gráf nem volna összefüggő. Az x₂ pontot és az x₁x₂ élt beválasztjuk a G’ részgráfba.

k. LÉPÉS:

Tegyük fel, hogy az x₁, x₂, …, x_k–1 pontokat már kiválasztottuk.

Ha az {x₁, x₂, …, x_k–1}=A halmaz tartalmazza a G gráf összes pontját, akkor befejezzük az eljárást.

Ha az {x₁, x₂, …, x_k–1}=A halmaz nem tartalmazza a G gráf összes pontját, akkor (D) szerint van olyan él, amely A és a gráf többi pontja között fut, vagyis egy A-beli x_i pontot köt össze egy A-n kívüli x_k ponttal. Az x_k pontot és az x_ix_k élt beválasztjuk a G’ részgráfba. (Az alábbi ábrán i=2 és k=8.)

Ha G-nek n pontja van, akkor az eljárás pontosan az n-edik lépésben ér véget és az első lépés kivételével minden lépésben a G gráf egy új élét választja ki és veszi hozzá G’-höz. Ebből következik:

Az I. eljárással kapott G’ részgráf a G gráf összes pontját tartalmazza. Ha G-nek n pontja van, akkor G’-nek n–1 éle van.

MEGOLDÁS:

a): Az I. eljárás minden lépésben x₁ egy szomszédját választja ki, vagy egy már kiválasztott szomszédjának szomszédját (x₁ „másodszomszédját”), vagy x₁ egy szomszédjának „másodszomszédját (x₁ „harmadszomszédját”), stb. Vagyis minden lépésben olyan pontot választ ki, amelybe vezet út x₁-bol. Tehát G’ teljesíti az összefüggőség második definícióját. Másrészt minden lépésben egy újonnan választott pontot kötünk össze egy már korábban kiválasztottal, ezért egyetlen beválasztott él sem zárhat be kört a már korábban beválasztott élekkel. A G’ részgráf tehát körmentes és összefüggő, tehát fa.

b): Egy összefüggő gráf bármely két pontja között megy út. Ha tehát két még össze nem kötött pontját összekötjük, akkor ez az él kört zár be az él két végpontját már eddig is összekötő úttal.

c) Ha a G gráf nem egyezik a G’ részgráfjával, akkor van olyan éle, amely nem szerepel G’-ben. De akkor b) szerint ez az él kört zár be a G gráfban. Tehát G nem lehet fa. Ha tehát G fa, akkor megegyezik a G’ részgráfjával.

(E) ÁLLÍTÁS BIZONYÍTÁSÁNAK befejezése:

Az (E) állítás bizonyítása most már azonnal következik a 8. feladat állításaiból: ha G n pontú fa, akkor valóban n–1 éle van, hiszen megegyezik azzal a G’ részgráffal, amelyet az I. eljárás kiválaszt. Márpedig G’-rol tudjuk, hogy n–1 éle van.

MEGOLDÁS:

Ha G összefüggő, akkor minden pontja elérhető a gyökérből induló úttal, tehát az I. eljárás a gráf minden pontját ki fogja választani. Vagyis minden összefüggő gráfra működik az eljárás. Ha G nem összefüggő, akkor az eljárás nem minden pontot ér el.

Ha G összefüggő, akkor G-nek egy olyan G’ részgráfját választja ki, amely G összes pontját tartalmazza, összefüggő és a pontszámnál eggyel kevesebb éle van (az első lépésben csak egy pontot választ ki, a további lépésekben minden ponttal együtt pontosan egy élet is kiválaszt), tehát fa.

DEFINÍCIÓ:

Ha az összefüggő G gráf egy G’ feszítő részgráfja fa, akkor G’-t G feszítő fájának, favázának vagy kaptafájának nevezzük.

MEGOLDÁS:

Egy kör bármely két szomszédos pontjának távolsága egy, viszont a favázában egy él nem fog szerepelni, ennek két végpontja közötti távolság tehát a favázban nagyobb lesz egynél. Nyilvánvaló, hogy ha az összefüggő gráf nem körmentes, akkor mindig lesz olyan éle, amely nem szerepel a favázban és ennek végpontjai között a favázban egynél nagyobb lesz a távolság.

Tehát ha egy összefüggő gráf nem körmentes (nem fa), akkor nincs a feladat feltételének megfelelő, azaz „távolságtartó” faváz, vagyis olyan faváz, amely a gráf bármely két pontja között megtartja a távolságot.

MEGOLDÁS:

Tegyük fel először, hogy az I. eljárásban x_k-t mindig úgy választjuk, hogy a lehető legkisebb indexű kiválasztott ponttal legyen összekötve. Másképp fogalmazva ez a következőt jelenti:

II. ELJÁRÁS:

1. LÉPÉS:

Kiválasztjuk x₁-et, ez lesz a fa gyökere, és ezt tekintjük a fa első szintjének.

2. LÉPÉS:

Ha nincs több pontja a gráfnak, az eljárást befejezzük.

Ha van még pont a gráfban, akkor x₁-nek vannak szomszédai, mert a gráf összefüggő. Kiválasztjuk x₁ szomszédait – ez lesz az első szint. Behúzzuk a második szint pontjait a gyökérrel összekötő éleket.

3. LÉPÉS:

Ha a gráfnak már minden pontját kiválasztottuk, akkor az eljárást befejezzük.

Ha nem minden pontot választottunk még ki, akkor (D) állítás szerint a kiválasztott pontok és a még ki nem választott pontok között fut él, mert a gráf összefüggő.

Végigmegyünk az első szint pontjain, és mindegyiknek kiválasztjuk azokat a szomszédait, amelyek még nincsenek kiválasztva. Ezek alkotják a második szintet. A második szint a fent mondottak szerint nem üres. A második szinten azok a pontok vannak, amelyeknek van szomszédja az első szinten, minden második szintű pontot összekötünk egy első szintű szomszédjával (például azzal, „amelyik miatt” kiválasztottuk).

k. LÉPÉS:

Ha a gráfnak már minden pontját kiválasztottuk, akkor az eljárást befejezzük.

Ha nem minden pontot választottunk még ki, akkor (D) állítás szerint a kiválasztott pontok és a még ki nem választott pontok között fut él, mert a gráf összefüggő.

Általában a k+1-edik szintet azok a pontok alkotják, amelyek az k-adik szinten levő pontok szomszédai és még nem szerepelnek valamelyik korábbi szinten. A k+1-edik szint a fent mondottak szerint nem üres. Ezen a szinten azok a pontok vannak, amelyeknek van szomszédja az előző, k-adik szinten, minden k+1-edik szintű pontot összekötünk egy k-adik szintű szomszédjával (például azzal, „amelyik miatt” kiválasztottuk).

Az eljárás akkor ér véget, amikor a gráf minden pontját besoroltuk valamelyik emeletre.

Vagyis az x₁ gyökerű szélességi faváz megoldása a 11. feladatnak.

MEGOLDÁS: Az adott ponthoz tartozó szélességi faváz nem feltétlenül egyértelmű: a szintek egyértelműek, de az élek nem: hogy melyik élek fognak szerepelni a favázban, ez függ attól, hogy a soron levő pont még nem szereplő szomszédait milyen sorrendben írjuk be a favázba. Ha például veszünk egy négy hosszú kört, amelynek pontjai sorban 1, 2, 3, 4, akkor az 1-es ponthoz tartozó szélességi faváz első szintjén a 2-es és a 4-es pont fog szerepelni, a második szintjén a 3-as. De attól függően, hogy a 2-es és 4-es pontot ilyen sorrendben vettük be a gráfba, vagy fordítva, a 3-as pont a 2-es, illetve a 4-es ponthoz is csatlakozhat a szélességi favázban. (A két ábra mutatja a két lehetőséget, a szaggatottan behúzott él éle a gráfnak, de nem éle a faváznak.)

                 

MEGOLDÁS:

Bármely ponthoz tartozó bármely szélességi faváz megfelel. Ez következik a szélességi faváz definíciójából. Tegyük fel ugyanis, hogy az xy él alacsonyabb szintű végpontja – legyen ez x – az i-edik szinten van és tegyük fel, hogy y magasabb szintre került. De ekkor biztosan felkerült az i+1-edik szintre, hiszen erre a szintre az összes olyan pontot feltesszük, amely (legalább) egy i-edik szintű ponttal össze van kötve.

MEGOLDÁS:

Igaz, ez következik (B)-bol.

MEGOLDÁS:

a) A teljes gráf átmérője nyilván 1 és 1 gráf átmérője nyilván pontosan akkor 1, ha a gráf teljes gráf.

b) A csillagban a gyökértől minden pont 1 távolságra van, viszont bármely két másik pont 2 távolságra van. Tehát ha a csillagnak legalább 3 pontja van, akkor átmérője 2. A 2 pontú csillag átmérője 1.

c) Az 5 hosszú kör átmérője 2(!), mert bármely két nem-szomszédos pontját egy 2 és egy 3 élu út köti össze:

Ugyanígy a 7 hosszú kör átmérője 3 és általában a 2k+1 hosszú köré k. A 2k hosszú köré szintén k (a négy hosszúé ketto, a hat hosszúé három, stb.).

d) Egy út átmérője nyilván a két végpontjának távolsága, vagyis egy út átmérője megegyezik az út hosszával.

e) A tetraédek élgráfja 4 pontú teljes gráf, és a teljes gráfok átmérője a) szerint 1. A kocka élgráfjának az átmérője 3: két szemközti csúcs távolsága ugyanis ennyi. Bármely két, nem szemközti csúcs távolsága ennél kevesebb: 1 vagy 2.

f) Az oktaéder élgráfjában minden pont pontosan egy másikkal, a szemköztivel nincsen összekötve. Ettől tehát kettő távolságra van. Az oktaéder élgráfjának átmérője ezek szerint 2.

g) Az ikozaéder élgráfjában minden pontnak 5 szomszédja van, ezek mindegyike további két ponttal van összekötve, de összesen öttel, tehát minden pontnak 5 másodszomszédja van. Marad egy pont, ami ben is minden ponttal van egy szemközti pont, ez 3 távolságra van tole, így az ikozaéder élgráfjának átmérője 3. (Az ábrán a legbelső pont körüli ötszög pontjai az első szomszédok, a külső ötszög pontjai a másodszomszédok, a szemközti csúcsot, amely a külső ötszög pontjaival van összekötve, az ábrán nem tüntettük fel: ez van a legbelső ponttól 3 távolságra.)

h) Ha egy fának 5 emelete van a gyökéren kívül, akkor bármely pontjából 5 élu úttal elérhető a gyökér, s így bármely két pontja között legfeljebb 10 élu út megy, tehát az átmérő legfeljebb 10. A 10 élu (11 pontú) út a példa rá, hogy van olyan fa, amelyben pontosan 10 az átmérő és 5 emelet van.

BIZONYÍTÁS:

A bizonyításhoz az egyszerűség kedvéért bevezetjük egy gyökeres fa magasságának fogalmát: ez a gyökértől legtávolibb pont távolsága a gyökértől. Vagy másképp: a fa (gyökértől különböző) szintjeinek száma.
Minden x ponthoz megkeressük az x gyökerű szélességi favázat. Ennek magassága az x-tol legtávolabbi pont távolsága. Jelöljük ezt t(x)-szel. Ha minden x-re meghatározzuk t(x)-et, akkor a gráf átmérője a legnagyobb t(x) lesz. Márpedig t(x) meghatározásához elég p(n) idő, és n pont van, ezért az összes t(x) meghatározásához is elég np(n) idő, ami szintén polinom. A maximum meghatározása minden x-nél csak plusz egy lépés: összehasonlítjuk azt, amit az aktuális t(x)-re kaptunk, az eddigi legnagyobb értékkel és a kettő közül a nagyobbat tároljuk.

MEGOLDÁS:

Egyáltalán nem magátólértetődo, hogy ilyen faváz mindig létezik. Persze, ha a gráf fa, akkor megfelel. Ha a gráf teljes, akkor bármely olyan út megfelel, amely a gráf minden pontját tartalmazza (az ilyen utat, ha van, a gráf Hamilton-útjának nevezzük). Érdemes ezt összevetni azzal, hogy milyen favázat ad a körkörösen haladó keresés ugyanennél a gráfnál. Itt egy csillagot kapunk, ami már sejtetni engedi, hogy mikor kaphatunk a második kérdés feltételét kielégítő favázat. Nyilvánvaló az is, hogy ha a gráfnak van Hamilton-útja, akkor ez az út megfelelő faváz. Általában is nyilvánvaló, hogy ha a gráfnak van Hamilton-útja, akkor bármely Hamilton-út megfelel a célunknak, ha egyik végpontja a gyökér. Hiszen egy ilyen Hamilton-útban bármely két pont közül az egyik a másik utódja. Vizsgáljuk meg még azt a gráfot, amelyben három háromszög illeszkedik egy pontban:

                                    

Ha az 1-es pontot választjűk gyökérnek, akkor a szélességi faváz egy csillag lesz, s ez nyilván nem felel meg, hiszen a kimaradó élek mindegyike azonos szintű, tehát nem összehasonlítható pontok között fut. Nézzük, mi lehet jó. Nyilvánvaló, hogy például a 2-es és 3-as pont közül egyik az első emeletre, közvetlenül a gyökér fölé fog kerülni, feltehetjük, hogy a 2-es kerül az első emeletre. De akkor a 3-as pontnak a második emeletre kell kerülnie, különben az első emeletre kerülne, s akkor a 23 él nem előd és utód között futna. Hasonlóan a 4-es és 5-ös pont közül is az egyik az első emeletre kerül, a másik a másodikra, és a 6-os és 7-es pontra is ugyanez áll. A faváz most így néz ki:

                                    

Általában is világos, hogy ha a keresés során eljutunk egy xyz… út xy éléhez, tehát sorra került x és utána bevettük az xy élt is a fába, akkor z-t y utódjaként kell a fához illesztenünk. A legegyszerűbb az, ha y szomszédjaként vesszük sorra. Vagyis itt a szélességi („körkörös”) kereséssel ellentétben célszerű mindig „előre törni”. Olyan algoritmussal érdemes tehát próbálkoznunk, amelyik mindig előre megy, amíg ez lehetséges. Ha valahol elakadunk, akkor visszakozunk, de akkor is csak a lehető legkevesebbet, és onnan próbálunk meg előre törni új pontok felé. Ez lesz a mélységi keresés. Ha egy pontot elérünk, nem az összes szomszédja érdekel minket, hanem csak egy.

A III. ELJÁRÁS tehát a következő: Ha elérünk egy y ponthoz, keresünk egy olyan szomszédját, amelyet még egyetlen korábbi lépésben sem értünk el, ha van ilyen, ezt is felvesszük az elért pontok közé az y-ból hozzá vezető éllel együtt, és ez lesz az új y, majd ettől a ponttól folytatjuk a keresést. Akkor akadunk meg, ha olyan y ponthoz érünk, amelynek már minden szomszédját korábban elértük. Ekkor visszamegyünk ahhoz a ponthoz, ahonnan y-t elértük, és onnan próbálkozunk: ez (vagyis y fabeli „apja”) lesz az új y.

Az algoritmust ezzel megadtuk. Megadjuk valamivel formálisabban is:

1. LÉPÉS:
Kiválasztunk egy x₁ pontot, ez lesz a fa gyökere. Legyen y=x₁. (y változik az eljárás során!)

2. LÉPÉS:
Keressük meg y-nak egy szomszédját. Ha ilyen pont nincs, akkor az eljárást befejezzük (ekkor a gráf egy pontból állt).
Ha y-nak van szomszédja, válasszűk ki egy szomszédját, legyen ez x₂, a faváznak éle lesz az yx₂= x₁x₂ él és most y=x₂.

k. LÉPÉS:
Tegyük fel, hogy már kiválasztottuk az x₁,x₂,…,x_k–1 pontokat és y=x_i. Járjuk végig y szomszédait, amíg nem találunk olyat, ami még nem szerepel a kiválasztott x_j-k között.

1. eset: Ha y-nak van ilyen szomszédja (amely tehát még nem szerepel a kiválasztott x_j-k között), akkor az előszörre talált ilyen pont lesz x_k, a favázba beillesztjük az yx_k=x_ix_k éllel együtt és y=x_k.

2. eset: Ha y-nak minden szomszédja szerepel a kiválasztott x_j pontok között, akkor megkeressük y apját az x_j pontok között, ez lesz az új y, s erre ismételjük az eljárást. Egyetlen esetben nincs y-nak apja: ha y a gyökér. Az eljárás tehát akkor ér véget, ha visszaérünk a gyökérhez, és a gyökérnek már minden szomszédja szerepel a fában. Ekkor az eljárást befejezzük.

Az alábbi hatpontú gráfban a vastagon jelölt éleket a következő sorrendben húztuk be: x₁x₂, most y=x₂. A következő lépésben behúztuk az x₂x₃ élt és y=x₃, ezután behúztuk az x₃x₄ élt és y=x₄. Eddig „nyílegyenesen” haladtunk előre. A következő lépésben azonban y=x₄-bol csak visszafelé megy él (x₄x₂, ezt nem választjuk ki, az ábrán szaggatott), tehát y=x₃ és nem húzűnk be élt. Az x₃x₁ él visszafelé megy, ezt nem húzzuk be (az ábrán szaggatott), viszont behúzzuk az x₃x₅ élt és y=x₅. Innen megint nem megy „előre” él csak visszafelé az x₅x₂ és x₅x₁ él (az ábrán szaggatott), ezért visszamegyünk x₅ apjához: y=x₃, innen sem tudunk már előbbre lépni, ezért y=x₂. Behúzhatjuk az x₂x₆ élt és y=x₆, innen már nem tudunk előrébb lépni, tehát ismét y=x₂ lesz, onnan sem mehetünk előrébb, tehát y=x₁. Most behúzzuk az x₁x₇ élt és y=x₇. Innen nem mehetünk előrébb, tehát ismét y=x₁ lesz, s onnan sem indul már új él, tehát az eljárásnak vége. A kiválasztott faélek vastagítva vannak, a többi él szaggatott.

Az eljárást ezzel megadtuk. A kérdés csak az, hogy a) valóban azt kapjuk, amit várunk tole: egy olyan favázat, amelybe a gráf összes éleit behúzva mindig elődöt és utódot fogunk összekötni; b) elég gyors-e ez az eljárás; és c) hogyan valósítható meg ez az eljárás számítógépen?

először vizsgáljuk meg az a) és b) kérdést. Mindkét kérdésre igenlő a válasz, de egyik válasz sem magától értetődo. Ez az algoritmus is mohó, csakúgy, mint a szélességi keresés: mindkettő minden pillanatban a legkézenfekvőbbet teszi – csak mást tekint legkézenfekvőbbnek. A szélességi inkább védekező jellegű algoritmus, a mélységi inkább offenzív algoritmus. Mindkét esetben meg kell tehát vizsgálnunk, hogy ami adott pillanatban a legkézenfekvőbb, az végeredményben is a legjobb-e, vagy egyáltalán célhoz vezet-e.

Be kell tehát bizonyítanunk, hogy az ismertetett algoritmus véget ér, összefüggő gráf esetén valóban favázat ad és a kapott faváznak megvan a feladatban kívánt tulajdonsága. Ez azonban következik abból, hogy

Ahogy a szélességi keresésre (II. eljárás), úgy a mélységi keresésre (III. eljárás) is igaz, hogy ha eljut egy ponthoz, akkor annak összes szomszédjához is eljut. Hiszen a gyökérhez csak akkor jut vissza, ha már minden pontból kimerítette az összes továbblépési lehetőségeket, tehát minden pont minden szomszédját bejárta. Vagyis az eljárás által bejárt pontok halmazából nem vezet ki él. Minthogy a gráf összefüggő, ebből már (D) szerint következik, hogy a gráf minden pontja sorra került. Ebből viszont a dőlt betűs állítás szerint következik, hogy minden élt is bejárt.

Bizonyítsuk be, hogy a mélységi keresés (III. eljárás) az összefüggő gráfnak valóban egy favázát adja meg!

A mélységi keresés – ismét a szélességi kereséshez hasonlóan – nem választ be olyan élt a felépítendő favázba, amely két korábban már beválasztott pontot köt össze, tehát nem hoz létre kört. De minden élt sorra vesz, így összefüggő gráf esetén valóban feszítő fát fog adni.

A 15. feladat megoldásának befejezése:

Nyilvánvaló, hogy a mélységi kereséssel kapott faváznak megvan a második kérdésben követelt tulajdonsága. Legyen ugyanis uv a gráf egy éle. Feltehetjük, hogy a keresés során u és v közül először u került sorra. Amikor elértünk u-hoz, akkor minden ezután beválasztott pont u utódja lesz a fán, amíg csak u-ból „vissza nem lépünk”. De vissza csak akkor lépünk, ha már u minden szomszédja szerepel, tehát eddigre a v pont sorra kerül. Tehát: a v pont u után és az u-ról való visszalépés előtt kerül sorra, de ez azt jelenti, hogy v biztosan u utódja lesz a fán.

BIZONYÍTÁS:

Legyen tehát H és H’ két maximális összefüggő részhalmaz. Ha diszjunktak, kész vagyunk. Ha van közös pontjuk, akkor ebből a közös pontból mind H, mind H’ minden pontja elérhető úttal, tehát H és H’ egyesítésének minden pontja is elérhető belőle úttal, vagyis egyesítésük is összefüggő részhalmaz (összefüggő részgráfot feszít). De H és H’ tartalmazásra maximális összefüggő részhalmazok voltak, s ez csak úgy lehet, ha H=H’.

A feladat többi állítása nyilvánvaló következménye a feladat most bizonyított első állításának.

Ha a három (I., II., III.) eljárás közül bármelyiket tetszőleges gráfra futtatjuk, akkor bármely pontnak megtalálja az összefüggő komponensét. Ha pedig egy összefüggő komponenst megtalált, akkor ezt elhagyhatjuk a gráfból, s megismételhetjük az eljárást. Így pontosan annyi komponense van a gráfnak, ahányszor „újraindítjuk” az eljárást.

Mindhárom algoritmus alkalmas tehát arra is, hogy eldöntse adott gráfról, hogy összefüggő-e. A gráf pontosan akkor összefüggő, ha nem kell újraindítani az eljárást.

Az eljárások általános esetben egy feszítő erdőt adnak, amely a gráf minden komponensében egy-egy favázat ad meg.

BIZONYÍTÁS:

Ha a mélységi keresést az x pontból indítjuk, akkor a legmagasabb szintű pontokba futó utak az x pontból induló leghosszabb utak, ez következik abból, hogy a gráf minden pontja a faváz egy elődje és utódja között fut (lásd az előző feladatot). Egy ilyen út megtalálásához elegendő tehát (lényegében) p(n) lépés. Ha minden pontra megcsináljuk ezt, akkor legfeljebb np(n) lépésben megkapjuk minden pontból a leghosszabb utat, s ezek közül a leghosszabb(ak) lesz(nek) a gráf leghosszabb útja(i).

MEGOLDÁS:

Nyilván elég az állítást összefüggő gráfokra vizsgálni, hiszen egy gráf pontosan akkor páros gráf, ha minden összefüggő komponense páros gráf. Legyen tehát G egy összefüggő gráf, amelyben minden kör hossza páros. Keressük meg egy feszítő fáját, például egy szélességi favázát. Színezzük ezt ki két színnel úgy, hogy a páros szintek pontjai (és a gyökér) pirosak legyenek, a páratlan szintek pontjai kékek. Ha sikerül a gráf pontjait két osztályba sorolni úgy, hogy csak különböző osztályok között menjen él, ez csak úgy lehetséges, ha a kék pontok alkotják az egyik osztályt, a pirosak a másikat. Ám a szélességi faváz bizonyított tulajdonsága szerint a gráf minden éle vagy azonos szintű pontok között fut, vagy szomszédos szintek között. A szomszédos szintek között futó élek „nem zavarnak”, mert különböző színű pontokat kötnek össze. Ha van olyan e=xy él, amely két azonos szintű pontot köt össze, akkor keressük meg x és y első közös osét, legyen ez u. Az x-bol u-ba vezető út és az y-ból u-ba vezető út egyforma hosszú és u-n kívül nincs közös pontjuk, hiszen u az első közös os. Ha a két utat összeillesztjük és az így kapott páros hosszú úthoz hozzávesszük az e élt, akkor egy páratlan kört kapunk. Ha ilyen él nincs, akkor viszont a fekete és a fehér pontok valóban két megfelelő osztályra bontják a gráf pontjait. (Az ábrán u=x₅, v=x₆, a közös os x₂, a talált páratlan kör x₅x₃x₂x₄x₆x₅.)

Ha a gráf nem összefüggő, akkor vegyük az összefüggő komponenseit, vagyis a legnagyobb összefüggő részgráfjait. Körmentes gráf minden részgráfja is körmentes. Így minden összefüggő komponense is körmentes, azaz fa. Ezért a körmentes gráfokat szokás erdőnek, vagy ligetnek is nevezni. (E) szerint egy ilyen erdő minden összefüggő részgráfjának a csúcsszámnál eggyel kevesebb éle van. Ebből kapjuk a következő tételt:

Ebből már következik a II/2. feladat állítása.

Hagyjuk el a gráf összes élét. Az így kapott üres gráf n komponensből áll. Most húzzuk be újra egyesével a gráf éleit. Nyilvánvaló, hogy minden él behúzása vagy eggyel csökkenti a komponensek számát (ha az él két különböző komponenst köt össze), vagy változatlanul hagyja (ha azonos komponenshez tartozó csúcsokat köt össze). Az eljárást addig folytatjuk, amíg a gráf összes élét be nem húzzuk. Végeredményben összefüggő gráfot kell kapnunk, vagyis olyan gráfot, amelyben a komponensek száma egy. Minden él behúzásánál maximum eggyel csökkent a komponensek száma és kezdetben n volt, ezért legalább n–1 élt kellett behúznunk.

MEGOLDÁS:

a) Az él két végpontja között nem marad út, hiszen a fában bármely két pont között pontosan egy út van, az él két végpontja között az él volt ez az egyetlen út.

b) A behúzott él két végpontját köti össze út a fában.

c) Ha d(x)=1, akkor az elhagyásával keletkező gráf is fa, mert körmentes gráf részgráfja is körmentes és az elsőfokú pont elhagyásával keletkező részgráf összefüggő marad. Ha viszont x-nek legalább két szomszédja van, legyenek ezek u és v. A fában u és v között is egyetlen út van, s ez az uxv út, amelyet x elhagyásával megszüntetünk. Tehát G–x gráfban u és v között nem fut él, azaz G–x nem lehet összefüggő.

MEGOLDÁS:

A feladat állítása NEM IGAZ. Az alábbi gráf egy egyszerű ellenpélda:

Ez a gráf bármely harmadfokú pont elhagyásával két komponensre esik szét (egy izolált pontra és egy 3 hosszú útra), de nem körmentes.