Plena grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
La artikolo estas parto de serio pri grafeteorio.




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


Elektitaj klasoj de grafejo
plena grafeo
plena dukolora grafeo
kohera grafeo
arbo
grafeo dudivdebla
Fenda grafeo
regula grafeo
grafeo de Euler
grafeo de Hamilton
grafeo senrelifa


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


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


Reprezentado de grafeo Glosaro de grafeteorio


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 Kn. Ĝ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 K3 respektivas al triangulo, K4 respektivas al kvaredro, K5 respektivas al kvinĉelo, kaj tiel plu.

K1 estas K4 estas ebenaj grafeo. Teoremo de Kuratowski diras ke ebena grafeo ne povas enhavi parton K5 (aŭ la plenan dukoloran grafeon K3, 3) kiel minoro. Pro tio keKn inkluzivas na Kn-1, plena grafeo Kn por n>4 ne estas ebena.

K1: 0 lateroj K2: 1 latero K3: 3 lateroj K4: 6 lateroj
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K5: 10 lateroj K6: 15 lateroj K7: 21 lateroj K8: 28 lateroj
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]