thumb|Graf 4-conex În teoria grafurilor, un graf conex se spune că este -conex dacă are mai mult de noduri și rămâne conex ori de câte ori sunt eliminate mai puțin de noduri.
Conexitatea unui graf este cel mai mare pentru care orice nod este conectat cu noduri.
Definiții Un graf (altul decât un graf complet) are conexitatea dacă este dimensiunea celui mai mic subset de noduri, astfel încât graful devine neconex dacă se șterg. Grafurile complete nu sunt incluse în această versiune a definiției deoarece nu pot fi deconectate prin ștergerea nodurilor. Graful complet cu noduri are conexitatea − 1, valoare implicită rezultată din prima definiție.
O definiție echivalentă este aceea că un graf cu cel puțin două noduri este -conex dacă, pentru fiecare pereche de noduri este posibil să se găsească drumuri disjuncte care conectează aceste noduri, v. . Din această definiție rezultă același răspuns, − 1, pentru conexitatea grafului complet .
Se spune că un graf 1-conex este „conex”, un graf 2-conex este „biconex”, unul 3-conex este „triconex” etc.Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21
Aplicații Combinatorică poliedrică 1- oricărui politop convex -dimensional formează un graf -conex (teorema lui Balinski, ). O teoremă parțial inversă, , afirmă că orice graf planar 3-conex formează scheletul unui poliedru convex.
Complexitate computațională Conexitatea nodurilor unui graf de intrare poate fi calculată în timp polinomial în următorul mod: The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291 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 î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
Bibliografie
Categorie:Teoria grafurilor