Matematyka dyskretna - teoria grafów

[aleheca]

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?

[micholak]

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]

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]

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

[Boran]

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]

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]

Rozwiazanie do tego zadania i nie tylko w folderze dyskretna. Autor tego tematu i wszyscy studenci informatyki na pb zapewne maja juz te rozwiazania.

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

[aleheca]

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ć.