A matematika, azon belül a gráfelmélet területén egy aszimmetrikus gráf olyan irányítatlan gráf, ami csak triviális szimmetriákkal rendelkezik.
Formálisan, egy gráf automorfizmusa a csúcsainak olyan p permutációja, melyben bármely két u és v csúcs pontosan akkor szomszédos egymással, ha p(u) és p(v) is szomszédosak. Egy gráf önmagába történő identikus megfeleltetése mindig automorfizmus, ezt a gráf triviális automorfizmusának nevezik. Egy aszimmetrikus gráf olyan gráf, mely csak ilyen automorfizmusokkal bír.
Példák A legkisebb nem triviális aszimmetrikus gráf 6 csúcsból áll. A legkisebb aszimmetrikus reguláris gráfok 10 csúcsúak; vannak közöttük 4- és 5 regulárisak is... A két legkisebb aszimmetrikus 3-reguláris gráf egyike az 1939-ben megtalált 12 csúcsú Frucht-gráf.. A Frucht-tétel megerősített változata szerint végtelen sok aszimmetrikus 3-reguláris gráf létezik.
Tulajdonságok Az aszimmetrikus gráfok családja a komplementerképzés műveletére zárt: G gráf pontosan akkor aszimmetrikus, ha komplementere is aszimmetrikus. Bármely n-csúcsú aszimmetrikus gráf szimmetrikussá tehető legfeljebb n/2 + o(n) él hozzáadásával/eltávolításával.
Véletlen gráfok Az n csúcsú, nem triviális automorfizmusokkal rendelkező gráfok száma n növekedésével tart nullához, ami informálisan úgy is megfogalmazható, hogy „csaknem minden véges gráf aszimmetrikus”. Ezzel ellentétben, szintén informálisan, „csak nem minden végtelen gráf szimmetrikus”. Specifikusabban, az Erdős–Rényi modell szerinti megszámlálhatóan végtelen véletlen gráfok 1 valószínűséggel izomorfak az erősen szimmetrikus Rado-gráffal..
Fák A legkisebb aszimmetrikus fa hét csúcsból áll: három, közös kezdőpontból induló út található benne, 1, 2 és 3 hosszúságban.. Az általános gráfoktól eltérően csaknem minden fa szimmetrikus. Ha az n címkézett csúccsal rendelkező fák közül véletlenszerűen választunk egyet, akkor n növekedésével 1-hez tart annak valószínűsége, hogy a fa tartalmazni fog ugyanahhoz a csúcshoz tartozó két levelet, és lesz olyan szimmetria, ami a két levelet megcseréli.
Fordítás
Jegyzetek
Kategória:Gráfcsaládok