Reguláris gráf

A Wikipédiából, a szabad enciklopédiából
Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív távolságreguláris erősen reguláris
szimmetrikus t-tranzitív, t ≥ 2 ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláris éltranzitív
csúcstranzitív reguláris (ha páros)
bireguláris
Cayley-gráf zérószimmetrikus aszimmetrikus

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.

Osztályozás[szerkesztés]

A legfeljebb 2-reguláris gráfok egyszerűen osztályozhatóak.

  • A 0-reguláris gráfok nem tartalmaznak éleket, ezek az üres gráfok.
  • Az 1-reguláris gráfok egy-egy éllel összekötött csúcspárokat tartalmaznak.
  • A 2-reguláris gráfok csúcsidegen körökből állnak.

Algebrai tulajdonságok[szerkesztés]

Legyen egy gráf szomszédsági mátrixa.

  1. G pontosan akkor reguláris, ha az vektor sajátvektora -nak. Ehhez a sajátvektorhoz tartozó sajátérték k, ha G k-reguláris.
  2. Egy k-reguláris gráf pontosan akkor összefüggő, ha k egyszeres sajátértéke.
  3. Egy gráf pontosan akkor reguláris és összefüggő, ha az mátrix eleme az mátrix szomszédsági algebrájának, azaz előáll hatványainak lineáris kombinációjaként (A. J. Hoffmann, 1963).

Példák[szerkesztés]

  1. Minden teljes gráf reguláris.
  2. Minden hiperkockagráf reguláris.
  3. Az egyenlő nagyságú osztályokkal rendelkező teljes páros gráfok regulárisak.
  4. Minden gyűrűs kocka 3-reguláris.