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 enako:

{n(n-1)} \over 2.

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. 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. Polni grafi na n točkah pri n med 1 in 8 so prikazani spodaj:

K1 (prazni graf N1)
Povečaj
K1 (prazni graf N1)
K2
Povečaj
K2
K3
Povečaj
K3
K4
Povečaj
K4
K5
Povečaj
K5
K6
Povečaj
K6
K7
Povečaj
K7
K8
Povečaj
K8