Minimum antal grafkantskæringer

I grafteori er skæringstallet cr( G ) af en graf G det mindste antal skæringspunkter af kanter i en flad tegning af en graf G . For eksempel er en graf plan , hvis og kun hvis dens skæringsnummer er nul.

Det matematiske udgangspunkt for at studere antallet af skæringspunkter var Turan murstensfabriksproblemet stillet af Pal Turan , hvor det var påkrævet at finde antallet af skæringspunkter for en komplet todelt graf K m,n [1] . Samme opgave blev dog stillet i sociologien nogenlunde samtidig i forbindelse med opbygningen af ​​sociogrammer [2] . Opgaven spiller fortsat en stor rolle i grafvisualisering .

Medmindre andet er angivet, refererer skæringsantal til repræsentationer af grafer ved enhver kurve. Betingelsen for lige linjeskæring kræver, at alle kanter er linjestykker, hvilket kan ændre svaret. Især er antallet af lineære skæringspunkter i en komplet graf lig med det mindste antal konvekse firkanter defineret af et sæt af n punkter i den generelle position, hvilket er tæt forbundet med problemet med lykkelig slutning [3] .

Historie

Under Anden Verdenskrig bliver den ungarske matematiker Pal Turan tvunget til at arbejde på en murstensfabrik, hvor han skubber en vogn fyldt med mursten fra ovnene til pakhusene. Fabrikken havde spor fra hver ovn til hvert lager, og det var sværere at skubbe vognen ved sporens skæringspunkter, hvilket fik Turan til at formulere murstensfabrikkens problem: hvad er minimumsantallet af krydsninger af en tegning af en komplet graf ? [4] .

Zarankiewicz forsøgte at løse Turans problem [5] . Hans bevis indeholdt en fejl, men han satte den korrekte øvre grænse

for antallet af skæringspunkter for den komplette todelte graf K m,n . Hypotesen om, at denne ulighed i virkeligheden er en lighed, er kendt som Zarankiewicz-formodningen. Den nedre grænse blev opdaget kun elleve år efter offentliggørelsen næsten samtidigt af Gerhard Ringel og Paul Chester Kainen [6] .

Problemet med at bestemme skæringsnummeret for en komplet graf blev først stillet af Anthony Hill og udkom på tryk i 1960 [7] . Hill og hans samarbejdspartner John Ernest var to konstruktivistiske kunstnere , der var fascineret af matematik, og de formulerede ikke kun problemet, men formulerede også en øvre grænse for formodningen om skæringstal for sådanne grafer, som Richard K. Guy offentliggjorde i 1960 [7] . Denne grænse er nemlig lig med

hvilket giver værdierne 1, 3, 9, 18, 36, 60, 100, 150 for p = 5, ..., 12 (sekvens A000241 i OEIS ). En uafhængig formulering af formodningen blev givet af Thomas L. Saaty i 1964 [8] . Saati fandt senere ud af, at den øvre grænse nås for p ≤ 10 , og Pan og Richter viste, at den også nås for p = 11, 12

Hvis kun lige buer er tilladt, kræves der flere kryds. Antallet af lige linjeskæringer for graferne K 5 - K 12 er 1, 3, 9, 19, 36, 62, 102, 153 (sekvens A014540 i OEIS ). Værdier for grafer op til K 27 er kendte. Til K 28 kræves enten 7233 eller 7234 krydsninger. Yderligere værdier er samlet i projektet "Antal lineære kryds" [9] . Interessant nok vides det ikke, om de almindelige og retlinede skæringsnumre er de samme for komplette todelte grafer. Hvis Zarankievich-formodningen er sand, så er formlen for skæringstallet for en komplet graf asymptotisk sand [10] , dvs.

Fra april 2015 er antallet af kryds kendt for et meget lille antal familier af grafer. Især, bortset fra nogle få indledende tilfælde, forbliver antallet af skæringspunkter mellem komplette grafer, komplette todelte grafer og cyklusprodukter ukendt. Der har været en vis succes for den nedre grænse, ifølge de Klerk, Maharry, Pasechnik og Richter [11] . En stor oversigt over de forskellige muligheder er leveret af Schäfer [12] .

Albertsons formodning , formuleret af Michael O. Albertson i 2007, siger, at blandt alle grafer med kromatisk tal n har den komplette graf K n det mindste antal skæringspunkter. Det vil sige, at hvis Guy-Saatys formodning om skæringstallet for en komplet graf er sand, har enhver n -kromatisk graf et skæringsnummer, der mindst er lig med formlen i hypotesen. Det er kendt, at dette gælder for n ≤ 16 [13] .

Sværhedsgrad

I det generelle tilfælde er det en vanskelig opgave at bestemme antallet af skæringspunkter i en graf. Garey og Johnson (Michael Garey, David S. Johnson) viste i 1983, at dette problem er NP-hårdt [14] . Faktisk forbliver problemet NP-hårdt, selv når det er begrænset til kubiske grafer [15] og næsten plane grafer [16] (grafer, der bliver plane efter at en kant er fjernet). Især er definitionen af ​​antallet af retlineære skæringspunkter fuldstændig for den eksistentielle teori om reelle tal [17] .

Der er dog effektive algoritmer til at bestemme, at antallet af skæringspunkter ikke overstiger en fast konstant k . Med andre ord kan problemet løses med en fast parameter [18] [19] . Det forbliver svært for store k som | V |/2. Der er også effektive tilnærmelsesalgoritmer til at estimere cr( G ) på grafer med afgrænset grad [20] . I praksis bruges heuristiske algoritmer, såsom en simpel algoritme, der starter med en graf uden kanter og gradvist tilføjer kanter for at opnå det mindst mulige yderligere antal skæringspunkter. Denne algoritme bruges i programmet for det distribuerede computerprojekt "Antal lineære skæringspunkter" [21] .

Antal skæringspunkter for kubiske grafer

De mindste kubiske grafer med kryds 1-8 kendes (sekvens A110507 i OEIS ).

De mindste kubiske grafer med antallet af skæringspunkter: [22]

1 er en komplet todelt graf K 3,3 med 6 toppunkter. 2 er en Petersen-graf med 10 hjørner. 3 er en Heawood-graf med 14 hjørner. 4 er en Möbius-Cantor graf med 16 hjørner. 5 er en Pappa-graf med 18 hjørner. 6 - Desargues graf med 20 hjørner. 7 - 4 grafer med 22 hjørner (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 - Nauru -graf og McGee-graf (eller (3,7) -celle ) med 24 hjørner.

I 2009 foreslog Ikzu (Exoo), at den mindste kubiske graf med skæringsnummer 11 er Coxeter-grafen , med skæringsnummer 13 Tatta-Coxeter-grafen , med skæringsnummer 170 Tatta 12-celle [23] [24] .

Ulighed for antallet af kryds

En meget nyttig ulighed for antallet af kryds blev opdaget uafhængigt af Aitai , Chvatal , Newborn og Szemeredi [25] og Layton [26] :

For urettede simple grafer G med n toppunkter og e kanter, således at e > 7 n har vi:

Konstanten 29 er den bedst kendte. Ifølge Ackerman [27] kan konstanten 7 sænkes til 4 , men det vil koste ved at ændre konstanten 29 til 64 .

Årsagen til Leightons interesse i undersøgelsen af ​​antallet af kryds var anvendelsen til udviklingen af ​​VLSI -chips i teoretisk datalogi. Senere indså Szekely [28] også, at denne ulighed giver meget enkle beviser for nogle vigtige sætninger om incidensgeometri , såsom Beck -sætningen og Szemeredi-Trotter-sætningen , og Tamal Dey brugte uligheden til at bevise en øvre grænse for geometriske k- sætter [29] .

For grafer med omkreds større end 2 r og e ≥ 4 n viste Pach, Spencer og Toth [30] en forbedring af denne ulighed

Bevis for uligheden for antallet af kryds

Først giver vi et foreløbigt skøn: for enhver graf G med n toppunkter og e kanter har vi

For at bevise dette præsenterer vi en tegning af en graf G med nøjagtigt cr( G ) skæringspunkter. Hvert sådant kryds kan fjernes sammen med fjernelse af en kant fra G. Således kan vi finde en graf med mindst e − cr( G ) kanter og n toppunkter med nul skæringspunkter, og derfor vil det være en plan graf . Men ud fra Eulers formel skal vi have e − cr( G ) ≤ 3 n , hvorfra vi får den nødvendige ulighed. (Faktisk har vi e − cr( G ) ≤ 3 n − 6 for n ≥ 3 ).

For at opnå uligheden i skæringstallet anvender vi sandsynlighedsræsonnement . Lad 0 < p < 1  være en probabilistisk parameter, der skal vælges senere. Konstruer en tilfældig undergraf H af G ved at placere hvert toppunkt af G i H uafhængigt med sandsynlighed p , og hver kant af G vil være i H hvis og kun hvis begge hjørner af kanten ligger i H . Lad eH , n H og cr H angive antallet af henholdsvis kanter, toppunkter og skæringspunkter på grafen H . Da H er en undergraf af G , er dens diagram indeholdt i diagrammet af G. Ved den foreløbige ulighed for antallet af kryds, har vi

Beregning af matematiske forventninger , får vi

Da hvert af de n hjørner i G har en sandsynlighed p for at falde ind i H , får vi E [ n H ] = pn . På samme måde har hver kant i G en sandsynlighed p 2 for at blive i H , da begge ender skal være i H . Således er E [ eH ] = p2e . _ Endelig har hvert skæringspunkt i G sandsynligheden p 4 for at forblive i H , da hvert skæringspunkt involverer fire hjørner. For at forstå dette skal du forestille dig et diagram G med cr( G ) skæringspunkter. Vi kan antage, at alle to kanter i dette diagram med et fælles toppunkt ikke skærer hinanden, ellers udveksler vi dele af kanterne, indtil skæringspunktet og antallet af skæringspunkter er reduceret med én. Således kan vi overveje, at skæringspunktet involverer fire forskellige hjørner af grafen G . Som en konsekvens, E [cr H ] = p 4 cr( G ), og vi får

Nu, hvis vi sætter p = 4 n / e < 1 (da vi antog, at e > 4 n ), efter nogle algebraiske beregninger, får vi

En lille ændring i ovenstående argumentation giver os mulighed for at erstatte 64 med 33,75 for e > 7,5 n [31] .

Se også

Noter

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

Litteratur