Polni graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Polni graf
Complete graph K7.svg
K7, polni graf na 7 točkah
Točke n
Povezave n(n − 1) / 2
Premer 1
Notranji obseg 3 pri n ≥ 3
Avtomorfizem n! (Sn)
Kromatično število n
Kromatični indeks n pri lihem n
n-1 pri sodem n
Spekter \left\{\begin{array}{ll}\{0^1\} & n = 1\\ \{(n - 1)^1, -1^{n - 1}\} & \text{drugače}\end{array}\right.
Značilnosti (n-1)-regularen
simetričen
točkovno-prehoden
povezavno-prehoden
z enotsko razdaljo
krepko regularen
celoštevilčen
Označba K_{n}\!\,

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 (vozlišč), oziroma kjer so vse točke povezane vsaka z vsako. Poln graf na n točkah se označuje s K_{n}. Število povezav je kot posledica leme o rokovanju enako trikotniškim številom (OEIS A000217):

 {n \choose 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-simpleksa. Geometrijsko je K3 soroden trikotniku, K4 tetraedru, K5 pentakronu ipd.

Ravninski graf ne more vsebovati subdivizije K_{5} (ali polnega dvodelnega grafa K_{3,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 12 so prikazani spodaj s številom povezav:

Glej tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]