Euler-vonalak, Hamilton-körök, fák

Eredet

Königsbergi hidak problémája (lehet-e egy olyan sétát tenni, hogy minden hídon pontosan egyszer menjünk át?). Euler válasza 1736-ban született meg. Ehhez tartozó gráf: csúcsok = partok és szigetek, élek = hidak.

Definíció — Euler-vonal

Egy \(G\) gráfban egy vonalat Euler-vonalnak nevezünk, ha tartalmazza \(G\) minden élét. Tehát az Euler-vonal olyan séta, amely a gráf minden élét pontosan egyszer tartalmazza.

Tétel — Euler, zárt változat

Legyen \(G\) izolált csúcsmentes gráf. Ekkor \(G\)-ben van zárt Euler-vonal \(\iff\) \(G\) összefüggő és \(G\) minden csúcsa páros fokú.

Bizonyítás

⟹: Mivel nincs izolált csúcs, ezért az E-vonal minden csúcson átmegy \(\implies\) az E-vonal mentén minden csúcsból minden csúcsba el lehet jutni. Tehát a gráf összefüggő. A kiinduló csúcsból először kimegyünk, majd néhányszor be és ki, majd be. Ekkor az ő fokszáma \(1 + (k \cdot 2) + 1 = \text{páros}\) (\(k \in \mathbb{N} \cup \{0\}\)). A többi csúcs esetén néhányszor be és ki megyünk. Ezek fokszáma \(l \cdot 2 = \text{páros}\) (\(l \in \mathbb{N}\)).

⟸: Vegyünk egy tetszőleges csúcsot. Ebből indulva építsünk vonalat: ha valamelyik csúcsba értünk, onnan még nem használt élen megyünk tovább. Folytassuk ezt amíg lehet. A vonal biztosan a kiinduló csúcsban akad el, mert minden más csúcsban a páros fokszám miatt, ha bemegyünk, akkor ki is tudunk belőle jönni. Tehát zárt vonal keletkezett.

• Ha ez a zárt vonal minden élt tartalmaz, akkor ez egy zárt E-vonal.
• Ha ez a zárt vonal nem tartalmaz minden élt, akkor megmutatjuk, hogy meghosszabbítható a zárt vonal. Ezt szükség szerint többször megtéve, előbb-utóbb minden élt tartalmazó zárt vonalhoz, azaz zárt E-vonalhoz jutunk a végesség miatt.

A zárt vonalon kívüli él kétféle lehet:

1. típus: egyik végpontja a zárt vonalon van. Legyen \(e\) egy ilyen él, zárt vonalon lévő végpontja \(v\). Ekkor \(v\)-ből az \(e\) élen át indulva építsünk vonalat úgy, hogy az előző zárt vonal éleit nem használhatjuk. Ez \(v\)-ben akad el a fokszámok párossága miatt, így egy új zárt vonalat kapunk. Az előző zárt vonalon elindulunk, \(v\)-be érve beszúrjuk az új zárt vonalat, majd megyünk tovább az eredeti zárt vonalon — ez egy hosszabb zárt vonal.
2. típus: egyik végpontja sincs a zárt vonalon. Mivel \(G\) összefüggő és nincs izolált csúcs, ezen él egyik végpontja és a zárt vonal egyik csúcsa között vezet út, amelyen biztosan van 1. típusú él — ez visszavezeti az 1. típusra.

Tétel — Euler, nyílt változat

Legyen \(G\) izolált csúcsmentes gráf. Ekkor \(G\)-ben van nyílt E-vonal \(\iff\) \(G\) összefüggő és \(G\)-ben pontosan 2 db páratlan fokú csúcs van.

Bizonyítás

⟹: összefüggőség, mint a zárt változatban. A kiinduló csúcsból kimegyünk, majd néhányszor be és ki, vagyis a fokszáma: \(1 + (\text{valahányszor } 2) = \text{páratlan}\). A végző csúcsba néhányszor be és ki, végül be, vagyis a fokszáma: \((\text{valahányszor } 2) + 1 = \text{páratlan}\). A többi csúcsnál néhányszor be és ki \(\implies\) fokszám \(= (\text{valahányszor } 2) = \text{páros}\).

⟸: húzzunk be egy új élt a két páratlan fokú csúcs közé. A kiegészített gráf összefüggő és minden csúcsának fokszáma páros. A kiegészített gráfban van zárt E-vonal. Feltehető, hogy ennek első éle az új él. Ekkor viszont az első lépést elhagyva \(G\)-ben nyílt E-vonalat kapunk.

Eredet

Hamilton dodekaéder játéka (1857).

Definíció — Hamilton-út, Hamilton-kör

Egy gráfban egy utat vagy kört Hamilton-útnak (H-út), illetve Hamilton-körnek (H-kör) nevezünk, ha a gráf minden csúcsát tartalmazza.

Tétel

Legyen \(G\) egyszerű gráf.

1. Ha \(G\)-ben van H-kör \(\implies\) van benne H-út.
2. Ha \(G\)-ben van H-út / H-kör \(\implies G\) összefüggő.

Bizonyítás

1. A H-kör utolsó lépését elhagyva H-út adódik.
2. H-út / H-kör mentén minden csúcsból minden más csúcsba el lehet jutni \(\implies\) összefüggő.

Tétel — Ore

Legyen \(G\) egyszerű gráf és \(|V(G)| \ge 3\). Ha \(\forall v, w \in V(G)\) nem szomszédos csúcspár esetén \(d(v) + d(w) \ge |V(G)|\), akkor \(G\)-ben van H-kör.

Bizonyítás

I. Először a H-út létezését bizonyítjuk: vegyünk egy tetszőleges utat \(G\)-ben.

• Ha ez tartalmaz minden csúcsot \(\implies\) H-út.
• Ha nem, akkor megmutatjuk, hogy meghosszabbítható másik úttá — ezt ismételve a végesség miatt előbb-utóbb H-úthoz jutunk.

Az úton nem lévő csúcs kétféle lehet:

1. eset: ha van olyan csúcs, ami nincs az úton, de szomszédos az út kezdő vagy végző csúcsával, akkor nyilvánvalóan meghosszabbítható az út.
2. eset: ha nincs ilyen csúcs, azaz az úton nem lévő csúcsok nem szomszédosak sem az út kezdő, sem a végző pontjával. Menjen az út \(v\)-ből \(w\)-be, és \(x\) egy úton kívüli csúcs. \(x\) szomszédainak száma \(d(x)\); \(w\) szomszédainak száma \(d(w)\), és ezek a szomszédok mind az úton vannak. \(w\) szomszédainak rákövetkezője is \(d(w)\) db van. Ha a két így kapott halmaznak nem lenne közös eleme, akkor \(|V(G)| \ge d(x) + d(w) + 1 \ge |V(G)| + 1\) (mivel \(x\) és \(w\) nem szomszédosak, az Ore-feltétel alkalmazható rájuk). Ez ellentmondáshoz vezet, vagyis van közös elemük. Legyen a közös elem \(y'\), és tfh. hogy \(y'\) az \(y\)-nak rákövetkezője. Ekkor \((v, \dots, y, w, \dots, y', x)\) egy hosszabb út.

II. H-kör létezése: az I. rész szerint van H-út, tfh. ez \(v\)-ből \(w\)-be megy.

1. eset: \(v\) és \(w\) szomszédosak \(\implies\) értelemszerűen van H-kör.
2. eset: \(v\) és \(w\) nem szomszédosak. \(v\) szomszédainak száma \(d(v)\); \(w\) szomszédainak rákövetkezője \(d(w)\) db van. Ha a két halmaznak nem lenne közös eleme, akkor \(|V(G)| \ge d(v) + d(w) + 1 \ge |V(G)| + 1\) (a \(v\)-t 1-esként véve figyelembe, mert nem tartozik a rákövetkezők közé, és \(v, w\) nem szomszédosak, az Ore-feltétel alkalmazható). Tehát a két halmaznak van közös eleme: \(y'\), és tfh. hogy \(y\)-t követi. Ekkor \((v, \dots, y, w, \dots, y', v)\) már H-kör.

Következmény — Dirac

Legyen \(G\) egyszerű gráf, \(|V(G)| \ge 3\). Ha \(\forall v \in V(G) : d(v) \ge \frac{|V(G)|}{2}\), akkor \(G\)-ben van H-kör.

Bizonyítás

Ellenőrizzük az Ore-feltételt! Legyen \(v, w\) két nem szomszédos csúcs. Ekkor:

\[ d(v) + d(w) \ge \frac{|V(G)|}{2} + \frac{|V(G)|}{2} = |V(G)| \]

Ez épp a Dirac-feltétel miatt teljesíti az Ore-t.

Tétel — nyakláncszabály

Legyen \(G\) egyszerű és összefüggő gráf.

1. Ha \(k\) db csúcs törlése után a komponensek száma \(\ge k + 1\), akkor \(G\)-ben nincs H-kör.
2. Ha \(k\) db csúcs törlése után a komponensek száma \(\ge k + 2\), akkor \(G\)-ben nincs H-út.

Bizonyítás

(1) Tfh. \(G\)-ben van H-kör. Ekkor a H-körbeli élekkel megadott feszítő részgráf \(k\) db csúcs törlése után legfeljebb \(k\) db komponensre esik szét \(\implies G\) is legfeljebb \(k\) db komponensre esik szét (a H-körben nem lévő élek miatt még kisebb is lehet akár a komponensek száma).

(2) Tfh. \(G\)-ben van H-út. Ekkor a H-útbeli élek által adott feszítő részgráf \(k\) db csúcs törlésével max \(k + 1\) db komponensre esik szét \(\implies G\) is legfeljebb ennyire.

Definíció — fa

Egy gráf fa, ha összefüggő és körmentes.

Definíció — erdő

Egy gráf erdő, ha körmentes.

Állítás

Minden fa és minden erdő egyszerű gráf.

Bizonyítás

fa / erdő \(\implies\) körmentes \(\implies\) nincs benne sem 1-, sem 2-hosszúságú kör \(\implies\) nincsenek sem hurokélei, sem párhuzamos élei \(\implies\) egyszerű.

Tétel

Ha \(G\) fa és \(|V(G)| \ge 2\), akkor \(G\)-ben van legalább 2 db elsőfokú csúcs (ezeket szokás leveleknek nevezni).

Bizonyítás

Vegyük \(G\)-ben a leghosszabb utat: \((v_0, v_1, v_2, \dots, v_k)\).

• \(v_0 \to v_1\) szomszédja \(v_0\)-nak.
• \(v_0\)-nak nincs másik szomszédja az úton, mert \(G\) körmentes.
• \(v_0\)-nak nincs az úton kívüli szomszédja, mert a leghosszabb utat vettük.

\(\implies d(v_0) = 1\). Hasonlóképpen \(d(v_k) = 1\).

Tétel

Ha \(G\) fa, akkor \(|V(G)| = |E(G)| + 1\).

Bizonyítás — \(|V(G)|\) szerinti teljes indukcióval

• \(|V(G)| = 1\): egyetlen csúcs, erre \(|E(G)| = 0\), így \(1 = 0 + 1\).
• Tfh. \(|V(G)| \ge 2\) és kevesebb csúcsú fákra igaz az állítás. Előző tétel szerint \(\exists v \in V(G) : d(v) = 1\). Ekkor a \(G - v\) (v-t törölve) fa, amire alkalmazható az indukciós feltétel: \(|V(G - v)| = |E(G - v)| + 1\). Mivel \(v\)-vel együtt 1 csúcs és 1 él törlődött: \(|V(G)| - 1 = (|E(G)| - 1) + 1\), amiből \(|V(G)| = |E(G)| + 1\).

Következmény

Ha \(G\) erdő, akkor \(|V(G)| = |E(G)| + c(G)\), ahol \(c(G)\) a komponensek száma.

Bizonyítás

Alkalmazzuk a tételt \(G\) komponenseire (komponensenként +1).

Tétel

Legyen \(n \ge 2\) és \(d_1, \dots, d_n \in \mathbb{N}\). Ekkor \(\exists\) fa \(d_1, \dots, d_n\) fokú csúcsokkal \(\iff d_1 + \dots + d_n = 2n - 2\).

Bizonyítás

⟹: tfh. van ilyen fa \(G \implies d_1 + \dots + d_n = 2|E(G)|\) (fokszámi tétel). Mivel \(G\) fa, \(|E(G)| = |V(G)| - 1 = n - 1\), így \(2(n - 1) = 2n - 2\).

⟸: \(n\) szerinti teljes indukcióval.

• \(n = 2\): \(d_1 + d_2 = 2 \cdot 2 - 2 = 2 \implies d_1 = d_2 = 1\). Ilyen fa létezik (két csúcs egy éllel összekötve).
• Tfh. \(n \ge 3\) és az állítás igaz \((n - 1)\)-re. Feltehető, hogy a számok növekvő sorrendűek: \(d_1 \le \dots \le d_n\). \(d_1 = 1\), mert ellenkező esetben \(d_1 \ge 2 \implies d_1, \dots, d_n \ge 2\), ekkor \(d_1 + \dots + d_n \ge 2n\) lenne, ami ellentmondás az összeg \(2n - 2\) értékének. \(d_n \ge 2\), mert ellenkező esetben \(d_1 = d_2 = \dots = d_n = 1\) lenne, ekkor az összeg \(n \ne 2n - 2\) lenne (mivel \(n \ge 3\)).
• Ekkor \(d_2, \dots, d_{n-1}, d_n - 1 \in \mathbb{N}\), számuk \(n - 1\). Összegük: \(d_2 + \dots + d_{n-1} + (d_n - 1) = (2n - 2) - d_1 - 1 = (2n-2) - 1 - 1 = 2(n - 1) - 2\). Ezért ezekre alkalmazható az indukciós feltétel \(\implies \exists\) fa \(d_2, \dots, d_{n-1}, d_n - 1\) fokú csúcsokkal. Ezután vegyünk hozzá egy új csúcsot és azt kössük össze a \((d_n - 1)\) fokú csúccsal. Az új csúcs fokszáma \(1 = d_1\), a \((d_n - 1)\) fokú csúcs fokszáma \(d_n\) lesz. A kapott gráf fa, amelyben a fokszámok: \(d_1, d_2, \dots, d_n\).