Wykazać, że w spójnym grafie prostym o 8 wierzchołkach istnieją co najmniej dwa wierzchołki jednakowych stopni.
Wskazówka: Założyć, że pewnych siedem wierzchołków tego grafu ma różne stopnie. Jakie to muszą być stopnie? Wywnioskować informacje o stopniu ostatniego wierzchołka.
Bardzo proszę o pokazanie, jak udowodnić tą tezę. Będę bardzo wdzięczna -- 12 kwi 2016, o 13:14 --Zgodzicie się ze mną?
Z: mamy spójny graf o 8 wierzchołkach
T: istnieją co najmniej 2 wierzchołki jednakowych stopni
D: załóżmy, że pewnych 7 wierzchołków tego grafu ma różne stopnie. Gdybyśmy chcieli, żeby każdy wierzchołek naszego grafu miał różny stopień, to zaczynając próbę wyznaczania tych stopni od największego możliwego do uzyskania tzn. st.6, to zauważamy, że kolejny musiałby mieć: st.5, st.4, st.3, st.2, st.1 i ... brakuje nam liczby, ponieważ kończymy liczyć stopnie na 1, a został nam jeszcze jeden wierzchołek, któremu nie przydzieliliśmy stopnia będącego różnym od pozostałych. Nie możemy mu przydzielić st.0, bo rozpatrujemy graf spójny prosty, co oznacza, że graf musi mieć przynajmniej 2 wierzchołki tego samego stopnia. Analogicznie odbywa się to w grafie spójnym prostym o 8 wierzchołkach, co kończy dowód.
Wykaż, że... graf spójny - wierzchołki - jednakowe stopnie
-
- Użytkownik
- Posty: 21
- Rejestracja: 10 kwie 2016, o 01:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 7 razy
Wykaż, że... graf spójny - wierzchołki - jednakowe stopnie
OK, ale troszkę przegadane
Masz 8 wierzchołków i 7 możliwych stopni. Z zasady szufladkowej 2 wierzchołki mają ten sam stopień.
BTW zasada szufladkowa to oczywistość, ale warto się na nią powoływać, by się nie napisać
Masz 8 wierzchołków i 7 możliwych stopni. Z zasady szufladkowej 2 wierzchołki mają ten sam stopień.
BTW zasada szufladkowa to oczywistość, ale warto się na nią powoływać, by się nie napisać