Plena grafeo
En grafeoteorio, plena grafeo estas simpla grafeo, en kiu ĉiun paron de malsamaj verticoj konektas eĝo.
La artikolo estas parto de serio pri grafeoteorio.
|
Plej gravaj terminoj Elektitaj klasoj de grafeoj Grafeaj algoritmoj Problemoj prezentataj kiel grafeaj Aliaj Reprezentado de grafeo Glosaro de grafeoteorio |
La plena grafeo de n verticoj havas eĝojn, kaj signiĝas per Kn. Ĝi estas regula grafeo de grado (n-1). Ĉiu plena grafeo estas kliko. Plenaj grafeoj estas maksimume koneksa ĉar la unusola vertica tranĉo kiu povas disigi la grafeon estas la tuta aro de verticoj.
Plena grafeo de n verticoj havas aŭtomorfiojn kie la signo "!" signifas faktorialon.
Plena grafeo kun n verticoj prezentas la verticojn kaj eĝo de (n-1)-simplaĵo. Tiel K3 respektivas al triangulo, K4 respektivas al kvaredro, K5 respektivas al kvinĉelo, kaj tiel plu.
K1 ĝis K4 estas ebenaj grafeo. Teoremo de Kuratowski asertas, ke ebena grafeo ne povas enhavi parton K5 (aŭ la plenan dukoloran grafeon K3, 3) kiel minoro. Pro tio ke Kn inkluzivas Kn-1, plena grafeo Kn kun n > 4 ne esta ebena.
K1: 0 lateroj | K2: 1 latero | K3: 3 lateroj | K4: 6 lateroj |
---|---|---|---|
K5: 10 lateroj | K6: 15 lateroj | K7: 21 lateroj | K8: 28 lateroj |
Vidu ankaŭ
redakti- Ciklo (grafeteorio)
- Vojo (grafeo)
- Nulgrafeo, speciale, seneĝa grafeo estas la malo de plena grafeo
- Kliko (grafeteorio) estas plena subgrafeo
Eksteraj ligiloj
redakti- Mehdi Hassani, Kalkulado de vojoj kaj cikloj en plenaj grafeoj [1] Arkivigite je 2007-12-16 per la retarkivo Wayback Machine aŭ [2]
- Eric W. Weisstein, Plena grafeo en MathWorld.