Autorské řešení 2. písemky
Mosty a artikulace
Obsahuje-li graf most, obsahuje artikulaci.
Odebráním mostu se tedy graf rozpadne na právě dvě komponenty souvislosti, z nichž vzhledem k tomu, že měl původní graf alespoň tři vrcholy, musí mít nějaká z nich alespoň dva vrcholy. Vyberem ten z těchto alespoň dvou vrcholů, který incidoval s mostem.
Tento vrchol musí být artikulace, protože po toho odebrání zanikne také původní most, tedy nebude existovat žádná cesta mezi vrcholy z na počátku zmiňovaných komponent souvislosti. Budou jistě neprázdné. Není jisté, že množina, ze které jsme odebrali artikulaci, bude souvislá.
Obsahule-li graf artikulaci, obsahuje most.
Jako protipříklad zvolíme tento graf:
Je zřejmé, že odstraněním prostředního vrcholu se graf rozpadne na dvě disjunktní \( K_3 \) a jde tedy o artikulaci, ale že žádná hrana most není.
Každá hrana grafu je most právě je-li graf strom.
Jedná se de facto o stejné tvrzení, jako jedno z ekvivalentních charakterizací stromů, konkrétně to o minimálním souvislém grafu.
Neexistuje graf, kde je každý vrchol artikulací.
Uvažme nějakou kostru, která pro libovolný souvislý graf určitě existuje. Pokud by byl vrchol artikulací v daném grafu, jistě by byl i v kostře, protože v té některé hrany a tedy cesty zanikají, žádné nevznikají.
Jenže, jak víme, každý strom na alespoň dvou vrcholech má alespoň dva listy. List však nikdy není artikulace. Proto v původním grafu existoval vrchol, který nebyl artikulace.
Nápovědou vám mohlo být, jak jsem se při písemce zmiňoval o důležitosti konečnosti, že nekonečná cesta má každý vrchol jako artikulaci -- na ní totiž selhává tvrzení, že každý strom má alespoň dva listy, jak jsme si svého času říkali.
Vysoké stupně
Existuje-li proti našemu tvrzení pro dané n nějaká množina protipříkladů na nejvýše n vrcholech, vybereme z ní nějaký takový, který má maximální poměr zlých vrcholů (těch, které mají stupeň devět a více) vůči všem vrcholům (aby to byl protipříklad, musí to být alespoň \( \frac{1}{2} \)).
Nyní počítejme konce hran. Řekněme, že je zlých vrcholů k. Potom je v této skupině nejméně 9k konců hran. Ve skupině nezlých vrcholů na první pohled nemusí být žádný, vrcholy mohou být izolované, ale teď využijeme toho, že náš protipříklad má být ve výše uvedeném smyslu maximální -- v takovém izolované vrcholy být nemohou, protože bychom je mohli ubrat, čímž bychom rovinnost grafu jistě neohrozili a získali bychom tak maximálnější protipříklad.
Stejně tak ve skupině nezlých vrcholů nebudou vrcholy stupně jedna a dva, protože i ty lze při zachování rovinnosti odebrat. (Konce hran v případě stupně dva prostě spojíme, v případě stupně jedna tento konec zapojíme do libovolného vrcholu ve stěně.) Takže je ve skupině nezlých vrcholů minimální stupeň tři.
Počítejme tedy: \( 9\cdot k+(n-k)\cdot 3 = 3n+6k \geq 6n \). Což je spor, protože v rovinném grafu být 3n hran nemůže. Tím jsme dokázali, že maximální protipříklad neexistuje -- nemůže tedy existovat žádný protipříklad. (Protipříkladů grafů do n vrcholů je jen konečně mnoho.)
Podgraf
Jsou to grafy, jejichž každá komponenta souvislosti splňuje aspoň jednu ze dvou podmínek:
- Má nejvýše tři vrcholy.
- Je to úplný bipartitní graf \( K_{1, n} \), neboli hvězda.
Proč?
Studovaný zakázaný podgraf je souvislý, podgrafem tedy může být jen vrcholů z jedné komponenty souvislosti (vynucujeme mezi nimi existenci cesty), tedy se naše charakterizace může vyslovovat jen o vlastnostech jednotlivých komponent, ne třeba o jejich počtu.
Graf na čtyčech vrcholech může být podgrafem jen grafů na alespoň čtyřech vrcholech, protože každá dostatečně malá komponenta \( P_3 \) jistě neobsahuje.
Hvězda \( P_3 \) také jistě neobsahuje, otázkou je neexistují-li další "velké" grafy, které ji neobsahují. Mějme tedy graf na alespoň čtyřech vrcholech a najděme v něm nejdelší cestu. Jistě její délka není \( \geq 3 \), protože pak by to byl onen zakázaný podgraf, jistě to také není 1, protože by pak graf nemohl obsahovat více, než dva vrcholy.
Tedy máme graf s nejdelší cestou právě tři a alespoň čtyřmi vrcholy. Jak vypadá? Za dva krajní vrcholy nejdelší cesty žádné nové vrcholy být zavěšené nemohou, protože by to pak byla nejdelší cesta. Za prostřední vrchol mohou, ale za tyto zavěšené už opět nemůžeme připojovat další vrcholy, protože bychom vytvořili cestu délky 3. Hvězda tedy tvoří přinejhorším kostru našeho grafu.
Mohou se v něm vyskytovat ještě nějaké další hrany, které by vedly mezi "cípy hvězdy"? Ne, vznikla by opět cesta délky tři.
Podgraf
Existoval-li by takový most, odstranili bychom ho a podívali se na libovolnou ze dvou vzniklých komponent. V těch by měl jeden vrchol lichý stupeň a všechny zbylé stupeň sudý, což není možné, protože konců hran musí být sudě.
Alternativně můžeme argumentovat tím, že je to graf eulerovský, takže v něm existuje uzavřený sled, takže po odstranění libovolné hrany stále existuje mezi každými dvěma vrcholy sled, tedy cesta, graf tedy zůstane spojitý a hrana mostem nebyla.