Ferdeszimmetrikus gráf

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\boldsymbol {\rightarrow }}$	távolságreguláris	${\boldsymbol {\leftarrow }}$	erősen reguláris
${\boldsymbol {\downarrow }}$
szimmetrikus	${\boldsymbol {\leftarrow }}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\boldsymbol {\downarrow }}$
(ha összefüggő) csúcs- és éltranzitív	${\boldsymbol {\rightarrow }}$	éltranzitív és reguláris	${\boldsymbol {\rightarrow }}$	éltranzitív
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
csúcstranzitív	${\boldsymbol {\rightarrow }}$	reguláris	${\boldsymbol {\rightarrow }}$	(ha páros) bireguláris
${\boldsymbol {\uparrow }}$
Cayley-gráf	${\boldsymbol {\leftarrow }}$	zérószimmetrikus		aszimmetrikus

A matematika, azon belül a gráfelmélet területén egy ferdeszimmetrikus gráf (skew-symmetric graph) olyan irányított gráf, ami izomorf saját transzponáltjával, tehát az élek megfordításával kapott gráffal, méghozzá olyan izomorfizmussal, ami fixpont nélküli involúció. A ferdeszimmetrikus gráfok megegyeznek a kettős irányítású gráfok dupla fedési gráfjaival. A ferdeszimmetrikus gráfokat először antiszimmetrikus digráfok néven vezette be (Tutte 1967), később poláris gráfok dupla fedési gráfjaiként (double covering graphs of polar graphs) (Zelinka 1976b), még később kettős irányítású gráfok dupla fedési gráfjaiként (double covering graphs of bidirected graphs) (Zaslavsky 1991). Felbukkannak még gráfok párosításait kereső algoritmusokban alternáló utak és alternáló körök keresésének modellezésekor, annak vizsgálatakor, hogy az életjáték egy „csendélete” felosztható-e kisebb komponensekre, a gráflerajzolásban és a 2-SAT problémák hatékony megoldásához használt következtetési gráfokban.

Definíció

(Goldberg & Karzanov 1996) definíciója alapján egy G ferdeszimmetrikus gráf olyan irányított gráf, mely a G csúcsait G más csúcsaiba átvivő σ leképezéssel együtt a következő feltételeket teljesíti:

1. bármely v csúcsra, σ(v) ≠ v,
2. bármely v csúcsra, σ(σ(v)) = v,
3. bármely (u,v) élre, (σ(v),σ(u)) szintén él.

A harmadik tulajdonság segítségével σ kiterjeszthető G élein egy orientációt megfordító leképezéssé. G transzponáltja az a gráf, melyet G minden élének megfordításával kapunk, σ pedig olyan izomorfizmust határoz meg, ami G-t transzponáltjába viszi át. Azonban a ferdeszimmetrikus gráfoktól azt is megköveteljük, hogy az izomorfizmus minden csúcsot egy tőle különböző csúcsba vigyen át, nem engedve meg, hogy a csúcs saját magába menjen át, sem azt, hogy kettőnél több csúcs alkosson egy izomorfizmus-ciklust. Egy ferdeszimmetrikus gráfban lévő utat vagy kört akkor nevezünk regulárisnak, ha az út vagy kör minden v csúcsára igaz, hogy a hozzá tartozó σ(v) csúcs nem része az adott útnak vagy körnek.

Példák

Minden páros számú csúccsal rendelkező irányított útgráf ferdeszimmetrikus, az út két végét felcserélő szimmetriával. A páratlan csúcsszámnál ez nem igaz, mert az irányt megfordító szimmetria az út középén lévő csúcsot helyben hagyja, ami nem megengedett. Hasonlóan, egy irányított körgráf akkor ferdeszimmetrikus, ha páros a csúcsszáma. Ebben az esetben a ferdeszimmetrikusságot létrehozó különböző σ leképezések száma a kör hosszának felével egyezik meg.

Felismerés

(Lalonde 1981) szerint annak meghatározása, hogy adott irányított gráf ferdeszimmetrikus-e, NP-teljes, mivel páros gráfban NP-nehéz egy színeket megfordító involúciót találni. Ilyen involúció pontosan akkor létezik, ha az egyik színosztályból a másik színosztályba mutató élek orientálásával kapott irányított gráf ferdeszimmetrikus, tehát ennek az irányított gráfnak a ferdeszimmetria-tesztelése nehéz feladat. Ez a bonyolultság nem érinti a ferdeszimmetrikus gráfokra vonatkozó útkeresési algoritmusokat, mivel ezek az algoritmusok bemenetként elvárják a ferdeszimmetrikus struktúrát, nem a gráf egyéb tulajdonságaiból következtetnek rá.

Fordítás

• Ez a szócikk részben vagy egészben a Skew-symmetric 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

• Aspvall, Bengt; Plass, Michael F. & Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8 (3): 121–123, DOI 10.1016/0020-0190(79)90002-4.
• Babenko, Maxim A. (2006), "Acyclic bidirected and skew-symmetric graphs: algorithms and structure", Computer Science – Theory and Applications, vol. 3967, Lecture Notes in Computer Science, Springer-Verlag, pp. 23–34, ISBN 978-3-540-34166-6, DOI 10.1007/11753728_6.
• Biggs, Norman (1974), Algebraic Graph Theory, London: Cambridge University Press.
• Cook, Matthew (2003), "Still life theory", New Constructions in Cellular Automata, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, pp. 93–118.
• Edmonds, Jack & Johnson, Ellis L. (1970), "Matching: a well-solved class of linear programs", Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, June 1969, New York: Gordon and Breach. Reprinted in Combinatorial Optimization — Eureka, You Shrink!, Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27–30, doi:10.1007/3-540-36478-1_3.
• Gabow, Harold N.; Kaplan, Haim & Tarjan, Robert E. (1999), "Unique maximum matching algorithms", Proc. 31st ACM Symp. Theory of Computing (STOC), pp. 70–78, ISBN 1-58113-067-8, DOI 10.1145/301250.301273.
• Goldberg, Andrew V. & Karzanov, Alexander V. (1996), "Path problems in skew-symmetric graphs", Combinatorica 16 (3): 353–382, DOI 10.1007/BF01261321.
• Goldberg, Andrew V. & Karzanov, Alexander V. (2004), "Maximum skew-symmetric flows and matchings", Mathematical programming 100 (3): 537–568, DOI 10.1007/s10107-004-0505-z.
• Hui, Peter; Schaefer, Marcus & Štefankovič, Daniel (2004), "Train tracks and confluent drawings", Proc. 12th Int. Symp. Graph Drawing, vol. 3383, Lecture Notes in Computer Science, Springer-Verlag, pp. 318–328.
• Lalonde, François (1981), "Le problème d'étoiles pour graphes est NP-complet", Discrete Mathematics 33 (3): 271–280, DOI 10.1016/0012-365X(81)90271-5.
• Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, ISBN 1-58113-184-4, DOI 10.1145/335305.335345.
• Tutte, W. T. (1967), "Antisymmetrical digraphs", Canadian Journal of Mathematics 19: 1101–1117, DOI 10.4153/CJM-1967-101-8.
• Zaslavsky, Thomas (1982), "Signed graphs", Discrete Applied Mathematics 4: 47–74, DOI 10.1016/0166-218X(82)90033-6.
• Zaslavsky, Thomas (1991), "Orientation of signed graphs", European Journal of Combinatorics 12: 361–375, DOI 10.1016/s0195-6698(13)80118-7.
• Zelinka, Bohdan (1974), "Polar graphs and railway traffic", Aplikace Matematiky 19: 169–176.
• Zelinka, Bohdan (1976a), "Isomorphisms of polar and polarized graphs", Czechoslovak Mathematical Journal 26: 339–351.
• Zelinka, Bohdan (1976b), "Analoga of Menger's theorem for polar and polarized graphs", Czechoslovak Mathematical Journal 26: 352–360.