Jednotkový kruhový graf

V teorii grafů je jednotkový kruhový graf průsečíkový graf rodiny jednotkových kruhů na euklidovské rovině . To znamená, že pro každou kružnici vytvoříme vrchol a spojíme dva vrcholy hranou, pokud se odpovídající kružnice protínají.

Charakteristika

Existuje několik možností pro definování grafu jednotkových kružnic, které jsou ekvivalentní až do výběru koeficientu:

• Graf průsečíků kružnic nebo kružnic o stejném poloměru.
• Graf vytvořený ze sady kružnic o stejném poloměru, ve kterém jsou dvě kružnice spojeny hranou, pokud je střed jedné kružnice uvnitř druhé.
• Graf vytvořený ze sady bodů v euklidovské rovině, ve které jsou dva body spojeny hranou, pokud je vzdálenost mezi těmito body menší než nějaký práh.

Vlastnosti

Jakýkoli vygenerovaný podgraf jednotkového kruhového grafu je také jednotkový kruhový graf. Příkladem grafu, který není jednotkovým kruhovým grafem, je hvězda K 1,7 se středovým vrcholem spojeným se sedmi listy - pokud se každý ze sedmi kruhů dotýká centrálního kruhu, musí se jakákoli dvojice kruhů dotýkat navzájem ( protože kontaktní číslo v letadle je 6). Jednotkový kruhový graf tedy nemůže obsahovat K 1,7 jako generovaný podgraf.

Aplikace

Od práce Husona a Sena ( Huson, Sen 1995 ) se grafy jednotkových kruhů používají v informatice k modelování topologie bezdrátových decentralizovaných samoorganizujících se sítí . V této aplikaci jsou uzly propojeny přímou bezdrátovou komunikací bez základnové stanice . Předpokládá se, že všechny vrcholy jsou homogenní a vybavené všesměrovými anténami . Umístění antén je modelováno jako body na euklidovské rovině a oblast, kde může být signál přijímán jiným vrcholem, je modelována jako kruh. Pokud mají všechny vrcholy vysílače stejné síly, budou mít tyto kruhy stejný poloměr. Náhodné geometrické grafy vytvořené jako jednotkové kruhové grafy s náhodnými středy lze použít k modelování filtrování a některých dalších jevů. [jeden]

Výpočetní složitost

Problém, zda lze abstraktně daný graf reprezentovat jako jednotkový kruhový graf, je NP-těžký (přesněji úplný pro existenciální teorii reálných čísel ) [2] [3] . Navíc je v polynomiálním čase prokázáno, že není možné najít určité souřadnice jednotkových kružnic: existují grafy jednotkových kružnic, které vyžadují exponenciální počet bitů přesnosti v jakékoli takové reprezentaci [4] .

Nicméně mnoho důležitých a složitých optimalizačních problémů na grafech, jako je problém nezávislých množin , zbarvení grafu a problém minimální dominující množiny , lze efektivně aproximovat pomocí geometrické struktury těchto grafů [5] [6] a problému kliky neboť tyto grafy lze řešit přesně v polynomiálním čase, pokud je dáno zobrazení kruhu [7] . Přesněji řečeno, pro daný graf lze v polynomiálním čase buď najít maximální kliku, nebo dokázat, že graf není jednotkový kruhový graf [8] .

Pokud daná množina vrcholů tvoří podmnožinu trojúhelníkové mřížky , je nutná a postačující podmínka pro dokonalost grafu známa [9] . Pro dokonalé grafy lze mnoho NP-úplných optimalizačních problémů ( problém zbarvení grafu , problém maximální kliky a problém nezávislé množiny ) vyřešit v polynomiálním čase.

Viz také

• Kolekce Vietoris-Rips , zobecnění jednotkového kruhového grafu, tvoří konstrukci v topologickém prostoru vyššího řádu z jednotkových vzdáleností v metrickém prostoru.
• Graf jednotkové vzdálenosti , vytvořený spojením bodů, které jsou od sebe přesně jeden, ne méně než jeden (jako v grafech jednotkových kruhů).

Poznámky

1. ↑ Viz např. práce Dahla a Christensena ( Dal, Christensen 2002 ).
2. ↑ Breu, Kirkpatrick, 1998 .
3. ↑ Kang, Müller, 2011 .
4. ↑ McDiarmid, Mueller, 2011 .
5. ↑ Marathe et al, 1994 .
6. ↑ Matsui, 2000 .
7. ↑ Clark, Colbourn, Johnson, 1990 .
8. ↑ Raghavan, Spinrad, 2003 .
9. ↑ Miyamoto, Matsui, 2005 .

Odkazy

• Heinz Breu, David G. Kirkpatrick. Rozpoznávání grafů jednotek je NP-hard // Computational Geometry Theory and Applications. - 1998. - T. 9 , no. 1–2 . — s. 3–24 .
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Jednotkové diskové grafy // Diskrétní matematika . - 1990. - T. 86 , čís. 1–3 . — S. 165–177 . - doi : 10.1016/0012-365X(90)90358-O .
• Jesper Dall, Michael Christensen. Náhodné geometrické grafy // Phys. Rev. E. - 2002. - T. 66 . - S. 016121 . - doi : 10.1103/PhysRevE.66.016121 . - arXiv : cond-mat/0203026 .
• Mark L. Huson, Arunabha Sen. Konference vojenských komunikací, IEEE MILCOM '95. - 1995. - T. 2 . — S. 647–651 . — ISBN 0-7803-2489-7 . - doi : 10.1109/MILCOM.1995.483546 .
• Ross J. Kang, Tobias Müller. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), 13.–15. června 2011, Paříž, Francie. - 2011. - S. 308-314 .
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi, Daniel J. Rosenkrantz. Heuristika založená na geometrii pro grafy jednotkových disků . - 1994. - arXiv : math.CO/9409226 .
• Tomomi Matsui. Aproximační algoritmy pro problémy s maximální nezávislou množinou a problémy se zlomkovým zbarvením na jednotkových diskových grafech // Poznámky k přednáškám z informatiky. - 2000. - T. 1763 . — S. 194–200 . — ISBN 978-3-540-67181-7 . - doi : 10.1007/978-3-540-46515-7_16 .
• Colin McDiarmid, Tobias, Mueller. Celočíselné realizace diskových a segmentových grafů. - 2011. - arXiv : 1111.2931 .
• Yuichiro Miyamoto, Tomomi Matsui. Dokonalost a nedokonalost k-té síly mřížkových grafů // Poznámky z přednášek z informatiky. - 2005. - T. 3521 . — S. 233–242 . - ISBN 978-3-540-26224-4 . - doi : 10.1007/11496199_26 .
• Vijay Raghavan, Jeremy Spinrad. Robustní algoritmy pro omezené domény // Journal of Algorithms. - 2003. - T. 48 , no. 1 . — S. 160–172 . - doi : 10.1016/S0196-6774(03)00048-8 .