Grafo oso

Grafo teorian, grafo osoa erpin guztiak ertzen bidez konektatuta dituen grafo sinplea da.

Grafo oso
K7, 7 erpineko grafo osoa.
Erpinak	n
Ertzak	n (n-1)/2
Diametroa	1
Gerria	3, n ≥ 3 bada
Automorfismoak	n! (Sn)
Zenbaki kromatikoa	n
Indize kromatikoa	n, n bakoitia bada n-1, n bikoitia bada
Propietateak	(n-1)-erregularra Simetrikoa Erpin iragankorra Ertz iragankorra Distantzia unitatea Biziki erregularra Integrala

$n$ erpineko grafo oso batek $n(n-1)/2$ ertz ditu, eta $K_{n}$ notazioaz adierazten da. Bere erpin guztiek $(n-1)$ gradua dutenez grafo erregularra da.

Kuratowski-ren teoremaren arabera, grafo lau batek ezin du $K_{5}$ grafo osoa (edo $K_{3,3}$ zatibiko grafo osoa) bere baitan izan. $K_{n}$ grafoek $K_{n-1}$ bere baitan dutenez, grafo osoa ezin da laua izan $n$$\geq$$5$ balioetarako.

Adibideak

Hona hemen erpin kopurua $n=1$ eta $n=12$ artean duten $K_{n}$ grafo osoak eta haien ertz kopurua:

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

Kanpo estekak

• Datuak: Q45715
• Multimedia: Complete graphs / Q45715