Grafic cubic

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Graficul Petersen este un grafic cub
Graficul bipartit complet este un exemplu de grafic bicubic

În câmpul matematic al teoriei graficelor , un grafic cub este un grafic în care toate vârfurile au gradul trei. Cu alte cuvinte, un grafic cub este un grafic regulat cu 3. Graficele cubice se mai numesc grafice trivalente .

Un grafic bicubic este un grafic cub bipartit .

Simetrie

În 1932, Ronald M. Foster a început să colecteze exemple de grafice simetrice cubice, creând primul nucleu al arhivei recensământului Foster ( recensământul Foster ). [1] Multe grafice individuale bine cunoscute sunt cubice și simetrice, inclusiv graficul serviciilor , graficul Petersen , graficul Heawood , graficul Möbius-Kantor , graficul Pappus , graficul Desargues , graficul Nauru , graficul Coxeter , graficul Graficul All-Coxeter , graficul Dyck , graficul Foster și graficul Biggs-Smith . William Thomas Tutti a clasificat graficele cubice simetrice cu cel mai mic număr integral s astfel încât oricare două căi orientate de lungime s pot fi mapate între ele exact pe baza unei simetrii a graficului. El a arătat că s este cel mult 5 și a dat exemple de grafice cu fiecare valoare posibilă a lui s de la 1 la 5. [2]

Graficele cubice semi-simetrice includ graficul lui Gray (cel mai mic grafic cub semisimetric), graficul Ljubljana și cușca Tutti 12 .

Graficul Frucht este unul dintre cele mai mici grafice cubice fără simetrii: posedă doar un singur automorfism grafic , identitatea automorfismului.

Colorare și seturi independente

Conform teoremei lui Brooks, fiecare grafic cub, altul decât graficul complet K 4, poate fi colorat cu maximum trei culori. Prin urmare, fiecare grafic cub, altul decât K 4, are un set independent de cel puțin n / 3 vârfuri, unde n este numărul de vârfuri din grafic: de exemplu, cea mai mare clasă de culoare dintr-o 3-colorare are cel puțin la fel de mulți vârfuri. .

Conform teoremei lui Vizing, fiecare grafic cub are nevoie de trei sau patru culori pentru a colora marginile. O colorare cu 3 margini este cunoscută sub numele de colorare Tait și formează o partiție a marginilor grafului în trei perechi perfecte . Prin teorema de colorare a liniei lui König, fiecare grafic bicubic are o colorare Tait.

Graficele cubice fără punte care nu au o culoare Tait sunt cunoscute sub numele de snarks . Acestea includ graficul Petersen , graficul Tietze , snarkul Blanuša , snarkul de flori , snarkul cu stea dublă, snarkul Szekeres și snarkul Watkins . Există un număr infinit de snarks distincte. [3]

Topologie și geometrie

Graficele cubice apar în mod natural în topologie în mai multe moduri. De exemplu, dacă considerăm un grafic ca fiind un complex celular unidimensional, gradele cubice sunt generice în sensul că majoritatea hărților atașate unei celule sunt disjuncte de scheletul 0 al graficului. Graficele cubice sunt, de asemenea, formate în trei dimensiuni, cum ar fi graficele poliedrelor simple , poliedre, cum ar fi dodecaedrul regulat, cu proprietatea pe care aceste trei fețe o întâlnesc la fiecare vârf.

O „ încorporare a graficelor (încorporarea) unei suprafețe bidimensionale poate fi reprezentată ca o structură cubică a graficului cunoscută sub numele de hartă codificată a graficelor . În această structură, fiecare vârf al unui grafic cub reprezintă un steag al încorporării, un triplu incident reciproc al unui vârf, margine și față de suprafață. Cei trei vecini ai fiecărui steag sunt cei trei steaguri care pot fi obținuți de la acesta prin schimbarea unuia dintre membrii acestui triplu incident reciproc și lăsarea neschimbată a celorlalți doi membri. [4]

Hamiltonitatea

S-au făcut multe cercetări asupra hamiltonicității graficelor cubice. În 1880, PG Tait a conjecturat că fiecare grafic poliedric cub are un circuit hamiltonian . William Thomas Tutti a oferit un contraexemplu conjecturii lui Tait , graficul cu 46 de vârfuri al Tutti, în 1946. În 1971, Tutti a presupus că toate graficele bicubice sunt hamiltoniene. Cu toate acestea, Joseph Horton a furnizat un contraexemplu cu 96 de vârfuri, graficul Horton . [5] Mai târziu, Mark Ellingham a construit încă două contraexemple: graficele Ellingham-Horton . [6] [7] Conjectura lui Barnette , o combinație încă deschisă a conjecturilor lui Tait și a lui Tutti, afirmă că fiecare grafic poliedric bicubic este hamiltonian. Când un grafic cub este hamiltonian, notația LCF îi permite să fie reprezentată concis.

Dacă un grafic cub este ales în mod aleatoriu uniform între toate graficele cubice cu n vârfuri, atunci este foarte probabil să fie hamiltonian: proporția graficelor cubice cu n vârfuri care sunt hamiltoniene tinde la limita la unu când n merge la infinit. [8]

David Eppstein a conjecturat că fiecare grafic cub cu n vârfuri are cel mult 2 n / 3 (aproximativ 1.260 n ) cicluri hamiltoniene distincte și a dat exemple de grafice cubice cu tot atâtea cicluri. [9] Cea mai bună limită superioară care a fost arătată pe numărul de cicluri hamiltoniene distincte este de 1,276 n . [10]

Alte proprietăți

Lățimea căii oricărui grafic cub cu n vârfuri este cel mult n / 6. Cu toate acestea, cea mai cunoscută limită inferioară pe lățimea traseului graficelor cubice este mai mică, 0,082 n . [11]

Rezultă din lema strângerilor de mână , demonstrată de Euler în 1736 ca parte a primului studiu al teoriei graficelor, că fiecare grafic cub are un număr par de vârfuri.

Teorema Petersen afirmă că fiecare grafic fără punți are o potrivire perfectă . [12] Lovász și Plummer au presupus că fiecare grafic cub fără punți are un număr exponențial de potriviri perfecte. Conjectura a fost dovedită recent, arătând că orice grafic cub de legătură cu n vârfuri are cel puțin 2 n / 3656 potriviri perfecte. [13]

Algoritmi și complexitate

Mai mulți cercetători au studiat complexitatea algoritmilor exponențiali de timp limitați la grafice cubice. De exemplu, prin aplicarea programării dinamice unei descompuneri a căii grafului, Fomin și Høie au arătat cum să găsească seturile lor maxime independente în timpul O (2 n / 6 + o (n) ). [11] Problema vânzătorului călător poate fi rezolvată în grafice cubice în timpul O (1.251 n ). [14]

Câteva probleme importante de optimizare a graficelor sunt APX dificile , ceea ce înseamnă că, deși au algoritmi de aproximare al căror raport de aproximare este delimitat de o constantă, nu au scheme polinomiale de aproximare a timpului al căror raport de aproximare tinde la mai puțin de 1 decât P = NP . Acestea includ problemele de găsire a acoperirii vârfurilor , un set maxim independent , un minim set dominant și o tăiere maximă . [15] Numărul de încrucișări (numărul minim de margini care se încrucișează în orice reprezentare a unui grafic ) al unui grafic cub este, de asemenea, NP-dificil pentru grade cubice, dar poate fi aproximat. [16] Problema vânzătorului ambulant pe grafice cubice sa dovedit a fi NP-dificil de aproximat în cadrul oricărui factor mai mic decât în ​​oricare dintre 1.153 / 1.152. [17]

Notă

  1. ^ RM Foster, Circuite geometrice ale rețelelor electrice , în Tranzacțiile Institutului american de ingineri electrici , vol. 51, nr. 2, 1932, 309-317, DOI : 10.1109 / T-AIEE.1932.5056068 .
  2. ^ WT Tutti, Despre simetria graficelor cubice , în Canad. J. Math , voi. 11, 1959, 621–624, DOI : 10.4153 / CJM-1959-057-2 .
  3. ^ R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable , în American Mathematical Monthly , vol. 82, nr. 3, 1975, 221–239, DOI : 10.2307 / 2319844 , JSTOR 2319844 .
  4. ^ C. Paul Bonnington și Charles HC Little, Fundamentele teoriei topologice a graficelor , Springer-Verlag, 1995.
  5. ^ Bondy, JA și Murty, USR Graph Theory with Applications. New York: Olanda de Nord, p. 240, 1976.
  6. ^ Ellingham, MN "Non-Hamiltonian 3-Connected Cubic Matches Graphs." Raport de cercetare nr. 28, Departamentul de Matematică, Univ. Melbourne, Melbourne, 1981.
  7. ^ MN Ellingham și JD Horton, grafice bipartite cubice non-hamiltoniene cu 3 conexiuni , în Journal of Combinatorial Theory , Seria B, vol. 34, nr. 3, 1983, pp. 350–353, DOI : 10.1016 / 0095-8956 (83) 90046-1 .
  8. ^ RW Robinson și NC Wormald, Aproape toate graficele regulate sunt hamiltoniene , în Random Structures and Algorithms , vol. 5, nr. 2, 1994, pp. 363–374, DOI : 10.1002 / rsa.3240050209 .
  9. ^ David Eppstein ,The travel salesman problem for cubic graphs ( PDF ), în Journal of Graph Algorithms and Applications , vol. 11, n. 1, 2007, pp. 61–81, arXiv : cs.DS / 0302030 .
  10. ^ H. Gebauer, Despre numărul de cicluri Hamilton în grafice cu grad mărginit ( PDF ), în Proc. Al 4-lea Workshop de Analitică Algoritmică și Combinatorică (ANALCO '08) [ link rupt ] , 2008.
  11. ^ a b Fedor V. Fomin și Kjartan Høie, Pathwidth of cubic graphs and exact algorithms , în Information Processing Letters , vol. 97, nr. 5, 2006, pp. 191–196, DOI : 10.1016 / j.ipl.2005.10.012 .
  12. ^ Julius Peter Christian Petersen, Die Theorie der regulären Graphs (Teoria graficelor regulate) , în Acta Mathematica , vol. 15, nr. 15, 1891, pp. 193-220, DOI : 10.1007 / BF02392606 .
  13. ^ Louis Esperet, František Kardoš, Andrew D. King, Daniel Král și Serguei Norine, Exponențial multe potriviri perfecte în grafice cubice , în Advances in Mathematics , vol. 227, nr. 4, 2011, pp. 1646–1664, DOI : 10.1016 / j.aim.2011.03.015 .
  14. ^ Kazuo Iwama and Takuya Nakashima, An Impract Exact Algorithm for Cubic Graph TSP , in Computing and Combinatorics , Lecture Notes in Computer Science, vol. 4598, Springer-Verlag, 2007, pp. 108-117, DOI : 10.1007 / 978-3-540-73545-8_13 , ISBN 978-3-540-73544-1 .
  15. ^ Paola Alimonti și Viggo Kann, Unele rezultate APX-complete pentru grafice cubice , în Theoretical Computer Science , vol. 237, 1-2, 2000, pp. 123–134, DOI : 10.1016 / S0304-3975 (98) 00158-3 .
  16. ^ Petr Hliněný, Numărul de încrucișare este greu pentru graficele cubice , în Journal of Combinatorial Theory , Seria B, vol. 96, nr. 4, 2006, pp. 455–471, DOI : 10.1016 / j.jctb.2005.09.009 .
  17. ^ Marek Karpinski și Richard Schmied, Aproximarea durității graficului TSP pe grafice cubice , 2013, arXiv : 1304.6800 .

Alte proiecte

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică
Adus de la „ https://it.wikipedia.org/w/index.php?title=Cubic_Graph&oldid=120788136 ”