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

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

La plena grafeo de n verticoj havas ${\frac {n(n-1)}{2}}$ eĝojn, kaj signiĝas per K_n. Ĝ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 $n!$ aŭtomorfiojn kie la signo "!" signifas faktorialon.

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

K₁ ĝis K₄ estas ebenaj grafeoj. Teoremo de Kuratowski asertas, ke ebena grafeo ne povas enhavi parton K₅ (aŭ la plenan dukoloran grafeon K_{3, 3}) kiel minoro. Pro tio, ke K_n inkluzivas K_m por ĉiu m < n, plena grafeo K_n kun n > 4 ne estas ebena.

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

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 Arkivigite je 2007-12-16 per la retarkivo Wayback Machine aŭ
• Eric W. Weisstein, Plena grafeo en MathWorld.