Średni stopień w grafie spójnym
-
- Użytkownik
- Posty: 97
- Rejestracja: 14 sty 2014, o 19:35
- Płeć: Kobieta
- Lokalizacja: Lublin
- Podziękował: 7 razy
Średni stopień w grafie spójnym
Średnim stopniem w grafie G nazywamy liczbę określoną wzorem: \(\displaystyle{ d_r{r}(G) = \frac{\left| E\right| }{\left| V\right| }}\). Wykazać, że dla grafu spójnego G zachodzi nierówność:\(\displaystyle{ 1- \frac{1}{\left| V\right| } \le d_{r}(G) \le \frac{\left| V\right| }{2}}\).
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Średni stopień w grafie spójnym
Skoro graf jest spójny, to \(\displaystyle{ |V|\leq |E|+1}\) i po elementarnych przekształceniach mamy \(\displaystyle{ 1-\frac{1}{|V|}\leq d_r(G)}\).
Graf mający \(\displaystyle{ |V|}\) wierzchołków może mieć co najwyżej \(\displaystyle{ \frac{|V|^2}{2}}\) krawędzi (każdy z każdym, a że wtedy liczymy podwójnie, to dzielimy przez dwa) i to załatwia drugą nierówność.
Graf mający \(\displaystyle{ |V|}\) wierzchołków może mieć co najwyżej \(\displaystyle{ \frac{|V|^2}{2}}\) krawędzi (każdy z każdym, a że wtedy liczymy podwójnie, to dzielimy przez dwa) i to załatwia drugą nierówność.