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 , később poláris gráfok dupla fedési gráfjaiként (double covering graphs of polar graphs) , 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) . 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ó 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: bármely v csúcsra, σ(v) ≠ v, bármely v csúcsra, σ(σ(v)) = v, 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 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
Jegyzetek . . . . . Reprinted in Combinatorial Optimization — Eureka, You Shrink!, Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27–30, . . . . . . . . . . . . .
Kategória:Gráfcsaládok Kategória:Irányított gráfok Kategória:Párosítás