Graf k-conex
În teoria grafurilor, un graf Format:Mvar conex se spune că este Format:Mvar-conex dacă are mai mult de Format:Mvar noduri și rămâne conex ori de câte ori sunt eliminate mai puțin de Format:Mvar noduri.
Conexitatea unui graf este cel mai mare Format:Mvar pentru care orice nod este conectat cu Format:Mvar noduri.
Definiții
Un graf (altul decât un graf complet) are conexitatea Format:Mvar dacă Format:Mvar este dimensiunea celui mai mic subset de noduri, astfel încât graful devine neconex dacă se șterg.[1] Grafurile complete nu sunt incluse în această versiune a definiției deoarece nu pot fi deconectate prin ștergerea nodurilor. Graful complet cu Format:Mvar noduri are conexitatea Format:Mvar − 1, valoare implicită rezultată din prima definiție.
O definiție echivalentă este aceea că un graf cu cel puțin două noduri este Format:Mvar-conex dacă, pentru fiecare pereche de noduri este posibil să se găsească Format:Mvar drumuri disjuncte care conectează aceste noduri, v. Format:Ill-wd Format:Harv. Din această definiție rezultă același răspuns, Format:Mvar − 1, pentru conexitatea grafului complet Format:Mvar.[1]
Se spune că un graf 1-conex este „conex”, un graf 2-conex este „biconex”, unul 3-conex este „triconex” etc.[2]
Aplicații
Combinatorică poliedrică
1-Format:Ill-wd oricărui politop convex Format:Mvar-dimensional formează un graf Format:Mvar-conex (teorema lui Balinski, Format:Harvnb). O teoremă parțial inversă, Format:Ill-wd, afirmă că orice graf planar 3-conex formează scheletul unui poliedru convex.
Complexitate computațională
Conexitatea nodurilor unui graf de intrare Format:Mvar poate fi calculată în timp polinomial în următorul mod:[3] se iau în considerare toate perechile posibile de noduri neadiacente de deconectat, folosind teorema lui Menger pentru a justifica faptul că separatorul de dimensiune minimă pentru este numărul de drumuri disjuncte perechile de noduri dintre ele, se codifică intrarea asimilând fiecare nod cu o muchie pentru a reduce în calcul numărului de drumuri disjuncte între perechi și se calculează numărul maxim de astfel de drumuri prin calculul Format:Ill-wd în graful dintre și cu capacitatea 1 pentru fiecare muchie, observând că un flux de în acest graf corespunde, prin teorema fluxului integral, la drumuri disjuncte între perechi de la la .
Note
- ↑ 1,0 1,1 Format:En icon Format:Citation
- ↑ Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21
- ↑ Format:En icon The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291