A gráfél metszéspontjainak minimális száma

A gráfelméletben a G gráf cr( G ) metszéspontja a legkisebb számú élmetszéspont egy G gráf lapos rajzában . Például egy gráf akkor és csak akkor sík , ha metszéspontja nulla.

A metszéspontok számának tanulmányozásának matematikai kiindulópontja a Turán Pál által felvetett turáni téglagyári probléma volt, amelyben meg kellett találni a K m,n teljes kétrészes gráf metszéspontjainak számát [1] . Ugyanezt a feladatot azonban a szociológiában nagyjából ugyanabban az időben tűzték ki a szociogramok felépítése kapcsán [2] . A feladat továbbra is nagy szerepet játszik a gráfvizualizációban .

Hacsak másképp nem jelezzük, a metszéspontok száma a grafikonok bármely görbével való ábrázolására vonatkozik. Az egyenes metszés feltétele megköveteli, hogy minden él vonalszakasz legyen, ami megváltoztathatja a választ. Konkrétan, egy teljes gráf egyenes metszéspontjainak száma egyenlő a konvex négyszögek minimális számával, amelyeket egy általános helyzetben lévő n pontból álló halmaz határoz meg, ami szorosan összefügg a boldog befejezés problémájával [3] .

Történelem

A második világháború idején Turán Pál magyar matematikus egy téglagyárban kénytelen dolgozni, és a kemencékből a raktárakba tolja a téglával megrakott szekeret. A gyárban minden kemencétől minden raktárig sínek voltak, és nehezebb volt tolni a szekeret a vágányok kereszteződésében, ami arra késztette Turánt, hogy megfogalmazza a téglagyár problémáját: mennyi a minimális metszéspontok száma egy teljes rajzon. grafikon ? [4] .

Zarankiewicz megpróbálta megoldani Turan problémáját [5] . Bizonyítása hibát tartalmazott, de helyes felső határt állított be

a teljes kétrészes gráf metszéspontjainak számához K m,n . Azt a hipotézist, hogy ez az egyenlőtlenség valójában egyenlőség, Zarankiewicz-sejtés néven ismerjük. Az alsó határt csak tizenegy évvel a publikáció után fedezte fel Gerhard Ringel és Paul Chester Kainen [6] .

A teljes gráf metszéspontszámának meghatározásának problémáját először Anthony Hill vetette fel, és 1960-ban jelent meg nyomtatásban [7] . Hill és munkatársa, John Ernest két konstruktivista művész volt, akiket lenyűgözött a matematika, és nem csak megfogalmazták a problémát, hanem egy felső korlátot is megfogalmaztak az ilyen gráfok metszéspontszám-sejtésére, amelyet Richard K. Guy 1960-ban publikált [7]. . Ez a határ ugyanis egyenlő

amely az 1, 3, 9, 18, 36, 60, 100, 150 értékeket adja meg p = 5, ..., 12 esetén ( A000241 szekvencia az OEIS -ben ). A sejtés független megfogalmazását Thomas L. Saaty adta meg 1964-ben [8] . Saati később úgy találta, hogy a felső korlát p ≤ 10 esetén érhető el , Pan és Richter pedig kimutatta, hogy p = 11, 12 esetén is eléri.

Ha csak egyenes ívek megengedettek, több kereszteződésre van szükség. A K 5 - K 12 gráfok egyenes metszéspontjainak száma 1 , 3, 9, 19, 36, 62, 102, 153 ( A014540 sorozat az OEIS -ben ). A grafikonok értékei K 27 -ig ismertek. A K 28 -hoz vagy 7233 vagy 7234 keresztezés szükséges. További értékeket az "Egyenes metszéspontok száma" [9] projektben gyűjtünk . Érdekes módon nem ismert, hogy a közönséges és az egyenes metszéspontok száma megegyezik-e a teljes kétrészes gráfoknál. Ha a Zarankievics-sejtés igaz, akkor a teljes gráf metszésszámának képlete aszimptotikusan igaz [10] , azaz

2015 áprilisától a metszéspontok száma nagyon kis számú gráfcsaládról ismert. Néhány kezdeti eset kivételével különösen a teljes gráfok, a teljes kétrészes gráfok és a ciklustermékek metszéspontjainak száma ismeretlen. De Klerk, Maharry, Pasechnik és Richter szerint volt némi siker az alsó határnál [11] . Schaefer [12] nyújt széles körű áttekintést a különféle lehetőségekről .

Albertson sejtése , amelyet Michael O. Albertson fogalmazott meg 2007-ben, azt állítja, hogy az n kromatikus számú gráfok közül a teljes K n gráfnak van a minimális számú metszéspontja. Ez azt jelenti, hogy ha igaz a Guy-Saaty-sejtés egy teljes gráf metszéspontszámáról, akkor bármely n -kromatikus gráf metszéspontszáma legalább egyenlő a hipotézisben szereplő képlettel. Ismeretes, hogy ez n ≤ 16 esetén érvényes [13] .

Nehézség

Általános esetben egy gráf metszéspontjainak számának meghatározása nehéz feladat. Garey és Johnson (Michael Garey, David S. Johnson) 1983-ban kimutatta, hogy ez a probléma NP-nehéz [14] . Valójában a probléma még akkor is NP-nehéz marad, ha csak köbös gráfokra [15] és majdnem síkgráfokra [16] korlátozódik (olyan gráfok, amelyek egy él eltávolítása után síkmá válnak). Különösen az egyenes metszéspontok számának meghatározása teljes a valós számok egzisztenciális elméletéhez [17] .

Vannak azonban hatékony algoritmusok annak meghatározására, hogy a metszéspontok száma ne haladja meg a rögzített k állandót . Vagyis a probléma megoldható egy rögzített paraméterrel [18] [19] . Továbbra is nehéz a nagy k , mint például | V |/2. Hatékony közelítő algoritmusok is léteznek cr( G ) becslésére korlátos fokozatú gráfokon [20] . A gyakorlatban heurisztikus algoritmusokat használnak, például egy egyszerű algoritmust, amely egy él nélküli gráfból indul, és fokozatosan ad hozzá éleket, hogy a lehető legkisebb számú metszéspontot kapja. Ezt az algoritmust az "Egyenes metszéspontok száma" [21] elosztott számítástechnikai projekt programjában használják .

Köbös grafikonok metszéspontjainak száma

Ismeretesek a legkisebb köbös grafikonok 1-8 keresztezésekkel ( A110507 szekvencia az OEIS -ben ).

A legkisebb köbös grafikonok a metszéspontok számával: [22]

Az 1 egy teljes kétrészes gráf K 3,3 6 csúcsgal. A 2 egy 10 csúcsú Petersen-gráf . A 3 egy Heawood gráf 14 csúcsgal. A 4 egy 16 csúcsos Möbius-Cantor gráf . Az 5 egy 18 csúcsos Pappa gráf . 6 - Desargues gráf 20 csúcsgal. 7-4 grafikon 22 csúcsgal (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 - Nauru gráf és McGee gráf (vagy (3,7) -cella ) 24 csúcstal.

2009-ben Ikzu (Exoo) azt javasolta, hogy a legkisebb köbös gráf a 11-es metszésponttal a Coxeter-gráf , a 13 -as metszetszámmal a Tatta-Coxeter-gráf , a 170 -es metszetszámmal pedig a Tatta 12-cellás [23] [24] .

A metszéspontok számának egyenlőtlensége

A metszéspontok számának egy nagyon hasznos egyenlőtlenségét egymástól függetlenül fedezte fel Aitai , Chvatal , Newborn és Szemedi [25] és Layton [26] :

Irányítatlan egyszerű G gráfokhoz n csúcsokkal és e élekkel úgy, hogy e > 7 n :

A 29 -es állandó a legismertebb. Ackerman [27] szerint a 7 -es konstans lecsökkenthető 4 -re , de a 29 - es konstans 64 -re történő módosítása költséges lesz .

Leighton érdeklődését a metszéspontok számának vizsgálata iránt a VLSI chipek elméleti számítástechnikai fejlesztésére való alkalmazása indokolta. Később Székely [28] is rájött, hogy ez az egyenlőtlenség nagyon egyszerű bizonyítékokat ad a beesési geometria néhány fontos tételére , mint például a Beck -tételre és a Szemedi-Trotter-tételre , és Tamal Dey az egyenlőtlenséget használta a geometriai k felső korlátjának bizonyítására. készletek [29] .

A 2 r - nél nagyobb és e ≥ 4 n kerületű gráfoknál Pach, Spencer és Toth [30] javulást mutatott ezen az egyenlőtlenségen.

A metszéspontok számának egyenlőtlenségének bizonyítása

Először adunk egy előzetes becslést: bármely n csúcsú és e élű G gráfra

Ennek bizonyítására bemutatunk egy G gráf rajzát pontosan cr( G ) metszéspontokkal. Minden ilyen metszéspont eltávolítható a G -ből egy él eltávolításával együtt . Így találhatunk egy gráfot, amelynek legalább e − cr( G ) éle és n csúcsa van nulla metszésponttal, és így egy síkgráf lesz . De az Euler-képletből e − cr( G ) ≤ 3 n kell , hogy legyen , ahonnan megkapjuk a szükséges egyenlőtlenséget. (Valójában e − cr( G ) ≤ 3 n − 6 n ≥ 3 esetén ) .

A metszésszám-egyenlőtlenség megszerzéséhez valószínűségi gondolkodást alkalmazunk . Legyen 0 < p < 1  egy későbbi valószínűségi paraméter. Szerkesszük meg G véletlenszerű H részgráfját úgy, hogy G minden csúcsát egymástól függetlenül H -be helyezzük p valószínűséggel , és G minden éle akkor és csak akkor lesz H -ban , ha az él mindkét csúcsa H -ban van . Jelölje e H , n H és cr H a H gráf éleinek, csúcsainak és metszéspontjainak számát. Mivel H G részgráfja , diagramját G diagramja tartalmazza . A kereszteződések számának előzetes egyenlőtlenségével megvan

A matematikai elvárások kiszámításával azt kapjuk, hogy

Mivel G -ben minden n csúcsnak van p valószínűsége , hogy H - ba esik , így kapjuk, hogy E [ n H ] = pn . Ugyanígy G -ben minden élnek p 2 a valószínűsége , hogy H -ben marad, mivel mindkét végnek H -ban kell lennie . Így E [ e H ] = p 2 e . Végül minden G -beli metszéspontnak p 4 a valószínűsége , hogy H -ben marad , mivel minden metszéspont négy csúcsot foglal magában. Ennek megértéséhez képzeljünk el egy G diagramot cr( G ) metszéspontokkal . Feltételezhetjük, hogy ezen a diagramon bármely két közös csúcsú él nem metszi egymást, ellenkező esetben az élek részeit addig cseréljük, amíg a metszéspont és a metszéspontok száma eggyel csökken. Tehát úgy tekinthetjük, hogy a metszéspont a G gráf négy különböző csúcsát foglalja magában . Ennek következtében E [cr H ] = p 4 cr( G ) és azt kapjuk

Most, ha p = 4 n / e < 1 (mivel azt feltételeztük, hogy e > 4 n ), néhány algebrai számítás után azt kapjuk, hogy

A fenti érvelés enyhe változtatása lehetővé teszi, hogy e > 7,5 n esetén a 64 -et 33,75 -re cseréljük [31] .

Lásd még

Jegyzetek

  1. ↑ Turán, 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, Tóth, 2009 .
  14. ↑ Garey és 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. ↑ Egyenes keresztezési szám archiválva : 2008. június 25. a Wayback Machine -nél , Grazi Műszaki Egyetem Szoftvermérnöki Intézete (2009).
  22. ↑ Weisstein, Eric W. "Legkisebb köbös kereszteződési számgrafikon." A MathWorldtől – egy Wolfram webes forrásból. . Letöltve: 2020. szeptember 20. Az eredetiből archiválva : 2020. március 19.
  23. ↑ Exoo .
  24. ↑ Pegg, Exoo, 2009 .
  25. ↑ Ajtai, Chvátal, Újszülött, Szemerédi, 1982 , p. 9-12.
  26. ↑ Leighton, 1983 .
  27. ↑ Ackerman, 2013 . Az egyéb állandókkal kapcsolatos korábbi eredményeket lásd Pach és Toph Pach, Tóth, 1997 , p. 427-439, Pach, Radchik, Tardos and Tof Pach, Radoičić, Tardos, Tóth, 2006 , p. 527-552
  28. ↑ Székely, 1997 , p. 353-358.
  29. ↑ Dey, 1998 , p. 373-382.
  30. ↑ Pach, Spencer, Tóth, 2000 , p. 623-644.
  31. ↑ Ackerman, 2013 .

Irodalom