Matematické Fórum

vytautas · 19. 12. 2015 20:33

Zdravím

mám ďalšiu otázku: Aká je maximálna dimenzia priestoru kružníc grafu s $n$ vrcholmi ?

dimenzia priestoru $\mathfrak{C}$ pre graf $G=(V,E)$ je $|E|-|V|+k$ , kde $k$ je počet komponent grafu G.

Podľa mňa, výraz by bol maximálny, keď by to bol graf úplný, čiže $\binom{n}{2} - n+1=\frac{n^2-3n+2}{2}$

Ako to dokázať ?

Ďakujem .

Matematické Fórum

#1 19. 12. 2015 20:33

teória grafov #2

Zápatí