Matematyka dyskretna - teoria grafów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
aleheca
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 sie 2007, o 23:26
Płeć: Mężczyzna
Lokalizacja: Białystok

Matematyka dyskretna - teoria grafów

Post autor: aleheca » 31 sie 2007, o 23:49

Witam!
Mam kilka zadań dotyczących teorii grafów. Nie wiem czy umieszczać wszystkie w jednym wątku, czy do każdego tworzyć osobny, więc na razie dla bezpieczeństwa podaję tylko jedno zadanie. Oto jego treść:

Czy każdy graf o 12 wierzchołkach, regularny stopnia 6 jest spójny?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

micholak
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 1 lis 2005, o 21:40
Płeć: Mężczyzna
Lokalizacja: warszawa
Pomógł: 41 razy

Matematyka dyskretna - teoria grafów

Post autor: micholak » 1 wrz 2007, o 00:06

Ok zauwaz ze jesli stopien kazdego wierzcholka w grafie jest wiekszy rowny 6 to w owym grafie istnieje cykl dlugosci 6 badz wiekszej.

Wskazowka druga
Jesli mamy graf ktory ma 6 lub mniej wieszcholkow to stopien kazdego jego wierzcholka jest mniejszy od 6.


edit
A domyslam sie ze mowimy o grafach prostychw przeciwnym wypadku kontrprzykladem sa 3 petelki na wierzcholku, ale to zbyt chyba upraszcza

aleheca
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 sie 2007, o 23:26
Płeć: Mężczyzna
Lokalizacja: Białystok

Matematyka dyskretna - teoria grafów

Post autor: aleheca » 1 wrz 2007, o 00:29

Mówimy o grafach prostych. tylko nie umiem wykorzystać tych wskazówek w udowodnieniu tego, że KAŻDY graf o 12 wierzchołkach, regularny stopnia 6 jest spójny. Może trzeba jednak pokazać jakiś kontrprzykład?

micholak
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 1 lis 2005, o 21:40
Płeć: Mężczyzna
Lokalizacja: warszawa
Pomógł: 41 razy

Matematyka dyskretna - teoria grafów

Post autor: micholak » 1 wrz 2007, o 09:07

Ok swieży i wypoczety... no mniej wiecej moge stwierdzic ze wskazowke pierwsza mozna spokojnie olac i zrobic tak.

Zalozmy ze nasz graf nie jest spojny.
A to znaczy ze ma jakies skladowe.
Skoro ma 12 wierzcholkow to w ktorej skladowej jest 6 lub mniej wierzcholkow.
A to jak mowila wskazowka druga jest sprzecznosc z tym ze stopien kazdego wierzcholka jest 6
Ostatnio zmieniony 8 wrz 2007, o 14:24 przez micholak, łącznie zmieniany 1 raz.

Boran
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 4 wrz 2007, o 01:23
Płeć: Mężczyzna
Lokalizacja: Białystok
Podziękował: 8 razy

Matematyka dyskretna - teoria grafów

Post autor: Boran » 8 wrz 2007, o 14:00

micholak, Wedlug mnie dla spelnienia warunkow zadania liczba wierzcholkow kazdej skladowej musiala by wynosic co najmniej 7, wtedy dla 7 w pierwszej skladowej reszty pozostaje nam 5 .Z czegi nie da sie juz zbudowac zadnej skladowej stopnia 6.

aleheca
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 sie 2007, o 23:26
Płeć: Mężczyzna
Lokalizacja: Białystok

Matematyka dyskretna - teoria grafów

Post autor: aleheca » 8 wrz 2007, o 14:24

a ja po rozważaniach i pomocy innych doszedłem do wniosku, że żeby udowodnić te zadanie trzeba posłużyć się tym, że każdy hamiltonowski jest spójny, wiec jeśli udowodnimy, że jest hamiltonowski to udowodnimy też, że jest spójny. Trzeba tu skorzystać z twierdzenia Orego, które brzmi: Jeśli graf prosty G=(V,E) o co najmniej 3'ech wierzchołkach posiada dwa dowolne niesąsiednie wierzchołki u i w, które spełniają zależność: deg(u) + deg(w) >= |V(G)| to graf ten jest hamiltonowski.

Dwa dowolne niesąsiednie wierzchołki naszego grafu spełniają tę zależność, więc nasz graf jest hamiltonowski, a jeżeli jest hamiltonowski to jest też spójny.
Pozdrawiam :).

Boran
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 4 wrz 2007, o 01:23
Płeć: Mężczyzna
Lokalizacja: Białystok
Podziękował: 8 razy

Matematyka dyskretna - teoria grafów

Post autor: Boran » 8 wrz 2007, o 15:15

Rozwiazanie do tego zadania i nie tylko w folderze dyskretna. Autor tego tematu i wszyscy studenci informatyki na pb zapewne maja juz te rozwiazania.
http://gorgeus.bcteam.org/egz.rar
Troszke zanczkow mi wcielo przy kopiowaniu:

wsyztskie takie grafy proste s , a hamiltonowskie
Graf hamiltonowski to graf rozwazany w teorii grafów zawieraj , acy sciezke (droge) przechodz , ac , a przez
kazdy wierzchołek dokładnie jeden raz zwan , a sciezk , a Hamiltona.

Twierdzenie Orego

Jesli graf prosty G ma n � 3 wierzchołków oraz deg(v) +deg(w) � n dla kazdej pary nies , asiednich wierz-chołków
v i w, to graf G jest hamiltonowski.
nasz graf:
n = 12,
deg(v) + deg(w) = 12 � n - dla kazdej pary nies , asiednich wierzchołków

Twierdzenie Gabriela Diraca Jesli dla grafu prostego G | V (G) | � 3 i deg(v) �
n
2 dla kazdego wierz-chołka
w G to graf jest hamiltonowski.
nasz graf:
| V (G) | = 12
n
2 = 6
deg(v) = 6 �
n
2
Ostatnio zmieniony 8 wrz 2007, o 16:01 przez Boran, łącznie zmieniany 1 raz.

aleheca
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 sie 2007, o 23:26
Płeć: Mężczyzna
Lokalizacja: Białystok

Matematyka dyskretna - teoria grafów

Post autor: aleheca » 8 wrz 2007, o 15:53

To nie jest twierdzenie Diraca, tylko wniosek Diraca, który powstał na podstawie Twierdzenia Orego, więc myślę, że można ten wniosek odpuścić.

ODPOWIEDZ