Aszimmetrikus gráf

csak triviális szimmetriákkal rendelkező 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.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus
A nyolc 6-csúcsú aszimmetrikus gráf
A legkisebb aszimmetrikus 3-reguláris gráf, a Frucht-gráf.

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ákSzerkeszté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ágokSzerkeszté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áfokSzerkeszté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ákSzerkeszté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ásSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. 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> Archiválva 2017. július 6-i dátummal a Wayback Machine-ben.
  2. Baron, G. & Imrich, W. (1969), "Asymmetrische reguläre Graphen", Acta Mathematica Academiae Scientiarum Hungaricae 20: 135–142, DOI 10.1007/BF01894574.
  3. 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.
  4. 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>.
  5. Quintas, Louis V. (1967), "Extrema concerning asymmetric graphs", Journal of Combinatorial Theory 3 (1): 57–82, DOI 10.1016/S0021-9800(67)80018-8.
A Wikimédia Commons tartalmaz Aszimmetrikus gráf témájú médiaállományokat.