szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 9 wrz 2015, o 20:07 
Użytkownik

Posty: 86
Lokalizacja: Gdańsk
Witam.

W jaki sposób można wykorzystać Szufladkową Zasadę Dirichleta w celu udowodnienia tezy głoszącej, że każdy graf prosty ma co najmniej dwa wierzchołki o tym samym stopniu?
Góra
Mężczyzna Offline
PostNapisane: 9 wrz 2015, o 21:13 
Użytkownik
Avatar użytkownika

Posty: 852
Lokalizacja: MiNI PW
Niech graf ma n wierzchołków.

Wierzchołek umieścimy w i-tej szufladce, jeżeli jego stopnień wynosi i, oczywiście i\in\{0,1,2,\ldots,n-1\}. Na razie jeszcze nic nie otrzymujemy, bo mamy n szufladek i n wierzchołków, ale zastanów się, czy mogą być naraz szufladki o numerach 0 oraz n-1?
Góra
Mężczyzna Offline
PostNapisane: 10 wrz 2015, o 10:30 
Użytkownik

Posty: 86
Lokalizacja: Gdańsk
Zatem odpowiedź będzie taka, że jest niemożliwe jednoczesne istnienie szufladki 0 i szufladki n - 1, ponieważ oznaczałoby to, że istnieje krawędź incydentna tylko z jednym wierzchołkiem, a to rodzi sprzeczność - krawędź - z definicji - jest podzbiorem 2 - elementowym wierzchołków (do jej istnienia potrzebne są 2 wierzchołki). Wynika z tego, że istnieją szufladki 1, 2, ..., n-1. Szufladek jest zawsze o 1 mniej niż wierzchołków, z których każdy ma stopień większy lub równy jeden. Zatem w choć jednej szufladce znajdą się przynajmniej 2 wierzchołki (szufladka oznacza stopień, więc przynajmniej 2 wierzchołki będą posiadały ten sam stopień)?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zasada szufladkowa Dirichleta - zadanie 25  t1tanium  5
 Graf Petersena - indeks chromatyczny  damtur  0
 Zasada włączeń i wyłączeń.  1608  1
 Graf, cykl Eulera  Gera  2
 Zasada szufladkowa Dirichleta - zadanie 2  Kamix___33  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl