Graf k-conex

graf care nu poate fi deconectat prin ștergerea a mai puțin de k noduri

Î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.

Graf 4-conex

Conexitatea unui graf este cel mai mare k pentru care orice nod este conectat cu k noduri.

DefinițiiModificare

Un 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țiiModificare

Combinatorică poliedricăModificare

1-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ăModificare

Conexitatea 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  .

NoteModificare

  1. ^ a b en Schrijver (), Combinatorial Optimization, Springer, ISBN 9783540443896 
  2. ^ Dana Lica, Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan, edu.ro, 2007, accesat 2022-08-21
  3. ^ en The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291

BibliografieModificare