Ferdeszimmetrikus gráf

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.

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

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

• .
• .
• .
• .
• . 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.
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

• Matematikaportál • összefoglaló, színes tartalomajánló lap