„Éltranzitív gráf” változatai közötti eltérés

Ugrás a navigációhoz Ugrás a kereséshez
a (def.)
[[Image:Gray graph 2COL.svg|thumb|200px|A [[Gray-gráf]] éltranzitív és [[reguláris gráf|reguláris]], de nem [[csúcstranzitív gráf|csúcstranzitív]].]]
 
Az éltranzitív gráfok közé tartozik az összes <math>K_{m,n}</math> [[teljes páros gráf]], az összes [[szimmetrikus gráf]], pl. a [[kocka]] csúcsai és élei is alkotnak.<ref name="biggs" /> A szimmetrikus gráfok [[csúcstranzitív gráf|csúcstranzitívek]] is (már ha összefüggőek), de általában véve az éltranzitív gráfok nem szükségképpen csúcstranzitívak. A [[Gray-gráf]] példa olyan gráfra, ami éltranzitív, de nem csúcstranzitív. Az összes ilyen gráf [[páros gráf|páros]],<ref name="biggs" /> ezért [[gráfok színezése|két színnel színezhető]]..
 
Az olyan éltranzitív gráfokat, amik [[reguláris gráf|regulárisak]] de nem csúcstranzitívak, [[félszimmetrikus gráf]]oknak nevezik. A [[Gray-gráf]] erre is példát szolgáltat.
89 988

szerkesztés

Navigációs menü