Pravidelný graf
z Wikipédie, slobodnej encyklopédie
Pravidelný graf alebo regulárny graf je graf, ktorý má všetky vrcholy rovnakého stupňa.
Regulárny graf s vrcholmi, ktoré majú stupeň k sa nazýva k-regulárny.
Regulárne grafy stupňa najviac 2 možno jednoducho popísať: 0-regulárny graf sa skladá zo samostatných vrcholov (bez hrán), 1-regulárny zo samostatných hrán a 2-regulárny zo samostatných kružníc. 3-regulárny graf sa nazývá kubický graf.
-
0-regulárny graf
-
1-regulárny graf
-
2-regulárny graf
-
3-regulárny graf
Silno regulárny graf je taký graf, v ktorom má každá dvojica susedných vrcholov rovnaký počet k spoločných susedov a každá dvojica nesusediacich vrcholov rovnaký počet n spoločných susedov. Najmenší regulárny graf, ktorý nie je silno regulárny, je cyklický graf na 6 vrcholoch.
[upraviť] Vlastnosti
- Úplný graf Kn je silno regulárny pre ľubovolné n.
- Podľa Nash-Williamsovej teorémy každý k‑regularny graf s 2k + 1 vrcholmi má Hamiltonovu kružnicu.
 |
Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš. |
[upraviť] Externé odkazy=
- Tento článok je sčasti alebo úplne založený na preklade článku regulární graf na českej Wikipédii (číslo revízie nebolo určené).
