Graf k-conex
În teoria grafurilor, un graf G conex se spune că este k-conex dacă are mai mult de k noduri și rămâne conex ori de câte ori sunt eliminate mai puțin de k noduri.
Conexitatea unui graf este cel mai mare k pentru care orice nod este conectat cu k noduri.
Definiții
modificareUn graf (altul decât un graf complet) are conexitatea k dacă k 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 n noduri are conexitatea n − 1, valoare implicită rezultată din prima definiție.
O definiție echivalentă este aceea că un graf cu cel puțin două noduri este k-conex dacă, pentru fiecare pereche de noduri este posibil să se găsească k drumuri disjuncte care conectează aceste noduri, v. teorema lui Menger(d) (Diestel 2005, p. 55). Din această definiție rezultă același răspuns, n − 1, pentru conexitatea grafului complet Kn.[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
modificareCombinatorică poliedrică
modificare1-scheletul(d) oricărui politop convex k-dimensional formează un graf k-conex (teorema lui Balinski, Balinski 1961. ). O teoremă parțial inversă, teorema lui Steinitz(d), afirmă că orice graf planar 3-conex formează scheletul unui poliedru convex.
Complexitate computațională
modificareConexitatea nodurilor unui graf de intrare G 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 fluxului maxim(d) î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
modificare- ^ a b en Schrijver (), Combinatorial Optimization, Springer, ISBN 9783540443896
- ^ Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21
- ^ en The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291
Bibliografie
modificare- en Balinski, M. L. (), „On the graph structure of convex polyhedra in n-space”, Pacific Journal of Mathematics, 11 (2): 431–434, doi:10.2140/pjm.1961.11.431
- en Diestel, Reinhard (), Graph Theory (ed. 3rd), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
