Vizualizare sursă pentru „Graf k-conex”

{{DISPLAYTITLE:Graf ''k''-conex}}
[[Fișier:4-connected graph.svg|thumb|Graf 4-conex]]
În [[teoria grafurilor]], un [[graf]] {{mvar|G}} [[conexitate (teoria grafurilor) |conex]] se spune că este '''{{mvar|k}}-conex''' dacă are mai mult de {{mvar|k}} [[nod (teoria grafurilor) |noduri]] și rămâne conex ori de câte ori sunt eliminate mai puțin de {{mvar|k}} noduri.

''[[Conexitate (teoria grafurilor)|Conexitatea]]'' unui graf este cel mai mare {{mvar|k}} pentru care orice nod este conectat cu {{mvar|k}} noduri.

== Definiții ==
Un graf (altul decât un [[graf complet]]) are conexitatea {{mvar|k}} dacă {{mvar|k}} este dimensiunea celui mai mic [[submulțime |subset]] de noduri, astfel încât graful devine neconex dacă se șterg.<ref name="Schrijver">{{en icon}} {{Citation|author=Schrijver|title=Combinatorial Optimization|date=12 February 2003|publisher=Springer|isbn=9783540443896|url=https://books.google.com/books?id=mqGeSQ6dJycC&q=%22k-vertex-connected+%22}}</ref> Grafurile complete nu sunt incluse în această versiune a definiției deoarece nu pot fi deconectate prin ștergerea nodurilor. Graful complet cu {{mvar|n}} noduri are conexitatea {{mvar|n}}&nbsp;&minus;&nbsp;1, valoare implicită rezultată din prima definiție.

O definiție echivalentă este aceea că un graf cu cel puțin două noduri este {{mvar|k}}-conex dacă, pentru fiecare pereche de noduri este posibil să se găsească {{mvar|k}} [[drum (teoria grafurilor) |drumuri]] disjuncte care conectează aceste noduri, v. {{ill-wd| Q928813||teorema lui Menger}} {{Harv|Diestel|2005| p=55}}. Din această definiție rezultă același răspuns, {{mvar|n}}&nbsp;&minus;&nbsp;1, pentru conexitatea grafului complet {{mvar|K<sub>n</sub>}}.<ref name="Schrijver"/>

Se spune că un graf 1-conex este „conex”, un graf 2-conex este „biconex”, unul 3-conex este „triconex” etc.<ref>Dana Lica, [http://campion.edu.ro/arhiva/www/arhiva_2009/papers/paper30.pdf ''Descompunerea unui graf in componente triconexe: Algoritmul - J.E. Hopcroft si R.E. Tarjan''], edu.ro, 2007, accesat 2022-08-21</ref>

== Aplicații ==
=== Combinatorică poliedrică ===
1-{{ill-wd| Q786441||scheletul}} oricărui [[politop convex]] {{mvar|k}}-dimensional formează un graf {{mvar|k}}-conex ([[teorema lui Balinski]], {{harvnb|Balinski|1961}}). O teoremă parțial inversă, {{ill-wd| Q7606897||teorema lui Steinitz}}, afirmă că orice [[graf planar]] 3-conex formează scheletul unui [[poliedru convex]].

== Complexitate computațională ==
Conexitatea nodurilor unui graf de intrare {{mvar|G}} poate fi calculată în timp polinomial în următorul mod:<ref>{{en icon}} ''The algorithm design manual'', p 506, and ''Computational discrete mathematics: combinatorics and graph theory with Mathematica'', p. 290-291</ref> se iau în considerare toate perechile posibile <math>(s, t)</math> de noduri neadiacente de deconectat, folosind teorema lui Menger pentru a justifica faptul că separatorul de dimensiune minimă pentru <math>(s, t)</math> 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 {{ill-wd| Q2585642||fluxului maxim}} în graful dintre <math>s</math> și <math>t</math> cu capacitatea 1 pentru fiecare muchie, observând că un flux de <math>k</math> în acest graf corespunde, prin teorema fluxului integral, la <math>k</math> drumuri disjuncte între perechi de la <math>s</math> la <math>t</math>.

== Note ==
<references responsive />

== Bibliografie ==
* {{en icon}} {{citation
 | last = Balinski
 | first = M. L.
 | issue = 2
 | journal = Pacific Journal of Mathematics
 | pages = 431–434
 | title = On the graph structure of convex polyhedra in ''n''-space
 | volume = 11
 | year = 1961
 | doi = 10.2140/pjm.1961.11.431
 | doi-access = free
 }}
* {{en icon}} {{citation
 | last = Diestel | first = Reinhard
 | edition = 3rd
 | isbn = 978-3-540-26183-4
 | location = Berlin, New York
 | publisher = [[Springer-Verlag]]
 | title = Graph Theory
 | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 | year = 2005}}

{{Portal|Matematică}}

[[Categorie:Teoria grafurilor]]