Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Eulerovské a hamiltonovské grafy

Definice (Eulerovský graf)

Graf se nazývá eulerovský, jestliže existuje takové pořadí všech hran že tedy každé dvě po sobě jdoucí hrany mají společný vrchol a rovněž první a poslední hrana se protínají, žádná hrana se neopakuje. Jinými slovy: graf je eulerovský, pokud v něm existuje uzavřený sled v němž se každá hrana vyskytuje právě jednou. Takový tah nazýváme uzavřeným eulerovským tahem.

Věta (Charakteristika eulerovského grafu)

Graf je eulerovský právě tehdy, když je souvislý a každý vrchol má sudý stupeň.

Důkaz

: tato implikace je triviální -- eulerovský graf musí být souvislý, do každého vrcholu musím vstoupit i z něj vystoupit, což zvýší stupeň vždy o 2.

: Mějme tah maximální délky První a poslední vrchol tahu jsou totožné, jinak by do prvního vrcholu vedl lichý počet hran, a jelikož graf má všechny stupně sudé, dal by se tah prodoužit. Vidíme, že každou hranou v grafu vede nějaký uzavřený tah (nejdelší tah hranou je uzavřený, protože jinak by šel z vrcholu ze sudým stupněm prodlužovat).

Náš maximální tah obsahuje všechny hrany a vrcholy, protože pokud ne, ze souvislosti jistě existuje vrchol, který je v max. tahu, z něhož vede hrana, která v max. tahu není. Tou vede uzavřený tah a pokud ho spojíme s naším maximálním tahem, dostaneme delší, což je spor.

Definice (k-hamiltonovský graf)

Graf je k-hamiltonovský, pokud existuje posloupnost všech vrcholů taková, že (Do každého vrcholu smíme jen jednou.) O grafu říkáme jednoduše, že je hamiltonovský, pokud je 1-hamiltonovský.

Definice (Hamiltonovská kružnice)

Hamiltonovská kružnice je kružnice procházející každým vrcholem grafu právě jednou. Graf má takovou kružnici, právě když je hamiltonovský. Její nalezení je NP-úplný problém.

Poznámka

Problém nalezení hamiltonovské kružnice se dá upřesnit na problém nalezení hamiltonovské kružnice s nejmenší vahou v ohodnoceném grafu, což je známý problém obchodního cestujícího. Je tedy také NP-úplný, ale existují algoritmy, jejichž řešení jsou blízká optimálnímu.

Věta (Diracova)

Graf je hamiltonovský, pokud platí:

Důkaz

Dokážeme o něco silnější lemma pro jeden vrchol, z kterého Diracova věta plyne: pro dva vrcholy v grafu nespojené hranou platí, že pokud , potom je graf hamiltonovský, právě když s přidanou hranou je hamiltonovský.

Jedna implikace je triviální, takže vezmeme tu druhou. Máme v grafu hamiltonovskou kružnici . Pokud ta neobsahuje tak je i v grafu a končíme, pokud tuto hranu obsahuje, označíme pro vrcholy grafu v pořadí, v jakém je prochází hamiltonovská kružnice :

Pokud mají tyto množiny neprázdný průnik, nalezneme vrcholy a , přes které můžeme kružnici přepojit. ani neobsahují , takže . Potom

takže takový bod existuje.

Věta

Každý souvislý graf je 3-hamiltonovský.

Důkaz

je souvislý, existuje v něm tedy kostra která je souvislá. Kostra vznikla ubráním některých hran, takže Stačí tedy dokázat, že kostra je 3-hamiltonovská.

Lemma

Každý strom je 3-hamiltonovský.

Důkaz

Indukcí:

1. pro triviální
2. Máme dvě komponenty každá je 3-hamiltonovská. Graf je souvislý existuje most z do Most vede přes vrcholy kde Potom existuje 3-hamiltonovské propojení komponent

Věta

Graf je vrcholově 2-souvislý, právě když v něm mezi každými dvěma různými vrcholy existují dvě vrcholově disjunktní cesty.

Důkaz

Implikace je zřejmá, opačná se dá ukázat sporem - nechť ve dvousouvislém grafu mezi nějakými dvěma vrcholy neexistují dvě vrcholově disjunktní cesty. Pak vezmu vrchol, který je na každé cestě mezi těmito dvěma a odeberu ho - a tím se graf stane nesouvislým, což je spor.

Věta

Graf je vrcholově 2-souvislý, právě když jej lze vytvořit z trojúhelníku (t.j. z ) posloupností dělení a přidávání hran (definice těchto operací jsou na začátku kapitoly).

Věta

Každý 2-souvislý graf je 2-hamiltonovský.

Důkaz

??? Do každého vrcholu vedou 2 vrcholově i hranově disjunktní cesty -- při zpáteční cestě použiju druhou. Důkaz podobně jako u věty o 3-hamiltonovských grafech.