Plena grafeo

En grafeoteorio, plena grafeo estas simpla grafeo, en kiu ĉiun paron de malsamaj verticoj konektas eĝo.

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 grafeoj. 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 Km por ĉiu m < n, plena grafeo Kn kun n > 4 ne estas ebena.

 K1: 0 eĝoj  K2: 1 eĝoj  K3: 3 eĝoj  K4: 6 eĝoj 140px 140px 140px 140px K5: 10 eĝoj  K6: 15 eĝoj  K7: 21 eĝoj  K8: 28 eĝoj 140px 140px 140px 140px

 Vidu ankaŭ 
 Ciklo (grafeoteorio)
 Vojo (grafeo)
 Nulgrafeo, speciale, seneĝa grafeo estas la malo de plena grafeo
 Kliko (grafeoteorio) estas plena subgrafeo

 Eksteraj ligiloj 

 Mehdi Hassani, Kalkulado de vojoj kaj cikloj en plenaj grafeoj   aŭ 


Kategorio:Grafeteorio