Křížení čísla (teorie grafů) - Crossing number (graph theory)

Kresba Heawoodův graf se třemi přechody. Toto je minimální počet křížení mezi všemi výkresy tohoto grafu, takže graf má číslo křížení cr (G) = 3.

v teorie grafů, číslo křížení cr (G) grafu G je nejnižší počet křížení hran roviny výkres grafu G. Například graf je rovinný právě když je jeho číslo křížení nula. Určení čísla křížení má v roce stále velký význam kreslení grafu, jak ukázaly uživatelské studie, že kreslení grafů s několika kříženími lidem usnadňuje pochopení výkresu.^[1]

Studie čísel křížení vznikla v roce 2006 Problém továrny na cihly v Turánu, ve kterém Pál Turán požádal o tovární plán, který minimalizoval počet přejezdů mezi tratěmi spojujícími cihlové pece s úložišti. Matematicky lze tento problém formalizovat jako požadavek na křížení čísla a kompletní bipartitní graf,^[2] Stejný problém vznikl nezávisle v sociologie přibližně ve stejnou dobu v souvislosti s výstavbou sociogramy.^[3] Turánův domnělý vzorec pro křížení čísel úplných bipartitních grafů zůstává neprokázaný, stejně jako analogický vzorec pro kompletní grafy.

The nerovnost čísla křížení uvádí, že pro grafy, kde je číslo E hran je dostatečně větší než počet n z vrcholů je číslo křížení alespoň úměrné E³/n². Má aplikace v VLSI design a geometrie dopadu.

Bez další kvalifikace počet křížení umožňuje kresby, na nichž mohou být hrany znázorněny libovolnými křivkami. Variace tohoto konceptu, přímé číslo křížení, vyžaduje, aby všechny hrany byly přímými segmenty, a mohou se lišit od čísla křížení. Zejména číslo přímého křížení a kompletní graf je v podstatě stejný jako minimální počet konvexních čtyřúhelníků určený množinou n body v obecné poloze. Problém stanovení tohoto počtu úzce souvisí s šťastný konec problém.^[4]

Definice

Pro účely definování čísla křížení je nakreslen výkres neorientovaný graf je mapování od vrcholů grafu k disjunktním bodům v rovině a od okrajů grafu ke křivkám spojujícím jejich dva koncové body. Žádný vrchol by neměl být mapován na hranu, jejíž není koncovým bodem, a kdykoli mají dvě hrany křivky, které se protínají (jiné než ve sdíleném koncovém bodě), jejich průsečíky by měly tvořit konečnou množinu správných křížení, kde jsou tyto dvě křivky příčný. Křížení se počítá zvlášť pro každý z těchto křížení, pro každou dvojici hran, které se protínají. Číslo křížení grafu je potom minimální počet křížení ve výkresu u všech těchto výkresů.^[5]

Někteří autoři přidávají do definice výkresu další omezení, například že každá dvojice hran má nanejvýš jeden průsečík (sdílený koncový bod nebo křížení). U čísla křížení, jak je definováno výše, tato omezení nemají žádný rozdíl, protože kresba s minimem křížení nemůže mít hrany s více průsečíky. Pokud se dvě hrany se sdíleným koncovým bodem kříží, lze výkres lokálně změnit v místě křížení, přičemž zbytek výkresu se nezmění, aby se vytvořil jiný výkres s menším počtem křížení. A podobně, pokud se dva okraje protínají dvakrát nebo vícekrát, lze výkres lokálně změnit na dvou bodech křížení, aby se vytvořil jiný výkres s dvěma méně kříženími. Tato omezení jsou však relevantní pro alternativní definice čísla křížení, které například počítají pouze počet párů hran, které se kříží, spíše než počet křížení.^[5]

Speciální případy

V dubnu 2015 jsou čísla křížení známa pro velmi málo rodin grafů. Zejména, až na několik počátečních případů, počet křížení úplných grafů, bipartitních úplných grafů a produktů cyklů zůstávají neznámé, i když u dolních mezí došlo k určitému pokroku.^[6]

Kompletní bipartitní grafy

Optimální kresba K._4,7 což ukazuje, že problém Turánovy cihelny se 4 skladovacími místy (žluté skvrny) a 7 pecemi (modré skvrny) vyžaduje 18 přechodů (červené tečky)

V době druhá světová válka, Maďarský matematik Pál Turán byl nucen pracovat v cihelně a tlačil vagónový náklad cihel z pecí na skladiště. Továrna měla stopy z každé pece do každého skladiště a vozy se těžší tlačily v místech, kde se koleje protínaly, z čehož byl Turán veden k tomu, aby se zeptal na svůj problém s cihelnou: jak mohou pece, sklady a koleje být uspořádán tak, aby se minimalizoval celkový počet přejezdů? Matematicky lze pece a sklady formalizovat jako vrcholy a kompletní bipartitní graf, se stopami jako jeho hranami. Tovární rozvržení lze reprezentovat jako nákres tohoto grafu, takže se stává problém: jaký je minimální možný počet křížení ve výkresu kompletní bipartitní graf ?^[7]

Kazimierz Zarankiewicz pokusil se vyřešit problém Turánovy cihelny;^[8] jeho důkaz obsahoval chybu, ale prokázal platnost horní hranice z

${displaystyle {extrm {cr}} (K_ {m, n}) leq leftlfloor {frac {n} {2}} ightfloor leftlfloor {frac {n-1} {2}} ightfloor leftlfloor {frac {m} {2} } ightfloor leftlfloor {frac {m-1} {2}} ightfloor}$

pro číslo křížení celého bipartitního grafu K._{m, n}. Tato vazba byla považována za optimální počet křížení pro všechny kompletní bipartitní grafy.^[9]

Kompletní grafy a zbarvení grafů

Problém stanovení čísla křížení kompletní graf byl poprvé představen Anthony Hill, a objevil se v tisku v roce 1960.^[10] Hill a jeho spolupracovník John Ernest byli dva stavební umělci fascinován matematikou. Nejenže formulovali tento problém, ale také vytvořili domněnkový vzorec pro toto křížové číslo, které Richard K. Guy publikováno v roce 1960.^[10] Jmenovitě je známo, že vždy existuje kresba s

${displaystyle {extrm {cr}} (K_ {p}) leq {frac {1} {4}} leftlfloor {frac {p} {2}} ightfloor leftlfloor {frac {p-1} {2}} ightfloor leftlfloor { frac {p-2} {2}} ightfloor leftlfloor {frac {p-3} {2}} ightfloor}$

přechody. Tento vzorec udává hodnoty 1, 3, 9, 18, 36, 60, 100, 150 pro str = 5, ..., 12; viz sekvence A000241 v On-line encyklopedie celočíselných sekvencí Domníváme se, že nemůže existovat lepší kresba, takže tento vzorec poskytuje optimální počet křížení pro celé grafy. Nezávislou formulaci stejného dohadu vytvořil autor Thomas L. Saaty v roce 1964.^[11]

Saaty dále ověřil, že tento vzorec poskytuje optimální počet přechodů pro str ≤ 10 a Pan a Richter ukázali, že je to také optimální pro str = 11, 12.^[12]

The Albertsonova domněnka, formuloval Michael O. Albertson v roce 2007, uvádí, že mezi všemi grafy s chromatické číslo n, celý graf K._n má minimální počet přejezdů. To znamená, že pokud je domnělý vzorec pro křížové číslo celého grafu správný, pak každý n-chromatický graf má číslo křížení alespoň rovné stejnému vzorci. Nyní je známo, že Albertsonova domněnka platí n ≤ 16.^[13]

Krychlové grafy

Nejmenší kubické grafy s křížením čísla 1–8 a 11 jsou známa (sekvence A110507 v OEIS ). Nejmenší 1-kubický kubický graf je kompletní bipartitní graf K._3,3, se 6 vrcholy. Nejmenší 2křížkový kubický graf je Petersenův graf, s 10 vrcholy. Nejmenší 3křížkový kubický graf je Heawoodův graf, se 14 vrcholy. Nejmenší čtyřkřížkový kubický graf je Möbius-Kantorův graf, s 16 vrcholy. Nejmenší 5křížkový kubický graf je Pappusův graf, s 18 vrcholy. Nejmenší šestistupňový kubický graf je Desargues graf, s 20 vrcholy. Žádný ze čtyř křížících se 7 křížových grafů s 22 vrcholy není dobře znám.^[14] Mezi nejmenší 8 křížové kubické grafy patří Nauru graf a McGeeův graf nebo (3,7) -klecový graf, s 24 vrcholy.^[15] Mezi nejmenší 11 křížení kubických grafů patří Coxeterův graf s 28 vrcholy.^[16]

V roce 2009 Pegg a Exoo předpokládali, že nejmenší kubický graf s křížením číslo 13 je Tutte – Coxeterův graf a nejmenší kubický graf s křížením číslo 170 je Tutte 12-klec.^[15][17]

Složitost a aproximace

Obecně je stanovení čísla křížení grafu těžké; Garey a Johnson v roce 1983 ukázal, že se jedná o NP-tvrdé problém.^[18] Ve skutečnosti problém zůstává NP-těžký, i když je omezen na kubické grafy^[19] a na téměř rovinné grafy (grafy, které se po odstranění jedné hrany stanou rovinnými).^[20] Úzce související problém, stanovení přímého čísla křížení, je kompletní pro existenciální teorie skutečností.^[21]

Na pozitivní straně existují účinné algoritmy pro určení, zda je číslo křížení menší než pevná konstanta k. Jinými slovy, problém je fixovatelný parametr.^[22][23] Pro větší je to stále obtížné k, jako k = |PROTI|/2. Existují také efektivní aproximační algoritmy pro přiblížení cr (G) na grafech omezeného stupně.^[24] V praxi heuristický používají se algoritmy, jako je jednoduchý algoritmus, který začíná bez hran a neustále přidává každou novou hranu způsobem, který produkuje co nejméně dalších možných křížení. Tyto algoritmy se používají v Rectilinear Crossing Number distribuované výpočty projekt.^[25]

Nerovnost čísla přechodu

Pro neorientovaného jednoduchý graf G s n vrcholy a E hrany takové E > 7n číslo křížení je vždy alespoň

${displaystyle operatorname {cr} (G) geq {frac {e ^ {3}} {29n ^ {2}}}.}$

Tento vztah mezi hranami, vrcholy a číslem křížení byl objeven nezávisle na sobě Ajtai, Chvátal, Novorozenec a Szemerédi,^[26] a tím Leightone.^[27] To je známé jako nerovnost čísla křížení nebo překračování lemmatu.

Konstanta 29 je dosud nejznámější a je způsoben Ackermanem.^[28] Konstanta 7 lze snížit na 4, ale na úkor výměny 29 s horší konstantou 64.^[26][27]

Motivací Leightona při studiu čísel křížení bylo, aby aplikace přišla VLSI design v teoretické informatice.^[27] Později si Székely také uvědomil, že tato nerovnost přinesla velmi jednoduché důkazy o některých důležitých větách v geometrie dopadu, jako Beckova věta a Szemerédi-Trotterova věta,^[29] a Tamal Dey použil to k prokázání horních hranic geometrický k-sady.^[30]

Variace

Pokud je potřeba nakreslit hrany jako úsečkové segmenty, nikoli jako libovolné křivky, pak některé grafy vyžadují více křížení. The přímé číslo křížení je definován jako minimální počet křížení výkresu tohoto typu. Je vždy alespoň stejně velký jako číslo křížení a u některých grafů je větší. Čísla přímého křížení pro K.₅ přes K.₁₂ jsou 1, 3, 9, 19, 36, 62, 102, 153, (A014540 ) a hodnoty až K.₂₇ jsou známy, s K.₂₈ vyžadující přechod 7233 nebo 7234. Další hodnoty shromažďuje projekt Rectilinear Crossing Number.^[25]

Graf má místní číslo přechodu k pokud to lze nakreslit maximálně k přechody na hranu, ale ne méně. Grafy, které lze nakreslit maximálně k přechody na hranu se také nazývají k-planární.^[31]

Mezi další varianty čísla křížení patří párové křížení číslo (minimální počet párů hran, které se protínají v jakémkoli výkresu) a liché křížení číslo (počet párů hran, které v libovolném výkresu protínají lichý počet opakování). Liché číslo křížení se nanejvýš rovná počtu párových křížení, které se maximálně rovná číslu křížení. Avšak tím, že Věta Hanani – Tutte, kdykoli je jedno z těchto čísel nula, všechna jsou.^[5] Schaefer (2014, 2018 ) zkoumá mnoho takových variant.^[32][33]

Viz také

• Planarizace, rovinný graf vytvořený nahrazením každého křížení novým vrcholem
• Problém se třemi nástroji, hádanka, která se ptá, zda K._3,3 lze nakreslit 0 křížení

Reference