Polni graf
Iz Wikipedije, proste enciklopedije
Pólni gráf (redko tudi popólni gráf) je v teoriji grafov graf, v katerem vsaka povezava povezuje par njegovih točk (vozlišč), oziroma kjer so vse točke povezane vsaka z vsako. Poln graf na n točkah se označuje s Kn. Število povezav je kot posledica leme o rokovanju enako:
.
Polni graf je regularen stopnje n-1. Vsi polni grafi so maksimalno povezani, saj je točkovni prerez grafa, s katerim grafi postanejo nepovezani, kar celotna množica njegovih točk.
Polni graf z n točkami predstavlja robove n-simpleksa. Geometrijsko je K3 soroden trikotniku, K4 tetraedru, K5 pentakronu ipd.
Ravninski graf ne more vsebovati subdivizije K5 (ali polnega dvodelnega grafa K3,3) kot podgrafa (izrek Kuratowskega). K4 je torej največji polni graf, ki je še ravninski.
Polne grafe običajno rišemo v obliki pravilnega mnogokotnika, razen grafa K4. Polni grafi na n točkah pri n med 1 in 8 so prikazani spodaj:
 K1 (prazni graf N1) |
 K2 |
 K3 |
 K4 |
 K5 |
 K6 |
 K7 |
 K8 |
[uredi] Glej tudi
- prazni graf
- pot
