Minimální počet průsečíků hran grafu

V teorii grafů je číslo průsečíku cr( G ) grafu G nejmenším počtem průsečíků hran v plochém kreslení grafu G . Například graf je rovinný právě tehdy, když je jeho průsečík číslo nula.

Matematickým výchozím bodem pro studium počtu průsečíků byl problém cihelny Turan předložený Palem Turanem , ve kterém bylo požadováno najít počet průsečíků úplného bipartitního grafu K m,n [1] . Stejný úkol si však přibližně ve stejné době kladla i sociologie v souvislosti s konstrukcí sociogramů [2] . Úloha nadále hraje velkou roli ve vizualizaci grafů .

Pokud není uvedeno jinak, počet průsečíků se týká znázornění grafů libovolnými křivkami. Podmínka průsečíku přímky vyžaduje, aby všechny hrany byly úsečky, což může změnit odpověď. Konkrétně počet přímých průsečíků úplného grafu je roven minimálnímu počtu konvexních čtyřúhelníků definovaných množinou n bodů v obecné poloze, což úzce souvisí s problémem šťastného konce [3] .

Historie

Během druhé světové války je maďarský matematik Pal Turan nucen pracovat v cihelně a tlačí vozík naložený cihlami z pecí do skladů. Továrna měla koleje od každé pece do každého skladu a bylo obtížnější tlačit vozík na křižovatkách kolejí, což vedlo Turana k formulaci problému cihelny: jaký je minimální počet průsečíků výkresu kompletního graf ? [4] .

Zarankiewicz se pokusil vyřešit Turanův problém [5] . Jeho důkaz obsahoval chybu, ale nastavil správnou horní hranici

pro počet průsečíků úplného bipartitního grafu K m,n . Hypotéza, že tato nerovnost je ve skutečnosti rovností, je známá jako Zarankiewiczova domněnka. Spodní hranici objevili pouhých jedenáct let po publikaci téměř současně Gerhard Ringel a Paul Chester Kainen [6] .

Problém určování průsečíkového čísla kompletního grafu byl poprvé položen Anthony Hillem a objevil se v tisku v roce 1960 [7] . Hill a jeho spolupracovník John Ernest byli dva konstruktivističtí umělci , kteří byli fascinováni matematikou a nejenže formulovali problém, ale také formulovali horní mez odhadu počtu průniků pro takové grafy, které Richard K. Guy publikoval v roce 1960 [7]. . Totiž, tato hranice se rovná

což dává hodnoty 1, 3, 9, 18, 36, 60, 100, 150 pro p = 5, ..., 12 (sekvence A000241 v OEIS ). Nezávislou formulaci domněnky podal Thomas L. Saaty v roce 1964 [8] . Saati později zjistil, že horní hranice je dosažena pro p ≤ 10 a Pan a Richter ukázali, že je dosaženo také pro p = 11, 12

Pokud jsou povoleny pouze přímé oblouky, je zapotřebí více průsečíků. Počet průsečíků přímek pro grafy K 5 - K 12 je 1, 3, 9, 19, 36, 62, 102, 153 (sekvence A014540 v OEIS ). Hodnoty pro grafy do K 27 jsou známy. Pro K 28 je potřeba buď 7233 nebo 7234 přejezdů. Další hodnoty jsou shromažďovány v projektu "Počet přímkových křižovatek" [9] . Je zajímavé, že není známo, zda jsou obyčejná a přímočará čísla průsečíků stejná pro úplné bipartitní grafy. Pokud je Zarankievichova domněnka pravdivá, pak vzorec pro průsečíkové číslo úplného grafu je asymptoticky pravdivý [10] , tzn.

Od dubna 2015 je počet křižovatek znám pro velmi malý počet rodin grafů. Zejména, kromě několika počátečních případů, počet průsečíků úplných grafů, úplných bipartitních grafů a produktů cyklu zůstává neznámý. Podle de Klerka, Maharryho, Pasechnika a Richtera [11] zaznamenala dolní hranice určitý úspěch . Velký přehled různých možností poskytuje Schaefer [12] .

Albertsonův odhad , formulovaný Michaelem O. Albertsonem v roce 2007, uvádí, že ze všech grafů s chromatickým číslem n má úplný graf K n minimální počet průsečíků. To znamená, že pokud je Guy-Saatyho domněnka o čísle průsečíku úplného grafu pravdivá, každý n -chromatický graf má číslo průsečíku alespoň rovné vzorci v hypotéze. Je známo, že to platí pro n ≤ 16 [13] .

Obtížnost

V obecném případě je určení počtu průsečíků grafu obtížným úkolem. Garey a Johnson (Michael Garey, David S. Johnson) v roce 1983 ukázali, že tento problém je NP-těžký [14] . Ve skutečnosti problém zůstává NP-těžký, i když je omezen na kubické grafy [15] a téměř rovinné grafy [16] (grafy, které se stanou rovinnými po odstranění jedné hrany). Zejména definice počtu přímočarých průsečíků je kompletní pro existenciální teorii reálných čísel [17] .

Existují však účinné algoritmy pro určení, že počet průsečíků nepřekročí pevnou konstantu k . Jinými slovy, problém je řešitelný s pevným parametrem [18] [19] . Zůstává obtížné pro velká k , jako je | V |/2. Existují také účinné aproximační algoritmy pro odhad cr( G ) na grafech s omezeným stupněm [20] . V praxi se používají heuristické algoritmy, jako je jednoduchý algoritmus, který začíná grafem bez hran a postupně přidává hrany tak, aby se získal minimální možný přídavný počet průsečíků. Tento algoritmus je použit v programu projektu distribuovaných výpočtů "Počet průsečíků přímek" [21] .

Počet průsečíků kubických grafů

Nejmenší kubické grafy s kříženími 1-8 jsou známy (sekvence A110507 v OEIS ).

Nejmenší kubické grafy s počtem průsečíků: [22]

1 je kompletní bipartitní graf K 3,3 se 6 vrcholy. 2 je Petersenův graf s 10 vrcholy. 3 je Heawoodův graf se 14 vrcholy. 4 je Möbiův-Cantorův graf se 16 vrcholy. 5 je Pappa graf s 18 vrcholy. 6 - Desargues graf s 20 vrcholy. 7 - 4 grafy s 22 vrcholy (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 - Nauruův graf a McGeeův graf (nebo (3,7) -buňka ) s 24 vrcholy.

V roce 2009 Ikzu (Exoo) navrhl, že nejmenší kubický graf s číslem průsečíku 11 je Coxeterův graf , s průsečíkem číslo 13 graf Tatta-Coxeter , s průsečíkem číslo 170 12-buňka Tatta [23] [24] .

Nerovnost pro počet křižovatek

Velmi užitečnou nerovnost pro počet průsečíků nezávisle na sobě objevili Aitai , Chvatal [ , Newborn a Szemeredi [25] a Layton [26] :

Pro neorientované jednoduché grafy G s n vrcholy a e hranami takovými, že e > 7 n máme:

Konstanta 29 je nejznámější. Podle Ackermana [27] lze konstantu 7 snížit na 4 , ale bude to stát změnou konstanty 29 na 64 .

Důvodem Leightonova zájmu o studium počtu průsečíků byla aplikace na vývoj VLSI čipů v teoretické informatice. Později si Szekely [28] také uvědomil, že tato nerovnost poskytuje velmi jednoduché důkazy některých důležitých teorémů incidenční geometrie , jako je Beckova věta a Szemeredi-Trotterova věta , a Tamal Dey použil nerovnost k prokázání horní hranice geometrického k- sady [29] .

U grafů s obvodem větším než 2 r a e ≥ 4 n vykázali Pach, Spencer a Toth [30] zlepšení této nerovnosti.

Důkaz nerovnosti pro počet křižovatek

Nejprve uvedeme předběžný odhad: pro každý graf G s n vrcholy a e hranami máme

Abychom to dokázali, předkládáme nákres grafu G s přesně cr( G ) průsečíky. Každý takový průsečík může být odstraněn spolu s odstraněním hrany z G . Můžeme tedy najít graf s alespoň e − cr( G ) hranami a n vrcholy s nulovými průsečíky, a bude to tedy rovinný graf . Ale z Eulerova vzorce musíme mít e − cr( G ) ≤ 3 n , odkud dostaneme požadovanou nerovnost. (Ve skutečnosti máme e − cr( G ) ≤ 3 n − 6 pro n ≥ 3 ).

K získání průsečíkové číselné nerovnosti použijeme pravděpodobnostní uvažování . Nechť 0 < p < 1  je pravděpodobnostní parametr, který bude zvolen později. Sestrojte náhodný podgraf H grafu G umístěním každého vrcholu G do H nezávisle s pravděpodobností p a každá hrana G bude v H právě tehdy, když oba vrcholy hrany leží v H . Nechť eH , n H a cr H označují počet hran, vrcholů a průsečíků grafu H. Protože H je podgrafem G , jeho diagram je obsažen v diagramu G. Podle předběžné nerovnosti pro počet křižovatek máme

Výpočtem matematických očekávání dostaneme

Protože každý z n vrcholů v G má pravděpodobnost , že p spadne do H , dostaneme E [ nH ] = pn . Stejně tak každá hrana v G má pravděpodobnost p 2 zůstat v H , protože oba konce musí být v H . Tedy E [ eH ] = p2e . _ _ Konečně, každý průsečík v G má pravděpodobnost p 4 zůstat v H , protože každý průsečík zahrnuje čtyři vrcholy. Abyste tomu porozuměli, představte si diagram G s průsečíky cr( G ) . Můžeme předpokládat, že jakékoli dvě hrany v tomto diagramu se společným vrcholem se neprotínají, jinak vyměníme části hran, dokud se průnik a počet průsečíků nezmenší o jeden. Můžeme tedy uvažovat, že průnik zahrnuje čtyři různé vrcholy grafu G . V důsledku toho E [cr H ] = p 4 cr( G ) a dostáváme

Nyní, když položíme p = 4 n / e < 1 (protože jsme předpokládali, že e > 4 n ), po některých algebraických výpočtech dostaneme

Mírná změna ve výše uvedené argumentaci nám umožňuje nahradit 64 33,75 pro e > 7,5 n [31] .

Viz také

Poznámky

  1. ↑ Turán, 1977 , s. 7-9.
  2. ↑ Bronfenbrenner, 1944 , str. 283-289.
  3. ↑ Scheinerman, Wilf, 1994 , str. 939-943.
  4. ↑ Pach, Sharir, 2009 , str. 126-127.
  5. ↑ Zarankiewicz, 1954 , s. 137-145.
  6. ↑ Chlap, 1969 , str. 63-69.
  7. ↑ 1 2 Chlap, 1960 , str. 68-72.
  8. ↑ Saaty, 1964 , str. 688-690.
  9. ↑ Aichholzer .
  10. ↑ Kainen, 1968 , str. 374-377.
  11. ↑ Klerk, Maharry, Pasechnik, Richter, Salazar, 2006 , str. 189-202.
  12. ↑ Schaefer, 2014 , str. #DS21.
  13. ↑ Barát, Toth, 2009 .
  14. ↑ Garey a Johnson, 1983 , s. 312-316.
  15. ↑ Hliněny, 2006 , str. 455-471.
  16. ↑ Cabello, Mohar, 2013 , str. 1803-1829.
  17. ↑ Schaefer, 2010 , str. 334-344.
  18. ↑ Grohe, 2005 , str. 285-302.
  19. ↑ Kawarabayashi, Reed, 2007 , str. 382-390.
  20. ↑ Even, Guha, Schieber, 2003 , str. 231-252.
  21. ↑ Rectilinear Crossing Number Archivováno 25. června 2008 na Wayback Machine , Graz Institute for Software Engineering, University of Technology (2009).
  22. ↑ Weisstein, Eric W. "Smallest Cubic Crossing Number Graph." Z MathWorld – webový zdroj Wolfram. . Získáno 20. září 2020. Archivováno z originálu dne 19. března 2020.
  23. ↑ Exoo .
  24. ↑ Pegg, Exoo, 2009 .
  25. ↑ Ajtai, Chvátal, Novorozenec, Szemerédi, 1982 , str. 9-12.
  26. ↑ Leighton, 1983 .
  27. ↑ Ackerman, 2013 . Dřívější výsledky s jinými konstantami viz Pach a Toph Pach, Tóth, 1997 , str. 427-439, Pach, Radchik, Tardos a Tof Pach, Radoičić, Tardos, Tóth, 2006 , s. 527-552
  28. ↑ Szekely, 1997 , str. 353-358.
  29. ↑ Dey, 1998 , str. 373-382.
  30. ↑ Pach, Spencer, Tóth, 2000 , str. 623-644.
  31. ↑ Ackerman, 2013 .

Literatura