Plena grafeo

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj
grafeo
arbo
subgrafeo
ciklo
kliko
grado de vertico
grado de grafeo

Elektitaj klasoj de grafeoj
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudividebla
Fenda grafeo
regula grafeo
grafeo de Euler
grafeo de Hamilton
grafeo senrelifa

pli...

Grafeaj algoritmoj
A*
Bellman-Ford
Dijkstry
Fleury
Floyd-Warshall
Johnson
Kruskal
Prim
traserĉado de grafeo
– en larĝeco
– en profundo
plej proksima najbaro

Problemoj prezentataj kiel grafeaj
problemo de vojaĝisto
problemo de ĉina leteristo
problemo de marŝrutigado
problemo de kunigado de geedzoj

Aliaj
kodo de Gray
diagramo de Hasse
kodo de Prüfer

Reprezentado de grafeo Glosaro de grafeoteorio

vidi • diskuti • redakti

En grafeteorio, plena grafeo estas simpla grafeo en kiu ĉiu paro de malsamaj verticoj estas koneksa per latero.

La plena grafeo de n verticoj havas n(n-1)/2 laterojn, kaj estas skribata kiel K_n. Ĝi estas regula grafeo de grado n-1. Ĉiu plena grafeo estas kliko. Plenaj grafeoj estas maksimume koneksa kiel la nura vertica tranĉo kiu malkonektigas la grafeon estas la plena aro de verticoj.

Plena grafeo de n verticoj havas n! aŭtomorfiojn kie la signo "!" signifas faktorialon.

Plena grafeo kun n verticoj prezentas la verticojn kaj laterojn de (n-1)-simplaĵo. Tiel K₃ respektivas al triangulo, K₄ respektivas al kvaredro, K₅ respektivas al kvinĉelo, kaj tiel plu.

K₁ estas K₄ estas ebenaj grafeo. Teoremo de Kuratowski diras ke ebena grafeo ne povas enhavi parton K₅ (aŭ la plenan dukoloran grafeon K_{3, 3}) kiel minoro. Pro tio keK_n inkluzivas na K_n-1, plena grafeo K_n por n>4 ne estas ebena.