Aszimmetrikus gráf
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 szerkesztés
A legkisebb nem triviális aszimmetrikus gráf 6 csúcsból áll.[1] A legkisebb aszimmetrikus reguláris gráfok 10 csúcsúak; vannak közöttük 4- és 5 regulárisak is.[2][3] A két legkisebb aszimmetrikus 3-reguláris gráf egyike az 1939-ben megtalált 12 csúcsú Frucht-gráf.[4] A Frucht-tétel megerősített változata szerint végtelen sok aszimmetrikus 3-reguláris gráf létezik.
Tulajdonságok szerkesztés
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.[1] 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.[1]
Véletlen gráfok szerkesztés
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.[1]
Fák szerkesztés
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.[5] 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.[1]
Fordítás szerkesztés
- Ez a szócikk részben vagy egészben az Asymmetric 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 c d e Erdős, P. & Rényi, A. (1963), "Asymmetric graphs", Acta Mathematica Hungarica 14 (3): 295–315, doi:10.1007/BF01895716, <http://www.math-inst.hu/~p_erdos/1963-04.pdf>. Hozzáférés ideje: 2017-03-18.
- ↑ Baron, G. & Imrich, W. (1969), "Asymmetrische reguläre Graphen", Acta Mathematica Academiae Scientiarum Hungaricae 20: 135–142, DOI 10.1007/BF01894574.
- ↑ Gewirtz, Allan; Hill, Anthony & Quintas, Louis V. (1969), "The minimal number of points for regular asymmetric graphs", Universidad Técnica Federico Santa Maria. Scientia 138: 103–111.
- ↑ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica 6: 239–250, ISSN 0010-437X, <http://www.numdam.org/item?id=CM_1939__6__239_0>.
- ↑ Quintas, Louis V. (1967), "Extrema concerning asymmetric graphs", Journal of Combinatorial Theory 3 (1): 57–82, DOI 10.1016/S0021-9800(67)80018-8.
