Minsta antal grafkantskärningar

I grafteorin är skärningsnumret cr( G ) för en graf G det minsta antalet skärningspunkter av kanter i en platt ritning av en graf G . Till exempel är en graf plan om och endast om dess skärningsnummer är noll.

Den matematiska utgångspunkten för att studera antalet skärningar var det Turan-tegelfabriksproblem som Pal Turan ställde upp , där det krävdes att hitta antalet skärningspunkter för en komplett tvådelad graf K m,n [1] . Samma uppgift ställdes dock i sociologin ungefär samtidigt i samband med konstruktionen av sociogram [2] . Uppgiften fortsätter att spela en stor roll vid grafvisualisering .

Såvida inget annat anges, hänvisar skärningsräkningen till representationer av grafer med alla kurvor. Villkoret för rätlinjeskärning kräver att alla kanter är linjesegment, vilket kan ändra svaret. I synnerhet är antalet rätlinjiga skärningar i en komplett graf lika med det minsta antalet konvexa fyrhörningar som definieras av en uppsättning av n punkter i allmän position, vilket är nära relaterat till problemet med lyckligt slut [3] .

Historik

Under andra världskriget tvingas den ungerske matematikern Pal Turan att arbeta i en tegelfabrik och skjuta en vagn lastad med tegel från ugnarna till lagren. Fabriken hade spår från varje ugn till varje lager, och det var svårare att skjuta vagnen i korsningarna mellan spåren, vilket fick Turan att formulera tegelfabrikens problem: vad är det minsta antalet korsningar av en ritning av en komplett graf ? [4] .

Zarankiewicz försökte lösa Turans problem [5] . Hans bevis innehöll ett fel, men han satte den korrekta övre gränsen

för antalet skärningar av den fullständiga tvådelade grafen K m,n . Hypotesen att denna ojämlikhet i själva verket är en jämlikhet kallas Zarankiewicz-förmodan. Den nedre gränsen upptäcktes bara elva år efter publiceringen nästan samtidigt av Gerhard Ringel och Paul Chester Kainen [6] .

Problemet med att bestämma skärningsnumret för en komplett graf ställdes först av Anthony Hill och dök upp i tryck 1960 [7] . Hill och hans medarbetare John Ernest var två konstruktivistiska konstnärer som var fascinerade av matematik, och de formulerade inte bara problemet, utan formulerade också en övre gräns för förmodan om skärningstal för sådana grafer, som Richard K. Guy publicerade 1960 [7] . Denna gräns är nämligen lika med

vilket ger värdena 1, 3, 9, 18, 36, 60, 100, 150 för p = 5, ..., 12 (sekvens A000241 i OEIS ). En oberoende formulering av gissningen gavs av Thomas L. Saaty 1964 [8] . Saati fann senare att den övre gränsen nås för p ≤ 10 , och Pan och Richter visade att den också nås för p = 11, 12

Om endast raka bågar tillåts krävs fler korsningar. Antalet rätlinjeskärningar för graferna K 5 - K 12 är 1, 3, 9, 19, 36, 62, 102, 153 (sekvens A014540 i OEIS ). Värden för grafer upp till K 27 är kända. För K 28 behövs antingen 7233 eller 7234 korsningar. Ytterligare värden finns samlade i projektet "Antal rätlinjekorsningar" [9] . Intressant nog är det inte känt om de vanliga och rätlinjiga skärningsnumren är desamma för kompletta tvådelade grafer. Om Zarankievich-förmodan är sann, är formeln för skärningsnumret för en komplett graf asymptotiskt sann [10] , det vill säga,

Från och med april 2015 är antalet korsningar känt för ett mycket litet antal graffamiljer. I synnerhet, förutom ett fåtal initiala fall, är antalet skärningspunkter för kompletta grafer, kompletta tvådelade grafer och cykelprodukter fortfarande okänt. Det har varit viss framgång för den nedre gränsen, enligt de Klerk, Maharry, Pasechnik och Richter [11] . En stor översikt över de olika alternativen tillhandahålls av Schäfer [12] .

Albertsons gissning , formulerad av Michael O. Albertson 2007, säger att bland alla grafer med kromatiskt nummer n har den kompletta grafen K n det minsta antalet skärningspunkter. Det vill säga, om Guy-Saatys gissningar om skärningsnumret för en komplett graf är sann, har varje n -kromatisk graf ett skärningsnummer som är minst lika med formeln i hypotesen. Det är känt att detta gäller för n ≤ 16 [13] .

Svårighet

I det allmänna fallet är det en svår uppgift att bestämma antalet skärningspunkter i en graf. Garey och Johnson (Michael Garey, David S. Johnson) 1983 visade att detta problem är NP-hårt [14] . Faktum är att problemet förblir NP-hårt även när det begränsas till kubiska grafer [15] och nästan plana grafer [16] (grafer som blir plana efter att en kant har tagits bort). I synnerhet är definitionen av antalet rätlinjiga skärningar fullständig för den existentiella teorin om reella tal [17] .

Det finns emellertid effektiva algoritmer för att bestämma att antalet skärningar inte överstiger en fast konstant k . Med andra ord är problemet lösbart med en fast parameter [18] [19] . Det är fortfarande svårt för stora k som | V |/2. Det finns också effektiva approximationsalgoritmer för att uppskatta cr( G ) på grafer med begränsad grad [20] . I praktiken används heuristiska algoritmer, till exempel en enkel algoritm som börjar med en graf utan kanter och gradvis lägger till kanter för att erhålla minsta möjliga ytterligare antal korsningar. Denna algoritm används i programmet för det distribuerade beräkningsprojektet "Antal rätlinjekorsningar" [21] .

Antal skärningar av kubiska grafer

De minsta kubikgraferna med korsningar 1-8 är kända (sekvens A110507 i OEIS ).

De minsta kubikgraferna med antalet korsningar: [22]

1 är en komplett tvådelad graf K 3,3 med 6 hörn. 2 är en Petersen-graf med 10 hörn. 3 är en Heawood-graf med 14 hörn. 4 är en Möbius-Cantor-graf med 16 hörn. 5 är en Pappa-graf med 18 hörn. 6 - Desargues graf med 20 hörn. 7 - 4 grafer med 22 hörn (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 - Nauru- graf och McGee-graf (eller (3,7) -cell ) med 24 hörn.

2009 föreslog Ikzu (Exoo) att den minsta kubiska grafen med skärningsnummer 11 är Coxeter-grafen , med skärningsnummer 13 Tatta-Coxeter-grafen , med skärningsnummer 170 Tatta 12-cell [23] [24] .

Olikhet för antalet korsningar

En mycket användbar ojämlikhet för antalet korsningar upptäcktes oberoende av Aitai , Chvatal , Newborn och Szemeredi [25] och Layton [26] :

För oriktade enkla grafer G med n hörn och e kanter så att e > 7 n har vi:

Konstanten 29 är den mest kända. Enligt Ackerman [27] kan konstanten 7 sänkas till 4 , men det kommer att kosta genom att ändra konstanten 29 till 64 .

Anledningen till Leightons intresse för studiet av antalet korsningar var tillämpningen av utvecklingen av VLSI -chips inom teoretisk datavetenskap. Senare insåg Szekely [28] också att denna ojämlikhet ger mycket enkla bevis för några viktiga satser för incidensgeometri , såsom Beck -satsen och Szemeredi-Trotter-satsen , och Tamal Dey använde ojämlikheten för att bevisa en övre gräns för geometriska k- ställer [29] .

För grafer med omkrets större än 2 r och e ≥ 4 n visade Pach, Spencer och Toth [30] en förbättring av denna ojämlikhet

Bevis på olikheten för antalet korsningar

Först ger vi en preliminär uppskattning: för varje graf G med n hörn och e kanter har vi

För att bevisa detta presenterar vi en ritning av en graf G med exakt cr( G ) skärningspunkter. Varje sådan korsning kan tas bort tillsammans med borttagningen av en kant från G. Således kan vi hitta en graf med åtminstone e − cr( G ) kanter och n hörn med noll skärningspunkter, och därför blir det en plan graf . Men från Eulers formel måste vi ha e − cr( G ) ≤ 3 n , varifrån vi får den nödvändiga olikheten. (Vi har faktiskt e − cr( G ) ≤ 3 n − 6 för n ≥ 3 ).

För att få fram skärningstalets olikhet använder vi sannolikhetsresonemang . Låt 0 < p < 1  vara en probabilistisk parameter som ska väljas senare. Konstruera en slumpmässig subgraf H av G genom att placera varje vertex av G i H oberoende med sannolikheten p , och varje kant av G kommer att vara i H om och bara om båda hörn av kanten ligger i H . Låt eH , n H och cr H beteckna antalet kanter, hörn och skärningar av grafen H . Eftersom H är en subgraf av G , finns dess diagram i diagrammet för G. Genom den preliminära ojämlikheten för antalet korsningar har vi

Att beräkna matematiska förväntningar får vi

Eftersom vart och ett av de n hörnen i G har en sannolikhet p att falla in i H , får vi E [ n H ] = pn . På samma sätt har varje kant i G en sannolikhet p 2 att stanna i H eftersom båda ändarna måste vara i H . Således är E [ eH ] = p2e . _ Slutligen har varje skärningspunkt i G sannolikheten p 4 att stanna kvar i H , eftersom varje skärning innefattar fyra hörn. För att förstå detta, föreställ dig ett diagram G med cr( G ) skärningspunkter. Vi kan anta att vilka två kanter som helst i detta diagram med en gemensam vertex inte skär varandra, annars byter vi delar av kanterna tills skärningspunkten och antalet skärningar reduceras med en. Således kan vi anse att skärningspunkten involverar fyra olika hörn av grafen G . Som en konsekvens är E [cr H ] = p 4 cr( G ) och vi får

Om vi ​​nu sätter p = 4 n / e < 1 (eftersom vi antog att e > 4 n ), efter några algebraiska beräkningar, får vi

En liten förändring i ovanstående argumentation gör att vi kan ersätta 64 med 33,75 för e > 7,5 n [31] .

Se även

Anteckningar

  1. ↑ Turán, 1977 , sid. 7-9.
  2. ↑ Bronfenbrenner, 1944 , sid. 283-289.
  3. ↑ Scheinerman, Wilf, 1994 , sid. 939-943.
  4. ↑ Pach, Sharir, 2009 , sid. 126-127.
  5. ↑ Zarankiewicz, 1954 , sid. 137-145.
  6. ↑ Guy, 1969 , sid. 63-69.
  7. ↑ 1 2 Guy, 1960 , sid. 68-72.
  8. ↑ Saaty, 1964 , sid. 688-690.
  9. ↑ Aichholzer .
  10. ↑ Kainen, 1968 , sid. 374-377.
  11. ↑ Klerk, Maharry, Pasechnik, Richter, Salazar, 2006 , sid. 189-202.
  12. ↑ Schäfer, 2014 , sid. #DS21.
  13. ↑ Barát, Toth, 2009 .
  14. ↑ Garey och Johnson, 1983 , sid. 312-316.
  15. ↑ Hliněny, 2006 , sid. 455-471.
  16. ↑ Cabello, Mohar, 2013 , sid. 1803-1829.
  17. ↑ Schäfer, 2010 , sid. 334-344.
  18. ↑ Grohe, 2005 , sid. 285-302.
  19. ↑ Kawarabayashi, Reed, 2007 , sid. 382-390.
  20. ↑ Even, Guha, Schieber, 2003 , sid. 231-252.
  21. ↑ Rectilinear Crossing Number Arkiverad 25 juni 2008 på Wayback Machine , Graz Institute for Software Engineering, University of Technology (2009).
  22. ↑ Weisstein, Eric W. "Smallest Cubic Crossing Number Graph." Från MathWorld - En Wolfram webbresurs. . Hämtad 20 september 2020. Arkiverad från originalet 19 mars 2020.
  23. ↑ Exoo .
  24. ↑ Pegg, Exoo, 2009 .
  25. ↑ Ajtai, Chvátal, Newborn, Szemerédi, 1982 , sid. 9-12.
  26. ↑ Leighton, 1983 .
  27. ↑ Ackerman, 2013 . För tidigare resultat med andra konstanter, se Pach och Toph. Pach, Tóth, 1997 , sid. 427-439, Pach, Radchik, Tardos och Tof Pach, Radoičić, Tardos, Tóth, 2006 , sid. 527-552
  28. ↑ Szekely, 1997 , sid. 353-358.
  29. ↑ Dey, 1998 , sid. 373-382.
  30. ↑ Pach, Spencer, Tóth, 2000 , sid. 623-644.
  31. ↑ Ackerman, 2013 .

Litteratur