Egységkör grafikonja

A gráfelméletben az egységkör gráf az egységkörök családjának metszésponti gráfja az euklideszi síkon . Azaz minden körnek alkotunk egy csúcsot, és két csúcsot összekötünk éllel, ha a megfelelő körök metszik egymást.

Jellemzők

Számos lehetőség van az egységkörök grafikonjának meghatározására, amelyek egyenértékűek az együttható kiválasztásával:

• Körök vagy azonos sugarú körök metszéspontjainak grafikonja.
• Azonos sugarú körök halmazából képzett gráf, amelyben két kört él összeköt, ha az egyik kör középpontja a másikon belül van.
• Az euklideszi síkban lévő pontok halmazából képzett gráf, amelyben két pontot él összeköt, ha a pontok közötti távolság kisebb, mint valamilyen küszöb.

Tulajdonságok

Az egységkörgráf bármely generált részgráfja egyben egységkörgráf is. Példa egy olyan gráfra, amely nem egységkör gráf, a K 1,7 csillag , amelynek központi csúcsa hét levélhez kapcsolódik - ha a hét kör mindegyike érinti a központi kört, akkor bármely körpárnak érintenie kell egymást (mivel a kapcsolati szám a gépben 6 ). Így az egységkörgráf nem tartalmazhat K 1,7 -et generált részgráfként.

Alkalmazások

Huson és Sen munkássága óta ( Huson, Sen 1995 ) a számítástechnikában egységkörgráfokat használnak a vezeték nélküli decentralizált önszerveződő hálózatok topológiájának modellezésére . Ebben az alkalmazásban a csomópontok közvetlen vezeték nélküli kommunikációval vannak összekötve bázisállomás nélkül . Feltételezzük, hogy minden csúcs homogén, és mindenirányú antennákkal van felszerelve . Az antennák elhelyezkedését az euklideszi síkon lévő pontokként modellezzük, és körként azt a területet, ahol a jelet egy másik csúcs fogadhatja. Ha minden csúcsnak azonos teljesítményű adója van, akkor ezeknek a köröknek ugyanaz lesz a sugara. A véletlenszerű középpontú egységkör gráfokként kialakított véletlen geometriai gráfok felhasználhatók szűrés és más jelenségek modellezésére. [egy]

Számítási összetettség

NP-nehéz (pontosabban a valós számok egzisztenciális elméletére teljes ) [2] [3] probléma . Emellett bizonyítottan lehetetlen polinom időben megtalálni az egységkörök bizonyos koordinátáit: vannak olyan egységkörgráfok, amelyek exponenciális számú bit pontosságot igényelnek minden ilyen ábrázolásnál [4] .

Azonban a gráfokon sok fontos és összetett optimalizálási probléma, mint például a független halmazprobléma , a gráf színezése és a minimálisan domináns halmazprobléma hatékonyan közelíthető e gráfok geometriai szerkezetével [5] [6] és a klikkproblémával . mert ezek a gráfok pontosan polinomiális időben megoldhatók, ha adott a körábrázolás [7] . Pontosabban, egy adott gráfra, polinomiális időben, meg lehet találni a maximális klikket, vagy bebizonyítani, hogy a gráf nem egységkörgráf [8] .

Ha az adott csúcshalmaz a háromszögrács részhalmazát alkotja , akkor ismert a gráf tökéletességének szükséges és elégséges feltétele [9] . Tökéletes gráfokhoz sok NP-teljes optimalizálási probléma (a gráf színezési problémája , a maximális klikkelési probléma és a független halmazprobléma ) megoldható polinomiális időben.

Lásd még

• A Vietoris-Rips gyűjtemény , az egységkör gráf általánosítása, egy magasabb rendű topológiai térben alkot konstrukciót a metrikus térben lévő egységnyi távolságokból.
• Egységtávolság-gráf , olyan pontok összekapcsolásával jön létre, amelyek egymástól pontosan egy, de legalább egy távolságra vannak (mint az egységkör grafikonokon).

Jegyzetek

1. ↑ Lásd például Dahl és Christensen munkásságát ( Dall, 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 .

Linkek

• Heinz Breu, David G. Kirkpatrick. Az egységlemezes gráffelismerés NP-kemény // Computational Geometry Theory and Applications. - 1998. - T. 9 , sz. 1–2 . — 3–24 .
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Egységlemezes grafikonok // Diszkrét matematika . - 1990. - T. 86 , sz. 1–3 . – S. 165–177 . - doi : 10.1016/0012-365X(90)90358-O .
• Jesper Dall, Michael Christensen. Véletlenszerű geometriai grafikonok // Phys. Fordulat. E. - 2002. - T. 66 . - S. 016121 . - doi : 10.1103/PhysRevE.66.016121 . - arXiv : cond-mat/0203026 .
• Mark L. Huson, Arunabha Sen. Katonai Kommunikációs Konferencia, 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-7th Annual Symposium on Computational Geometry (SCG'11), 2011. június 13–15, Párizs, Franciaország. - 2011. - S. 308-314 .
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi, Daniel J. Rosenkrantz. Geometria alapú heurisztika egységlemezes gráfokhoz . - 1994. - arXiv : math.CO/9409226 .
• Tomomi Matsui. Közelítő algoritmusok maximális független halmazproblémákhoz és törtszínezési problémákhoz egységlemezes grafikonokon // Előadásjegyzetek a számítástechnikából. - 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. Lemez- és szegmensgráfok egészszámú megvalósításai. - 2011. - arXiv : 1111.2931 .
• Yuichiro Miyamoto, Tomomi Matsui. A rácsos gráfok kth hatványának tökéletessége és tökéletlensége // Számítástechnikai előadásjegyzetek. - 2005. - T. 3521 . – S. 233–242 . - ISBN 978-3-540-26224-4 . - doi : 10.1007/11496199_26 .
• Vijay Raghavan, Jeremy Spinrad. Robusztus algoritmusok korlátozott tartományokhoz // Journal of Algorithms. - 2003. - T. 48 , sz. 1 . – S. 160–172 . - doi : 10.1016/S0196-6774(03)00048-8 .