Pólni gráf (redko tudi popólni gráf ali komplétni gráf) je v teoriji grafov graf, v katerem vsaka povezava povezuje par njegovih točk, oziroma kjer so vse točke povezane vsaka z vsako. Polni graf na n točkah se označuje s . Število povezav je kot posledica leme o rokovanju enako trikotniškim številom (OEIS A000217):

Polni graf
K7, polni graf na 7-ih točkah
Točken
Povezaven(n − 1) / 2
Premer1
Notranji obseg3 pri n ≥ 3
Avtomorfizemn! (Sn)
Kromatično številon
Kromatični indeksn pri lihem n
n-1 pri sodem n
Spekter
Značilnosti(n-1)-regularen
simetričen
točkovnoprehoden
povezavnoprehoden
z enotsko razdaljo
krepkoregularen
celoštevilski
Označba

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 -simpleksa. Geometrijsko je K3 soroden trikotniku, K4 tetraedru, K5 5-celici (pentahoronu) ipd.

Ravninski graf ne more vsebovati subdivizije (ali polnega dvodelnega grafa ) kot podgrafa (izrek Kuratowskega). K4 je torej največji polni graf, ki je še ravninski.

Polne grafe se običajno riše v obliki pravilnega mnogokotnika, razen grafa K4. Polni grafi na n točkah pri n med 1 in 12 so prikazani spodaj s številom povezav:

Glej tudi

uredi

Zunanje povezave

uredi
  • Weisstein, Eric Wolfgang. »Complete Graph«. MathWorld.