Reguláris gráf

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív → {\displaystyle {\boldsymbol {\rightarrow }}} távolságreguláris ← {\displaystyle {\boldsymbol {\leftarrow }}} erősen reguláris
↓ {\displaystyle {\boldsymbol {\downarrow }}}
szimmetrikus ← {\displaystyle {\boldsymbol {\leftarrow }}} t-tranzitív, t ≥ 2ferdeszimmetrikus
↓ {\displaystyle {\boldsymbol {\downarrow }}}
(ha összefüggő)
csúcs- és éltranzitív		 → {\displaystyle {\boldsymbol {\rightarrow }}} éltranzitív és reguláris → {\displaystyle {\boldsymbol {\rightarrow }}} éltranzitív
↓ {\displaystyle {\boldsymbol {\downarrow }}} ↓ {\displaystyle {\boldsymbol {\downarrow }}} ↓ {\displaystyle {\boldsymbol {\downarrow }}}
csúcstranzitív → {\displaystyle {\boldsymbol {\rightarrow }}} reguláris → {\displaystyle {\boldsymbol {\rightarrow }}} (ha páros)
bireguláris
↑ {\displaystyle {\boldsymbol {\uparrow }}}
Cayley-gráf ← {\displaystyle {\boldsymbol {\leftarrow }}} zérószimmetrikusaszimmetrikus

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 2 k + 1 {\displaystyle 2k+1} csúcsú k-reguláris gráfban van Hamilton-kör.

Egzisztencia

Akkor és csak akkor létezik n csúcsú k {\displaystyle k} -reguláris gráf, ha , ha n ≥ k + 1 {\displaystyle n\geq k+1} és n k {\displaystyle nk} páros. Ebben az esetben egy ilyen reguláris gráf könnyen megkonstruálható megfelelően paraméterezett cirkuláns gráfként.[forrás?]

Osztályozá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.
  • A 3-reguláris gráfokat angol nyelvterületen cubic graph-nak nevezik.
  • 0-reguláris gráf
    0-reguláris gráf
  • 1-reguláris gráf
    1-reguláris gráf
  • 2-reguláris gráf
    2-reguláris gráf
  • 3-reguláris gráf
    3-reguláris gráf

Algebrai tulajdonságok

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

A gráf akkor és csak akkor reguláris, ha j = ( 1 , … , 1 ) {\displaystyle {\textbf {j}}=(1,\dots ,1)} sajátvektora A-nak.[2] Ekkor a sajátérték k. A többi sajátértéknek megfelelő sajátvektorok merőlegesek j {\displaystyle {\textbf {j}}} -re, tehát az ilyen sajátvektorok koordinátáinak összege nulla.

Egy k-reguláris gráf csak akkor összefüggő, ha k egyszeres sajátértéke. A "csak akkor" meghatározás a Perron–Frobenius-tétel következménye.[2]

Van egy másik kritérium a reguláris és összefüggő gráfokra: egy gráf pontosan akkor reguláris és összefüggő, ha az

[ 1 ⋯ 1 ⋮ ⋱ ⋮ 1 ⋯ 1 ] {\displaystyle {\begin{bmatrix}1&\cdots &1\\\vdots &\ddots &\vdots \\1&\cdots &1\end{bmatrix}}}

mátrix eleme A szomszédsági algebrájának, azaz előáll A hatványainak lineáris kombinációjaként.[3]

Legyen G k- reguláris gráf, D átmérővel és k = λ 0 > λ 1 ≥ ⋯ ≥ λ n − 1 {\displaystyle k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}} sajátértékekkel. Ha G nem páros gráf, akkor

D ≤ log ⁡ ( n − 1 ) log ⁡ ( λ 0 / λ 1 ) + 1. {\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}

Példák

Generálás

Létezik gyors algoritmus az adott fokszámú és csúcsszámú reguláris gráfok izomorfizmus erejéig való felsorolására.[4]

Jegyzetek

  1. ↑ Chen, Wai-Kai. Graph Theory and its Engineering Applications. World Scientific, 29. o. (1997). ISBN 978-981-02-1859-1 
  2. ↑ a b Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
  3. ↑ Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography 34 (2-3): 241–248, DOI 10.1007/s10623-004-4857-4.
  4. ↑ Meringer (1999). „Fast generation of regular graphs and construction of cages”. Journal of Graph Theory 30 (2), 137–146. o. DOI:<137::AID-JGT7>3.0.CO;2-G 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.  

Fordítás

Ez a szócikk részben vagy egészben a Regular graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Kapcsolódó szócikkek

További információk

    • Weisstein, Eric W.: Regular Graph (angol nyelven). Wolfram MathWorld
    • Weisstein, Eric W.: Strongly Regular Graph (angol nyelven). Wolfram MathWorld
    • GenReg software and data by Markus Meringer.
    • Nash-Williams, Crispin (1969), Valency Sequences which force graphs to have Hamiltonian Circuits, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo