Numărul minim de intersecții ale marginilor graficului

În teoria graficelor, numărul de intersecție cr( G ) al unui grafic G este cel mai mic număr de intersecții ale muchiilor dintr-un desen plat al unui grafic G . De exemplu, un grafic este plan dacă și numai dacă numărul său de intersecție este zero.

Punctul de plecare matematic pentru studierea numărului de intersecții a fost problema fabricii de cărămidă Turan pusă de Pal Turan , în care se cerea să se găsească numărul de intersecții ale unui graf bipartit complet K m,n [1] . Totuși, aceeași sarcină a fost pusă în sociologie cam în același timp în legătură cu construcția sociogramelor [2] . Sarcina continuă să joace un rol important în vizualizarea graficului .

Dacă nu se menționează altfel, numărul de intersecții se referă la reprezentări ale graficelor după orice curbă. Condiția de intersecție în linie dreaptă necesită ca toate muchiile să fie segmente de linie, ceea ce poate schimba răspunsul. În special, numărul de intersecții drepte ale unui grafic complet este egal cu numărul minim de patrulatere convexe definite de o mulțime de n puncte în poziție generală, care este strâns legată de problema happy end [3] .

Istorie

În timpul celui de-al Doilea Război Mondial, matematicianul maghiar Pal Turan este nevoit să lucreze într-o fabrică de cărămidă, împingând un cărucior încărcat cu cărămizi din cuptoare către depozite. Fabrica avea șine de la fiecare cuptor până la fiecare depozit și era mai dificil să împingi căruciorul la intersecțiile șinelor, ceea ce l-a determinat pe Turan să formuleze problema fabricii de cărămidă: care este numărul minim de intersecții ale unui desen al unui întreg . grafic ? [4] .

Zarankiewicz a încercat să rezolve problema lui Turan [5] . Dovada sa conținea o eroare, dar a stabilit limita superioară corectă

pentru numărul de intersecții ale graficului bipartit complet K m,n . Ipoteza că această inegalitate este de fapt o egalitate este cunoscută sub numele de conjectura Zarankiewicz. Limita inferioară a fost descoperită la numai unsprezece ani după publicarea aproape simultan de Gerhard Ringel și Paul Chester Kainen [6] .

Problema determinării numărului de intersecție a unui grafic complet a fost pusă pentru prima dată de Anthony Hill și a apărut tipărit în 1960 [7] . Hill și colaboratorul său, John Ernest , au fost doi artiști constructiviști care au fost fascinați de matematică și nu numai că au formulat problema, ci au formulat și o limită superioară a conjecturii numărului de intersecție pentru astfel de grafice, pe care Richard K. Guy a publicat-o în 1960 [7] . Și anume, această limită este egală cu

care dă valorile 1, 3, 9, 18, 36, 60, 100, 150 pentru p = 5, ..., 12 (secvența A000241 în OEIS ). O formulare independentă a conjecturei a fost dată de Thomas L. Saaty în 1964 [8] . Saati a descoperit mai târziu că limita superioară este atinsă pentru p ≤ 10 , iar Pan și Richter au arătat că este atinsă și pentru p = 11, 12

Dacă sunt permise numai arce drepte, sunt necesare mai multe intersecții. Numărul de intersecții drepte pentru graficele K 5 - K 12 este 1, 3, 9, 19, 36, 62, 102, 153 (secvența A014540 în OEIS ). Sunt cunoscute valori pentru grafice până la K 27 . Pentru K 28 , sunt necesare fie 7233, fie 7234 traversări. Alte valori sunt colectate în proiectul „Numărul de intersecții în linie dreaptă” [9] . Interesant este că nu se știe dacă numerele de intersecție obișnuite și rectilinie sunt aceleași pentru graficele bipartite complete. Dacă conjectura lui Zarankievici este adevărată, atunci formula pentru numărul de intersecție a unui graf complet este adevărată asimptotic [10] , adică

Din aprilie 2015, numărul de intersecții este cunoscut pentru un număr foarte mic de familii de grafice. În special, cu excepția câtorva cazuri inițiale, numărul de intersecții ale graficelor complete, ale graficelor bipartite complete și ale produselor ciclului rămân necunoscute. A existat un oarecare succes pentru limita inferioară, conform lui de Klerk, Maharry, Pasechnik și Richter [11] . O privire de ansamblu asupra diferitelor opțiuni este oferită de Schaefer [12] .

Conjectura lui Albertson , formulată de Michael O. Albertson în 2007, afirmă că dintre toate graficele cu număr cromatic n , graficul complet K n are numărul minim de intersecții. Adică, dacă conjectura Guy-Saaty despre numărul de intersecție al unui graf complet este adevărată, orice graf n -cromatic are un număr de intersecție cel puțin egal cu formula din ipoteză. Se știe că acest lucru este valabil pentru n ≤ 16 [13] .

Dificultate

În cazul general, determinarea numărului de intersecții ale unui grafic este o sarcină dificilă. Garey și Johnson (Michael Garey, David S. Johnson) în 1983 au arătat că această problemă este NP-hard [14] . De fapt, problema rămâne NP-grea chiar și atunci când este limitată la grafice cubice [15] și grafice aproape plane [16] (grafice care devin plane după ce o muchie este îndepărtată). În special, definiția numărului de intersecții rectilinie este completă pentru teoria existențială a numerelor reale [17] .

Cu toate acestea, există algoritmi eficienți pentru a determina că numărul de intersecții nu depășește o constantă fixă ​​k . Cu alte cuvinte, problema este rezolvabilă cu un parametru fix [18] [19] . Rămâne dificil pentru k mari , cum ar fi | V |/2. Există, de asemenea, algoritmi eficienți de aproximare pentru estimarea cr( G ) pe grafice cu grad mărginit [20] . În practică, se folosesc algoritmi euristici , cum ar fi un algoritm simplu care începe cu un grafic fără muchii și adaugă treptat muchii, astfel încât să se obțină numărul suplimentar minim posibil de intersecții. Acest algoritm este utilizat în programul proiectului de calcul distribuit „Numărul de intersecții drepte” [21] .

Numărul de intersecții ale graficelor cubice

Sunt cunoscute cele mai mici grafice cubice cu încrucișările 1-8 (secvența A110507 în OEIS ).

Cele mai mici grafice cubice cu numărul de intersecții: [22]

1 este un grafic bipartit complet K 3,3 cu 6 vârfuri. 2 este un grafic Petersen cu 10 vârfuri. 3 este un grafic Heawood cu 14 vârfuri. 4 este un grafic Möbius-Cantor cu 16 vârfuri. 5 este un grafic Pappa cu 18 vârfuri. 6 - Graficul Desargues cu 20 de vârfuri. 7 - 4 grafice cu 22 de vârfuri (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 - Graficul Nauru și graficul McGee (sau (3,7) -celulă ) cu 24 de vârfuri.

În 2009, Ikzu (Exoo) a sugerat că cel mai mic grafic cubic cu numărul de intersecție 11 este graficul Coxeter , cu numărul de intersecție 13 graficul Tatta-Coxeter , cu numărul de intersecție 170 cel Tatta cu 12 celule [23] [24] .

Inegalitatea pentru numărul de intersecții

O inegalitate foarte utilă pentru numărul de intersecții a fost descoperită independent de Aitai , Chvatal , Newborn și Szemeredi [25] și Layton [26] :

Pentru graficele simple nedirecționate G cu n vârfuri și e muchii astfel încât e > 7 n avem:

Constanta 29 este cea mai cunoscută. Conform lui Ackerman [27] , constanta 7 poate fi coborâtă la 4 , dar va costa prin schimbarea constantei 29 la 64 .

Motivul interesului lui Leighton pentru studiul numărului de intersecții a fost aplicarea la dezvoltarea cipurilor VLSI în informatica teoretică. Mai târziu, Szekely [28] și-a dat seama că această inegalitate oferă dovezi foarte simple ale unor teoreme importante ale geometriei incidenței , cum ar fi teorema Beck și teorema Szemeredi-Trotter , iar Tamal Dey a folosit inegalitatea pentru a demonstra o limită superioară a geometricului k - seturi [29] .

Pentru graficele cu circumferința mai mare de 2 r și e ≥ 4 n , Pach, Spencer și Toth [30] au arătat o îmbunătățire a acestei inegalități

Dovada inegalității pentru numărul de intersecții

În primul rând, dăm o estimare preliminară: pentru orice grafic G cu n vârfuri și e muchii, avem

Pentru a demonstra acest lucru, prezentăm un desen al unui grafic G cu exact intersecții cr( G ) . Fiecare astfel de intersecție poate fi îndepărtată împreună cu îndepărtarea unei muchii din G. Astfel, putem găsi un graf cu cel puțin e − cr( G ) muchii și n vârfuri cu intersecții zero și, prin urmare, va fi un graf plan . Dar din formula lui Euler trebuie să avem e − cr( G ) ≤ 3 n , de unde obținem inegalitatea cerută. (De fapt, avem e − cr( G ) ≤ 3 n − 6 pentru n ≥ 3 ).

Pentru a obține inegalitatea numărului de intersecție, aplicăm raționamentul probabilistic . Fie 0 < p < 1  un parametru probabilist care va fi ales ulterior. Construiți un subgraf aleatoriu H al lui G plasând fiecare vârf al lui G în H independent cu probabilitatea p , iar fiecare muchie a lui G va fi în H dacă și numai dacă ambele vârfuri ale muchiei se află în H . Fie e H , n H și cr H să desemneze numărul de muchii, vârfuri și , respectiv, intersecții ale graficului H. Deoarece H este un subgraf al lui G , diagrama lui este conținută în diagrama lui G. Prin inegalitatea preliminară pentru numărul de intersecții, avem

Calculând așteptările matematice , obținem

Deoarece fiecare dintre cele n vârfuri din G are o probabilitate p de a cădea în H , obținem E [ n H ] = pn . În același mod, fiecare muchie din G are o probabilitate p 2 de a rămâne în H , deoarece ambele capete trebuie să fie în H . Astfel, E [ e H ] = p 2 e . În cele din urmă, fiecare intersecție din G are probabilitatea p 4 de a rămâne în H , deoarece fiecare intersecție implică patru vârfuri. Pentru a înțelege acest lucru, imaginați-vă o diagramă G cu intersecții cr( G ) . Putem presupune că oricare două muchii din această diagramă cu un vârf comun nu se intersectează, altfel schimbăm părți ale muchiilor până când intersecția și numărul de intersecții se reduce cu una. Astfel, putem considera că intersecția implică patru vârfuri diferite ale graficului G . Ca o consecință, E [cr H ] = p 4 cr( G ) și obținem

Acum, dacă punem p = 4 n / e < 1 (deoarece am presupus că e > 4 n ), după niște calcule algebrice, obținem

O ușoară modificare în argumentația de mai sus ne permite să înlocuim 64 cu 33,75 pentru e > 7,5 n [31] .

Vezi și

Note

  1. ↑ Turan, 1977 , p. 7-9.
  2. ↑ Bronfenbrenner, 1944 , p. 283-289.
  3. ↑ Scheinerman, Wilf, 1994 , p. 939-943.
  4. ↑ Pach, Sharir, 2009 , p. 126-127.
  5. ↑ Zarankiewicz, 1954 , p. 137-145.
  6. ↑ Guy, 1969 , p. 63-69.
  7. ↑ 1 2 Guy, 1960 , p. 68-72.
  8. ↑ Saaty, 1964 , p. 688-690.
  9. ↑ Aichholzer .
  10. ↑ Kainen, 1968 , p. 374-377.
  11. ↑ Klerk, Maharry, Pasechnik, Richter, Salazar, 2006 , p. 189-202.
  12. ↑ Schaefer, 2014 , p. #DS21.
  13. ↑ Barát, Toth, 2009 .
  14. ↑ Garey și Johnson, 1983 , p. 312-316.
  15. ↑ Hliněny, 2006 , p. 455-471.
  16. ↑ Cabello, Mohar, 2013 , p. 1803-1829.
  17. ↑ Schaefer, 2010 , p. 334-344.
  18. ↑ Grohe, 2005 , p. 285-302.
  19. ↑ Kawarabayashi, Reed, 2007 , p. 382-390.
  20. ↑ Even, Guha, Schieber, 2003 , p. 231-252.
  21. ↑ Rectilinear Crossing Number Arhivat 25 iunie 2008 la Wayback Machine , Graz Institute for Software Engineering, University of Technology (2009).
  22. ^ Weisstein , Eric W. „Smallest Cubic Crossing Number Graph”. De la MathWorld--O resursă web Wolfram. . Preluat la 20 septembrie 2020. Arhivat din original la 19 martie 2020.
  23. ↑ Exoo .
  24. ↑ Pegg, Exoo, 2009 .
  25. ↑ Ajtai, Chvátal, Nou-născut, Szemerédi, 1982 , p. 9-12.
  26. ↑ Leighton, 1983 .
  27. ↑ Ackerman, 2013 . Pentru rezultate anterioare cu alte constante, vezi Pach și Toph Pach, Tóth, 1997 , p. 427-439, Pach, Radchik, Tardos și Tof Pach, Radoičić, Tardos, Tóth, 2006 , p. 527-552
  28. ↑ Szekely, 1997 , p. 353-358.
  29. ↑ Dey, 1998 , p. 373-382.
  30. ↑ Pach, Spencer, Tóth, 2000 , p. 623-644.
  31. ↑ Ackerman, 2013 .

Literatură