logowanie

matematyka » forum » studia » zadanie

Matematyka dyskretna, zadanie nr 4665

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

brightnesss
postów: 113
2016-06-06 21:43:08

Pokazać, że jeśli $\delta(G)> $ (podłoga z) $\frac{n}{2}-1$ to G jest spójny.


bierzemy podłogę z liczby tylko $\frac{n}{2}$
Przepraszam, nie wiedziałam jak to zapisać


janusz78
postów: 820
2016-06-07 16:01:44

Jeżeli rozważymy składową o najmniejszej liczbie wierzchołków to liczba jej wierzchołków wynosi co najmniej $ 1 + \frac{n}{2}> \frac{n}{2}$.
Więc z nierówności:
$ \delta(G)> \lfloor \frac{n}{2}-1 \rfloor $
wynika, że jest tylko jedna taka składowa, czyli graf jest spójny.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 38 drukuj