Reguláris gráf

Reguláris gráfok
Bérczi Gergely
Gács András
Köszönet a Bolyai Farkas Ösztöndíj támogatásáért.

DEFINÍCIÓ: Azokat a gráfokat, amelyekben minden pont foka azonos, reguláris gráfnak nevezzük. Ha minden pont foka d, akkor a gráf d-reguláris.
Ezek szerint előző megállapításunk így is fogalmazható: ...

2) Egy 2n pontú reguláris gráf (minden fokszám ugyanannyi) csúcshalmazát két egyenlő (azaz egyenként n elemszámú) csúcshalmazba osztjuk. Bizonyítsuk be, hogy mindkét osztályon belül ugyanannyi él halad.

Az erősen reguláris gráf olyan reguláris gráf, melyben minden szomszédos csúcspár közös szomszédainak száma is megegyezik, továbbá minden nem szomszédos csúcspár közös szomszédainak száma is megegyezik.

See also: Gráf, Reguláris, Él, Végpont, Fokszám