Polni graf

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 $K_n$. Število povezav je kot posledica leme o rokovanju enako trikotniškim številom Predloga:OEIS:

$(\genfrac{}{}{0ex}{}{n}{2})=\frac{n(n-1)}{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.

Polni graf z n točkami predstavlja robove $(n-1)$-simpleksa. Geometrijsko je K₃ soroden trikotniku, K₄ tetraedru, K₅ 5-celici (pentahoronu) ipd.

Ravninski graf ne more vsebovati subdivizije $K_5$ (ali polnega dvodelnega grafa $K_{3,3}$) kot podgrafa (izrek Kuratowskega). K₄ je torej največji polni graf, ki je še ravninski.

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

• 
  K₁ (prazni graf N₁): 0
• 
  K₂: 1
• 
  K₃: 3
• 
  K₄: 6
• 
  K₅: 10
• 
  K₆: 15
• 
  K₇: 21
• 
  K₈: 28
• 
  K₉: 36
• 
  K₁₀: 45
• 
  K₁₁: 55
• 
  K₁₂: 66
• 
  K₁₃: 78
• 
  K₁₄: 91
• 
  K₁₅: 105
• 
  K₁₆: 120
• 
  K₁₇: 136
• 
  K₁₈: 153
• 
  K₁₉: 171
• 
  K₂₀: 190
• 
  K₂₁: 210
• 
  K₂₂: 231
• 
  K₂₃: 253
• 
  K₂₄: 276
• 
  K₂₅: 300

Glej tudi

• prazni graf
• pot

Zunanje povezave

• Predloga:MathWorld