Jak uzasadnić nierówność \( \delta \le \frac{2 \varepsilon }{\nu} \)? Gdzie \( \delta \) to minimalny stopień wierzchołka, \( \varepsilon \) - liczba krawędzi w grafie, \(\nu\) - liczba wierzchołków w grafie.
Bardzo proszę o jakieś wyjaśnienia.
teoria grafów - stopień minimalny wierzchołków
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 2963
- Rejestracja: 14 lis 2016, 14:38
- Podziękowania: 33 razy
- Otrzymane podziękowania: 1303 razy
- Płeć:
Re: teoria grafów - stopień minimalny wierzchołków
Jeśli wszystkie wierzchołki będą miały ten sam minimalny stopień to liczba krawędzi wynosi:
\( \varepsilon =\frac12\delta \nu\)
a gdy nie wszystkie wierzchołki posiadają minimalny stopień to
\( \varepsilon >\frac12\delta \nu\).
Ergo:
\( \varepsilon \ge \frac12\delta \nu\)
więc
\(\delta \le \frac{2\varepsilon}{\nu} \)
\( \varepsilon =\frac12\delta \nu\)
a gdy nie wszystkie wierzchołki posiadają minimalny stopień to
\( \varepsilon >\frac12\delta \nu\).
Ergo:
\( \varepsilon \ge \frac12\delta \nu\)
więc
\(\delta \le \frac{2\varepsilon}{\nu} \)