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 \boldsymbol{\rightarrow} távolságreguláris \boldsymbol{\leftarrow} erősen reguláris
\boldsymbol{\downarrow}
szimmetrikus \boldsymbol{\leftarrow} t-tranzitív, t ≥ 2 ferdeszimmetrikus
\boldsymbol{\downarrow}
(ha összefüggő)
csúcs- és éltranzitív
\boldsymbol{\rightarrow} éltranzitív és reguláris \boldsymbol{\rightarrow} éltranzitív
\boldsymbol{\downarrow} \boldsymbol{\downarrow} \boldsymbol{\downarrow}
csúcstranzitív \boldsymbol{\rightarrow} reguláris \boldsymbol{\rightarrow} (ha páros)
bireguláris
\boldsymbol{\uparrow}
Cayley-gráf \boldsymbol{\leftarrow} 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 A egy G=(V, E) gráf szomszédsági mátrixa.

  1. G pontosan akkor reguláris, ha az \begin{bmatrix}1\\ \vdots \\1 \end{bmatrix} vektor sajátvektora A-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 \begin{bmatrix}
  1      & \cdots & 1      \\
  \vdots & \ddots & \vdots \\
  1      & \cdots & 1
\end{bmatrix} mátrix eleme az A mátrix szomszédsági algebrájának, azaz előáll A 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.