Pravidelný graf

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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ýva kubický 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.

Vlastnosti[upraviť | upraviť zdroj]

Externé odkazy=[upraviť | upraviť zdroj]

  • Tento článok je čiastočný alebo úplný preklad článku regulární graf na českej Wikipédii (číslo revízie nebolo určené).