Viděli jsme příklady spojitých grafů a grafů, které nejsou spojité. Zatímco „nespojitý“ je v podstatě slepá ulička, o tom, „jak spojitý“ je spojitý graf, se dá říci mnoho.Nejjednodušší přístup je podívat se na to, jak těžké je rozpojit graf odstraněním vrcholů nebo hran. Předpokládáme, že všechny grafy jsou jednoduché.
Je-li možné graf rozpojit odstraněním jediného vrcholu, který se nazývá bod řezu, říkáme, že graf má spojitost1. Pokud to není možné, ale je možné graf rozpojitodstraněním dvou vrcholů, má graf konektivitu2.
To samé uděláme pro hrany:
Věta 5.7.3 $\kappa(G)\le\lambda(G)$.
Grafy, které jsou propojené 2, jsou obzvláště důležité a následující jednoduchá věta je užitečná.
Existují i další pěkné charakterizace 2-spojitých grafů.
Následující důsledek je snadným přeformulováním této věty.
Tato verze věty naznačuje zobecnění:
Nejprve dokážeme původní Mengerovu verzi, „lokální“ verzi.
Věta 5.7.9 Jsou-li $v$ a $w$ nesousední vrcholy v $G$, platí $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet\quad\bullet$$
Vrátíme se krátce k 2-konektivitě. následující větu lze někdy použít k zajištění indukčního kroku v indukčním důkazu.
Graf, který není spojitý, se skládá ze spojených komponent. V atheormu připomínajícím tuto větu vidíme, že spojité grafy, které nejsou2spojité, jsou konstruovány ze2spojitých podgrafů a mostů.
Definice 5.7.11 Blok v grafu $G$ je maximálně indukovaný podgraf na alespoň dvou vrcholech bez bodu řezu.
Jako obvykle, maximální zde znamená, že indukovaný podgraf $B$ nelze zvětšit přidáním vrcholů nebo hran (při zachování požadované vlastnosti, v tomto případě bez řezných bodů). blok je buď indukovaný podgraf se dvěma spojnicemi, nebo jedna hrana spolu s koncovými body. Bloky jsou užitečné z velké části díky této větě:
Věta 5.7.12 Bloky grafu $G$ rozdělují hrany.
Pokud má $G$ jeden blok, je buď $K_2$, nebo je 2-spojený, a každý 2-spojený graf má jeden blok.
Věta 5.7.13 Je-li $G$ spojitý, ale není2-spojený, pak každý vrchol, který je ve dvou blocích, je řezným bodem$G$.
Cvičení 5.7
Ex 5.7.1Předpokládejme, že jednoduchý graf $G$ na $n\ge 2$ vrcholech má alespoň$ds {(n-1)(n-2)\nad2}+1$ hran. Dokažte, že $G$ je spojitý.
Ex 5.7.3Předpokládejte, že $G$ je jednoduchý s posloupností stupňů$d_1\le d_2\le\cdots\le d_n$ a pro $k\le n-d_n-1$, $d_k\ge k$. Ukažte, že$G$ je spojitý.
Ex 5.7.4Připomeňte, že graf je $k$-regulární, jestliže všechny vrcholy mají stupeň $k$. Jaké nejmenší celé číslo $k$ tomu dává za pravdu:
Je-li $G$ jednoduchý, má $n$ vrcholů, $m\ge k$ a $G$ je $m$-regulární, pak $G$ je spojitý.
(Samozřejmě $k$ závisí na $n$.)
Př. 5.7.6Najděte jednoduchý graf s$\kappa(G)
Všimněte si, že řezný bod je obsažen alespoň ve dvou blocích, takže všechnypříslušné vrcholy blokově-řezného grafu jsou bloky. Tyto blokyse nazývají koncové bloky.
Př. 5.7.10Nakreslete blokově-řezový graf níže uvedeného grafu.
.