szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 12 kwi 2016, o 13:44 
Użytkownik

Posty: 18
Lokalizacja: Krk
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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 12 kwi 2016, o 15:36 
Użytkownik

Posty: 22
Lokalizacja: Warszawa
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ć :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wykaż, że zachodzi relacja  hubertwojtowicz  0
 Indukcja -graf  diablomichal  0
 graf planarny - jak sprawdzic  assimar  8
 [Teoria grafów] dowód, graf dwudzielny, graf planarny  matinf  3
 graf Hassego- rysowanie i roztrzyganie o cześciowym porządku  frankez  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl