liczba krawędzi w grafie

dhreal · Post autor: **dhreal** » 15 paź 2009, o 14:03

Ile krawędzi ma zupełny graf \(\displaystyle{ K_{n}}\) o n wierzchołkach?

Szemek · Post autor: **Szemek** » 15 paź 2009, o 18:23

Wierzchołków jest \(\displaystyle{ n}\), z każdego wierzchołka wychodzi \(\displaystyle{ n-1}\) krawędzi i każda krawędź należy do dwóch wierzchołków.

\(\displaystyle{ \frac{n(n-1)}{2} = \binom{n}{2}}\)

dhreal · Post autor: **dhreal** » 15 paź 2009, o 20:17

a nie powino byc n(n+1) bo tak mowi prawo indukcji??
ale zdaje sie na ciebie

miodzio1988 · Post autor: **miodzio1988** » 16 paź 2009, o 10:37

\(\displaystyle{ K_{3}}\) ma 3 wierzchołki. Narysuj ten graf i zobacz, że ma on 3 krawędzie
Wzor Szemka:
\(\displaystyle{ \frac{3 \cdot 2}{2}=3}\)
Wzor dhreal:
\(\displaystyle{ \frac{3 \cdot 4}{2}=6}\)
Widzisz już?