Reguláris gráf
matematikai fogalom / From Wikipedia, the free encyclopedia
Egy gráf reguláris, ha minden csúcsának ugyanannyi szomszédja van, más szóval minden csúcs fokszáma azonos. A közös fokszámot k-val jelölve beszélhetünk k-reguláris gráfról is. A reguláris irányított gráfnak meg kell felelnie annak az erősebb feltételnek is, hogy az egyes csúcsba bemenő élek és kimenő élek száma egyenlő legyen egymással.[1]
Egy erősen reguláris gráf egy olyan reguláris gráf, ahol a szomszédok száma megegyezik minden csúcsnál, de két összekötött csúcs közös szomszédjainak a száma és két nem-összekötött csúcs közös szomszédainak száma is független a két pont választásától.
A kézfogás-lemma szerint minden véges irányítatlan gráf páros darab páratlan fokszámú csúccsal rendelkezik.
A Nash-Williams-tétel szerint minden csúcsú k-reguláris gráfban van Hamilton-kör.