Reguláris gráf

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

  1. Minden teljes gráf reguláris.
  2. Minden hiperkocka grá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.