Am văzut exemple de grafuri conectate și grafuri care nu sunt conectate. În timp ce „neconectat” este destul de mult o fundătură, sunt multe de spus despre „cât de conectat” este un graf conectat.Cea mai simplă abordare este să ne uităm la cât de greu este să deconectăm un graf prin eliminarea unor vârfuri sau muchii. Presupunem că toate grafurile sunt simple.
Dacă este posibilă deconectarea unui graf prin eliminarea unui singur vârf, numit punct de tăiere, spunem că graful are conectivitate1. Dacă acest lucru nu este posibil, dar este posibilă deconectarea grafului prin îndepărtarea a două vârfuri, graful are conectivitate 2.
Facem același lucru pentru muchii:
Teorema 5.7.3 $\kappa(G)\le\lambda(G)$.
Grafele care sunt conectate 2 sunt deosebit de importante, iar următoarea teoremă simplă este utilă.
Există și alte caracterizări frumoase ale grafurilor 2-conectate.
Corolarul următor este o reformulare ușoară a acestei teoreme.
Această versiune a teoremei sugerează o generalizare:
Prima dată vom demonstra versiunea originală a lui Menger, o versiune „locală”.
Teorema 5.7.9. Dacă $v$ și $w$ sunt vârfuri neadiacente în $G$, $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet\quad\bullet$$
Ne întoarcem pe scurt la 2-conectivitate. următoarea teoremă poate fi folosită uneori pentru a furniza pasul de inducțieîntr-o demonstrație prin inducție.
Un graf care nu este conectat este format din componente conectate. În ateorema care amintește de aceasta, vedem că grafurile conectate care nu sunt2-conectate sunt construite din subgrafe 2-conectate și punți.
Definiția 5.7.11 Un bloc într-un graf $G$ este un subgraf maximalindus pe cel puțin două vârfuri fără un punct de tăiere.
Ca de obicei, maxim înseamnă aici că subgraful indus $B$ nu poate fi mărit prin adăugarea de vârfuri sau muchii (păstrând în același timp proprietatea dorită, în acest caz, fără puncte de tăietură).Un bloc este fie un subgraf indus cu 2 conexiuni, fie o singură muchie împreună cu punctele sale finale. Blocurile sunt utile în mare parte datorită acestei teoreme:
Teorema 5.7.12 Blocurile lui $G$ împart marginile.
Dacă $G$ are un singur bloc, el este fie $K_2$, fie este 2-conectat, iar orice graf 2-conectat are un singur bloc.
Teorema 5.7.13 Dacă $G$ este conex, dar nu este 2-conectat, atunci fiecare verigă care se află în două blocuri este un punct de tăiere al lui $G$.
Exerciții 5.7
Ex 5.7.1Supunem că un graf simplu $G$ pe $n\ge 2$ vârfuri are cel puțin $\ds {(n-1)(n-2)\ peste2}+1$ muchii. Demonstrați că $G$ este conex.
Ex 5.7.3Supunem că $G$ este simplu cu succesiunea de grade$d_1\le d_2\le\cdots\le d_n$, iar pentru $k\le n-d_n-1$, $d_k\ge k$. Arătați că $G$ este conex.
Ex 5.7.4Reamintim că un graf este $k$-regular dacă toate vârfurile au gradul $k$. Care este cel mai mic număr întreg $k$ care face ca acest lucru să fie adevărat:
Dacă $G$ este simplu, are $n$ vârfuri, $m\ge k$, iar $G$ este $m$-regular,atunci $G$ este conex.
(Desigur, $k$ depinde de $n$.)
Ex 5.7.6Găsește un graf simplu cu $\kappa(G)
Rețineți că un punct de tăietură este conținut în cel puțin două blocuri, astfel încât toate vârfurile dependente ale grafului bloc-punct de tăietură sunt blocuri. Aceste blocuri se numesc blocuri de capăt.
Ex 5.7.10Desenați graficul bloc-punct de tăiere al grafului de mai jos.
.