graf care nu poate fi deconectat prin ștergerea a mai puțin de k noduri From Wikipedia, the free encyclopedia
Î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.
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]
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.
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 .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.