Kompletné a bipartitné grafy


Kompletný graf s   vrcholmi má  hrán, priemer 1 a polomer 1.
  • Na obrázku vidíme kompletné grafy s 3, 4 a 5 vrcholmi.
 
  • Na obrázku vidíme príklad bipartitného grafu.

    Vrcholy jednej podmnožiny sme znázornili modrou a vrcholy druhej podmnožiny červenou farbou. Vidíme, že hranou nie sú nikdy spojené dva vrcholy s rovnakou farbou.
 

Kompletný bipartitný graf  má  hrán a vzdialenosť žiadnych dvoch jeho vrcholov nie je väčšia ako 2.
  • Na obrázku vidíme príklad kompletného bipartitného grafu  .

    Tri vrcholy jednej podmnožiny sme znázornili modrou a štyri vrcholy druhej podmnožiny červenou farbou. Vidíme, že hranou nie sú nikdy spojené dva vrcholy s rovnakou farbou. Vrcholy s rôznou farbou sú vždy spojené hranou.