Paritásgráf
A matematika, azon belül a gráfelmélet területén egy paritásgráf vagy párossággráf (parity graph) olyan gráf, melyben bármely két kiválasztott csúcs közti összes feszített út párossága megegyezik: az utak vagy mind páros, vagy mind páratlan hosszúságúak.[1] A gráfok ezen csoportját elsőként (Burlet & Uhry 1984) tanulmányozták, akiktől nevüket is kapták.[2]
Kapcsolódó gráfcsaládok
[szerkesztés]A paritásgráfok közé tartoznak a távolság-örökletes gráfok, melyekben bármely két csúcs között húzódó összes feszített út azonos hosszúságú. Közéjük tartoznak a páros gráfok, melyek úgy is jellemezhetők, mint a gráfok, melyekben bármely két csúcs közti összes út (nem feltétlenül feszített út) azonos parítású, és az élperfekt gráfok, melyek a páros gráfok általánosításai. Minden paritásgráf Meyniel-gráf, vagyis olyan gráf, melyben mindig legalább 5 hosszúságú páratlan kör rendelkezik két húrral. Mivel egy paritásgráf bármely páratlan köre két különböző paritású útra particionálható, melyek egyike sem áll egyetlen élből, legalább egy húr szükséges ahhoz, hogy ezek egyike se legyen feszített út. Ezután a kört az első húr végpontjai közti két útra particionálva egy második húrra van szükség, hogy a második partíció két útja se legyen feszített. Mivel a Meyniel-gráfok perfektek, ezért a paritásgráfok is azok.[1] Pontosan azok a gráfok továbbá, melyen egyetlen éllel való Descartes-szorzás után perfektek maradnak.[3]
Algoritmusok
[szerkesztés]Egy gráf pontosan akkor paritásgráf, ha ún. splitfelbontásának (az olyan vágások összességének, melyek csúcshalmazai teljes páros gráfot adnak) minden eleme vagy teljes, vagy páros gráf. Ennek a jellemzésnek a segítésével adott gráfról lineáris időben eldönthető, hogy paritásgráf-e. Ugyanez a jellemzés lehetővé teszi néhány, páros gráfokra íródott optimalizációs algoritmus paritásgráfokra való kiterjesztését. Például a splitfelbontást felhasználva polinom időben lehetséges egy paritásgráf súlyozott maximális elemszámú független csúcshalmazának megkeresése.[4]
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Parity graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ a b Parity graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
- ↑ Burlet, M. & Uhry, J.-P. (1984), "Parity graphs", Topics on perfect graphs, vol. 88, North-Holland Math. Stud., North-Holland, Amsterdam, pp. 253–277, DOI 10.1016/S0304-0208(08)72939-6.
- ↑ Jansen, Klaus (1998), "A new characterization for parity graphs and a coloring problem with costs", LATIN'98: theoretical informatics (Campinas, 1998), vol. 1380, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 249–260, DOI 10.1007/BFb0054326.
- ↑ Cicerone, Serafino & Di Stefano, Gabriele (1997), "On the equivalence in complexity among basic problems on bipartite and parity graphs", Algorithms and computation (Singapore, 1997), vol. 1350, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 354–363, DOI 10.1007/3-540-63890-3_38.
