Graf complet

În domeniul matematic al teoriei grafurilor, un graf complet este un graf neorientat simplu în care fiecare pereche de noduri distincte este conectată printr-o muchie unică. Un digraf complet este un graf orientat în care fiecare pereche de noduri distincte este conectată printr-o pereche de muchii unice (una în fiecare direcție).

De obicei, data de naștere a teoriei grafurilor este considerată a fi activitatea lui Leonhard Euler din 1736 la problema celor șapte poduri din Königsberg. Cu toate acestea, desene de grafuri complete, cu nodurile plasate în vârfurile unui poligon regulat, apăruseră deja în secolul al XIII-lea, în lucrările lui Ramon Llull.^[1] Un astfel de desen este uneori menționat ca roza mistică.^[2]

Proprietăți

Graful complet cu n noduri este notat cu $K n$ . Unele surse susțin că litera K din această notație vine de la cuvântul german komplett,^[3] dar numele german pentru un graf complet este vollständiger Graph, și nu conține litera K, iar alte surse afirmă că notația este în cinstea contribuțiilor lui Kazimierz Kuratowski în teoria grafurilor.^[4]

K_n are $n (n - 1)/2$ muchii (un număr triunghiular), și este un graf regulat de grad $n - 1$ . Toate grafurile complete sunt propriile lor clici maximale. Acestea sunt maximal conexe^⁠(d) întrucât singurul separator^⁠(d) (mulțime de noduri a cărei eliminare ar deconecta graful) este mulțimea tuturor nodurilor. Graful complementar^⁠(d) al unui graf complet este graful vid^⁠(d).

Dacă muchiile unui graf complet primesc fiecare o orientare^⁠(d), rezultă un graf orientat numit graf turneu.

Numărul de cuplaje^⁠(d) al grafurilor complete este dat de numerele telefonice^⁠(d)

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... Șirul A000085 la Enciclopedia electronică a șirurilor de numere întregi (OEIS).

Aceste numere oferă cea mai mare valoare posibilă a indicelui Hosoya pentru un graf cu n noduri.^[5] numărul de cuplaje perfecte al grafului complet K_n (cu n par) este dat de dublul factorial (n − 1)!!.^[6]

Geometrie și topologie

Un graf complet cu n noduri reprezintă muchiile unui $(n - 1)$ -Simplex. Din punct de vedere geometric, $K 3$ formează mulțimea muchiilor unui triunghi, $K 4$ a unui tetraedru etc. Poliedrul Császár^⁠(d), un poliedru neconvex cu topologia unui tor, are graful complet $K 7$ ca schelet. Fiecare politop de vecinătate din patru sau mai multe dimensiuni are, de asemenea, un schelet complet.

$K 1$ până la $K 4$ sunt grafuri planare. Cu toate acestea, fiecare desen planar al unui graf complet cu cinci sau mai multe noduri trebuie să conțină o trecere, și graful complet neplanar $K 5$ joacă un rol-cheie în caracterizările grafurilor planare: prin teorema lui Kuratowski^⁠(d), un graf este planar dacă și numai dacă nu conține nici pe $K 5$ , nici graful bipartit complet^⁠(d) $K 3,3$ ca subdiviziune, și conform teoremei lui Wagner^⁠(d) același rezultat este valabil pentru minorii de graf^⁠(d) în loc de subdiviziuni. Ca parte a familiei Petersen^⁠(d), $K 6$ joacă un rol similar ca fiind unul dintre minorii interziși^⁠(d) pentru încorporarea fără legături^⁠(d).^[7] Cu alte cuvinte, și așa cum au demonstrat Conway și Gordon,^[8] fiecare încorporare a lui $K 6$ în spațiul tridimensional este intrinsec legată cu cel puțin o pereche de triunghiuri legate. Conway și Gordon au arătat și că orice încorporare tridimensională a lui $K 7$ conține un ciclu hamiltonian , care este încorporat în spațiu ca nod netrivial^⁠(d).

Exemple

Grafurile complete de n noduri, pentru n între 1 și 12, sunt prezentate mai jos, împreună cu numărul de muchii:

$K 1 : 0$	$K 2 : 1$	$K 3 : 3$	$K 4 : 6$

$K 5 : 10$	$K 6 : 15$	$K 7 : 21$	$K 8 : 28$

$K 9 : 36$	$K 10 : 45$	$K 11 : 55$	$K 12 : 66$

Referințe

^ Knuth, Donald E. (2013), „Two thousand years of combinatorics”, În Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern (în engleză), Oxford University Press, pp. 7–37 .
^ Mystic Rose, nrich.maths.org, accesat în 23 ianuarie 2012 .
^ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 436 .
^ Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p. 154, ISBN 9780201308150 .
^ Tichy, Robert F.; Wagner, Stephan (2005), „Extremal problems for topological indices in combinatorial chemistry” (PDF), Journal of Computational Biology^⁠(d), 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004 .
^ Callan, David (2009), A combinatorial survey of identities for the double factorial .
^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), „Linkless embeddings of graphs in 3-space”, Bulletin of the American Mathematical Society, 28 (1): 84–89, doi:10.1090/S0273-0979-1993-00335-5 .
^ Conway, J. H.; Cameron Gordon (1983). „Knots and Links in Spatial Graphs”. J. Graph Th. 7 (4): 445–453. doi:10.1002/jgt.3190070410.

Legături externe

Portal Matematică

en Eric W. Weisstein, Complete Graph la MathWorld.

[1] Knuth, Donald E. (2013), „Two thousand years of combinatorics”, În Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern (în engleză), Oxford University Press, pp. 7–37 .

[2] Mystic Rose, nrich.maths.org, accesat în 23 ianuarie 2012 .

[3] Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 436 .

[4] Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p. 154, ISBN 9780201308150 .

[5] Tichy, Robert F.; Wagner, Stephan (2005), „Extremal problems for topological indices in combinatorial chemistry” (PDF), Journal of Computational Biology^⁠(d), 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004 .

[6] Callan, David (2009), A combinatorial survey of identities for the double factorial .

[7] Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), „Linkless embeddings of graphs in 3-space”, Bulletin of the American Mathematical Society, 28 (1): 84–89, doi:10.1090/S0273-0979-1993-00335-5 .

[8] Conway, J. H.; Cameron Gordon (1983). „Knots and Links in Spatial Graphs”. J. Graph Th. 7 (4): 445–453. doi:10.1002/jgt.3190070410.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]