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.
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 
 Graf regularny - zadanie 2  edaro  0
 graf trójkątny  matinf  0
 Wykaż, że... - symbol Newtona  rafaluk  3
 Graf pełny trójdzielny.  klaudiak  1
 Graf, zmiana cyklu  Crave  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl