Numărarea apexelor

În teoria grafurilor, un graf cu vârfuri este un graf care poate fi făcut plan prin eliminarea unui vârf. Vârful eliminat se numește vârful graficului. Rețineți că pot exista mai multe vârfuri. De exemplu, într-un grafic minim neplanar K 5 sau K 3,3 , fiecare vârf este un vârf. Graficele de vârf includ inițial grafice plane în care fiecare vârf este un vârf. Un graf nul este, de asemenea, considerat apic, deși nu are vârfuri de eliminat.

Graficele apex sunt închise sub operațiunea de generare a minorilor și joacă un rol important în alte câteva aspecte ale teoriei grafurilor minore, inclusiv încorporarea nelegată [1] , conjectura Hadwiger [2] , graficele reductibile YΔY [3] și relația dintre lățimea arborelui și diametrul graficului [4] [5] .

Descriere și recunoaștere

Graficele de vârf sunt închise sub operațiunea de generare a minorilor - micșorarea oricărei muchii sau ștergerea unui vârf sau muchie duce la un alt grafic de vârf. Într-adevăr, dacă G este un grafic de vârf cu vârful v , atunci o contracție sau îndepărtare care nu afectează vârful v păstrează planaritatea restului graficului (fără vârful v ). același lucru este valabil atunci când se elimină orice incident de margine cu v . Dacă o margine incidentă cu v este contractată , efectul este echivalent cu îndepărtarea capătului opus al muchiei. Dacă vârful v însuși este îndepărtat , orice alt vârf poate fi considerat un vârf [6] .

Deoarece graficele vârfurilor sunt închise prin operația de generare a minorilor, prin teorema Robertson-Seymour au o caracterizare prin grafice interzise . Există doar un număr finit de grafice care nu sunt grafice de vârf și nu conțin ca minor un alt grafic non-apex. Aceste grafice sunt minore interzise pentru proprietatea grafului vârfurilor. Orice alt grafic G este vârf dacă și numai dacă niciunul dintre minorii interziși nu este minor al lui G . Minorii interziși includ șapte grafice din familia Petersen , trei grafice deconectate formate din uniuni disjunse de K 5 și K 3,3 și multe alte grafice. O listă completă a tuturor minorilor interziși rămâne incompletă [6] [7] .

În ciuda faptului că lista completă a minorilor interziși nu este cunoscută, este posibil să se verifice în timp liniar dacă un anumit grafic este vârf și, dacă este, să se găsească vârful graficului. Mai general, pentru orice constantă fixă ​​k , graficele k -vertex (grafice în care ștergerea unei mulțimi alese cu grijă care conține cel mult k vârfuri duce la un grafic planar [8] ) pot fi recunoscute în timp liniar . Totuși, dacă k nu este fix, problema devine NP-complet [9] .

Număr cromatic

Orice graf de vârfuri are un număr cromatic care nu depășește cinci - un graf planar fără vârf necesită cel mult patru culori după teorema celor patru culori și o culoare suplimentară este suficientă pentru un vârf. Robertson, Seymour și Thomas [2] au folosit acest fapt pentru a demonstra cazul k  = 6 al conjecturii lui Hadwiger , afirmația că orice graf 6-cromatic are un graf complet K 6 ca minor — au arătat că orice contraexemplu minim pentru conjectura trebuie să fie un grafic de vârf, dar nu există grafice cromatice cu 6 vârfuri, deci nu există un astfel de contraexemplu.

Probleme nerezolvate la matematică : este fiecare graf conectat cu vârfuri 6 fără vârfuri minore?

Jorgensen [10] a presupus că orice graf conectat cu vârfuri 6 care nu are K 6 ca minore trebuie să fie apex. Dacă acest lucru s-ar dovedi, rezultatul Robertson–Seymour–Thomas pentru conjectura Hadwiger ar fi o consecință directă a [2] . Conjectura lui Jorgensen nu a fost încă dovedită [11] . Totuși, dacă presupunerea este falsă, are doar un număr finit de contraexemple [12] .

Lățimea arborelui local

O familie de grafice F are o lățime locală de arbore mărginită dacă graficele din F respectă o relație funcțională între diametru și lățimea arborelui — există o funcție ƒ astfel încât lățimea arborelui unui grafic din F cu diametrul d nu depășește ƒ( d ). Graficele de sus nu au o lățime locală de arbore mărginită - graficul format prin conectarea unui vârf la fiecare vârf al unei rețele n  ×  n are lățimea copacului n și diametrul 2, deci lățimea arborelui nu este delimitată de o funcție a diametrului acestor grafice. . Cu toate acestea, graficele de vârf sunt strâns legate de graficele cu lățime locală de arbore mărginită - familiile minore închise de grafice F care au lățime locală de arbore limitată sunt exact familii ale căror minore interzise sunt niște grafice de vârf [4] [5] . Familiile minore închise de grafice care au un graf apex drept minor sunt cunoscute a fi fără apex minor . Conform acestei terminologii, relația dintre graficele de vârf și lățimea locală a arborelui poate fi reformulată astfel: familiile de grafice fără vârfuri minore coincid cu familiile de grafice închise în minori cu lățime locală de arbore mărginită.

Conceptul de lățime locală de arbore mărginită formează baza teoriei bidimensionalității și permite rezolvarea multor probleme algoritmice pe grafice fără minori de top exact printr-un algoritm de timp polinomial sau printr -un algoritm solubil cu parametri fix , sau problema poate fi aproximată folosind o schemă aproximativă a timpului polinomial [4] [13] [14] . Pentru familiile de grafuri lipsite de minore apicale, este satisfăcută o versiune consolidată a teoremei grafului structural , ceea ce conduce la algoritmi suplimentari de aproximare pentru colorarea grafurilor și pentru problema vânzătorului ambulant [15] . Cu toate acestea, unele dintre aceste rezultate pot fi extinse la familii arbitrare minore-închise de grafuri prin utilizarea teoremelor de structură la grafuri asociate cu familii care sunt libere de apex minors [16] .

Atasamente

Dacă un grafic G este un grafic de vârf cu vârful v și este egal cu numărul minim de fețe necesare pentru a acoperi toate vecinele vârfului v sub o încorporare plană G \{ v }, atunci G poate fi încorporat într-o suprafață de gen bidimensională prin adăugarea acelorași punți la înglobarea plană, conectând astfel toate fețele la care v urmează să fie conectat. De exemplu, adăugarea unui vârf la un graf exterior planar (un graf cu a ) produce un graf planar. Dacă graficul G \{ v } este 3-conectat, granița sa nu diferă de cea optimă cu mai mult decât un factor constant - orice încorporare a lui G într-o suprafață necesită cel puțin . Totuși, problema determinării genului optim pentru o suprafață de încorporare pentru graficele de vârfuri este o problemă NP-hard [17] .

Când se utilizează arbori SPQR pentru a codifica posibile înglobări ale părții plane a graficului de vârf, este posibil să se calculeze în timp polinomial înglobarea graficului pe un plan în care intersecțiile sunt cauzate numai de muchiile care emană de la vârful vârfului și totalul numărul de intersecții este minim [18] . Dacă sunt permise intersecții arbitrare, problema minimizării numărului de intersecții devine NP-grea, chiar și în cazul special al graficelor de vârfuri formate prin adăugarea unei singure muchii la un graf plan [19] .

Graficele vârfuri sunt încorporabile fără a se lega în spațiul tridimensional - ele pot fi încorporate în așa fel încât orice ciclu din grafic să fie limita unui disc care nu este intersectat de nicio altă parte a graficului [20] . Un desen de acest tip poate fi obținut prin desenarea părții plane a graficului pe un plan, plasând partea superioară a graficului deasupra planului și conectându-l la vecinii săi cu segmente. Graficele încorporabile fără link formează o familie minoră închisă cu șapte grafice din familia Petersen ca minori minim interzis [1] . Astfel, aceste grafice sunt minore interzise și pentru graficele de vârf. Există, totuși, grafice care pot fi încorporate fără o legătură și nu sunt apex.

YΔY-reductibilitate

Un graf conectat este YΔY-reductibil dacă poate fi redus la un singur vârf printr-o succesiune de pași, fiecare dintre acestea fiind o transformare Δ-Y sau Y-Δ , eliminând o buclă sau mai multe muchii, eliminând un vârf cu un vecin, și înlocuirea unui vârf de gradul doi și a celor două muchii adiacente ale acestuia cu o muchie [3] .

Ca și graficele de vârf și graficele încorporabile fără legături, graficele reductibile YΔY sunt închise sub operațiunea de generare a minorilor. Asemenea graficelor încorporabile fără legătură, graficele reductibile YΔY au șapte grafice din familia Petersen ca minori minim interzis, ceea ce ridică întrebarea dacă aceste grafice sunt singurii minori interziși și dacă familiile graficelor reductibile YΔY și graficele încorporabile fără legături coincid . Neil Robertson, totuși, a dat un exemplu de grafic de vârf care nu este YΔY-reductibil. Deoarece orice graf de vârf este încorporabil fără o legătură, acest lucru arată că există grafuri încorporabile fără o legătură care nu sunt YΔY-reductibile și, prin urmare, există minore suplimentare interzise pentru grafurile YΔY-reductibile [3] .

Graficul apex Robertson este prezentat în figură. Poate fi obținut prin conectarea vârfului cu toate vârfurile dodecaedrului rombic de gradul trei sau prin îmbinarea a două vârfuri opuse ale graficului hipercub cu patru dimensiuni . Deoarece graficul dodecaedrului rombic este plan, graficul Robertson este apex. Graficul nu conține triunghiuri și are un grad minim de patru, așa că nu i se poate aplica nicio operație de reducere YΔY [3] .

Grafice aproape plane

Dacă un grafic este un vârf, nu are neapărat un singur vârf. De exemplu, în graficele minore-minimale neplanare K 5 și K 3,3 orice vârf poate fi ales ca vârf. Wagner [21] [22] a definit un graf aproape plan ca fiind un graf de vârf neplan în care orice vârf poate servi drept vârf. Astfel , K 5 și K 3,3 sunt grafice aproape plane. El a dat o clasificare a unor astfel de grafice, împărțindu-le în patru familii. O familie constă din grafice care (cum ar fi scări Möbius ) pot fi încorporate într-o bandă Möbius în așa fel încât marginea benzii să coincidă cu ciclul hamiltonian al graficului. Chiar înainte de a demonstra teorema în patru culori , el a demonstrat că orice graf aproape plan poate fi colorat cu cel mult patru culori, cu excepția graficelor formate dintr- o roată cu un ciclu exterior impar prin înlocuirea vârfului central cu două vârfuri adiacente - un astfel de grafic are nevoie de cinci culori. În plus, el a demonstrat că, cu o singură excepție ( complementul cu opt vârfuri al unui cub ), orice graf aproape plan are o încorporare în planul proiectiv .

Cu toate acestea, expresia „graf aproape plan” este foarte ambiguă - același termen a fost folosit pentru graficele de vârf [20] [4] , grafice formate prin adăugarea unei singure muchii la un grafic plan [23] , grafice formate dintr-o încorporare plană a unui grafic prin înlocuirea unui număr limitat de fețe „vârtejuri” cu lățime de cale limitată [24] , precum și alte seturi de grafice mai puțin strict definite.

Note

  1. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  2. ↑ 1 2 3 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 Truemper, 1992 .
  4. ↑ 1 2 3 4 Eppstein, 2000 .
  5. ↑ 1 2 Demaine, Hajiaghayi, 2004 .
  6. ↑ 1 2 Gupta, Impagliazzo, 1991 .
  7. ↑ Pierce, 2014 .
  8. ↑ Kawarabayashi, 2009 .
  9. ↑ Lewis, Yannakakis, 1980 .
  10. ↑ Jørgensen, 1994 .
  11. ↑ Conjectura lui Jorgensen , < http://www.openproblemgarden.org/op/jorgensens_conjecture > . Consultat la 13 noiembrie 2016. Arhivat la 14 noiembrie 2016 la Wayback Machine . 
  12. ↑ Kawarabayashi, Norine, Thomas, Wollan, 2012 .
  13. ↑ Frick, Grohe, 2001 .
  14. ↑ Demaine, Hajiaghayi, 2005 .
  15. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2009 .
  16. ↑ Grohe, 2003 .
  17. ↑ Mohar, 2001 .
  18. ↑ Chimani, Gutwenger, Mutzel, Wolf, 2009 .
  19. ↑ Cabello, Mohar, 2010 .
  20. ↑ 12 Robertson, Seymour, Thomas, 1993c .
  21. ↑ Wagner, 1967 .
  22. ↑ Wagner, 1970 .
  23. ↑ Arhidiacon, Bonnington, 2004 .
  24. ↑ Abraham, Gavoille, 2006 .

Literatură