Î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.. Un astfel de desen este uneori menționat ca roza mistică..
Proprietăți Graful complet cu n noduri este notat cu . Unele surse susțin că litera K din această notație vine de la cuvântul german komplett,. 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..
Kn are muchii (un număr triunghiular), și este un graf regulat de grad . Toate grafurile complete sunt propriile lor clici maximale. Acestea sunt maximal întrucât singurul (mulțime de noduri a cărei eliminare ar deconecta graful) este mulțimea tuturor nodurilor. al unui graf complet este .
Dacă muchiile unui graf complet primesc fiecare o , rezultă un graf orientat numit graf turneu.
Numărul de al grafurilor complete este dat de 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... . Aceste numere oferă cea mai mare valoare posibilă a indicelui Hosoya pentru un graf cu n noduri.. numărul de cuplaje perfecte al grafului complet Kn (cu n par) este dat de dublul factorial (n − 1)!!..
Geometrie și topologie Un graf complet cu n noduri reprezintă muchiile unui -Simplex. Din punct de vedere geometric, formează mulțimea muchiilor unui triunghi, a unui tetraedru etc. , un poliedru neconvex cu topologia unui tor, are graful complet ca schelet. Fiecare politop de vecinătate din patru sau mai multe dimensiuni are, de asemenea, un schelet complet.
până la 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 joacă un rol-cheie în caracterizările grafurilor planare: prin , un graf este planar dacă și numai dacă nu conține nici pe , nici ca subdiviziune, și conform același rezultat este valabil pentru în loc de subdiviziuni. Ca parte a , joacă un rol similar ca fiind unul dintre pentru .. Cu alte cuvinte, și așa cum au demonstrat Conway și Gordon, fiecare încorporare a lui î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 conține un ciclu hamiltonian , care este încorporat în spațiu ca .
Exemple Grafurile complete de n noduri, pentru n între 1 și 12, sunt prezentate mai jos, împreună cu numărul de muchii: 140x140px 140x140px 140x140px 140x140px 145x145px 140x140px 143x143px 140x140px 142x142px 140x140px 142x142px 140x140px
Referințe
Legături externe
Complet