Grafy-stopnie wierzchołów

miodzio1988 · Post autor: **miodzio1988** » 25 cze 2009, o 23:41

Udowodnij, że:

Jeśli stopień każdego wierzchołka grafu G jest większy lub równy 2 to każdy wierzchołek leży na pewnym cyklu prostym.
Enjoy

BettyBoo · Post autor: **BettyBoo** » 26 cze 2009, o 12:05

Edit: Właściwie dochodzę do wniosku, że moja pierwsza odpowiedź była jednak poprawna. W grafie (nieskierowanym) o wierzchołkach a,b,c i krawędziach aa,ab,bc,cc jest spełniony warunek zadania, ale wierzchołek b nie leży w żadnym cyklu prostym.

Tobie pewnie chodziło o graf prosty Skoro jednak znasz rozwiązanie, to nie będę się wygłupiać

Pozdrawiam.

miodzio1988 · Post autor: **miodzio1988** » 26 cze 2009, o 12:14

BettyBoo, jak rozwiążesz to ukryj odpowiedź, ok?

Kod: Zaznacz cały

 [hide][/hide]

Bo zadanko wrzuciłem dla sportu - rozwiązanie znam

edit chodzi o graf prosty oczywiście jakoś nie uznaję tych zawijasów wokół wierzchołka

Szemek · Post autor: **Szemek** » 26 cze 2009, o 23:28

Nic ładnego nie przychodzi mi do głowy

Każdy wierzchołek ma co najmniej dwóch sąsiadów, a każde dwa sąsiadujące ze sobą wierzchołki (u,v) mają co najmniej jeden inny wierzchołek w zbiorze sąsiadów - \(\displaystyle{ u}\) ma zbiorze sąsiadów \(\displaystyle{ v}\), a \(\displaystyle{ v}\) ma zbiorze sąsiadów \(\displaystyle{ u}\).
Liczba wierzchołków w grafie jest skończona.
Zacznijmy od \(\displaystyle{ u}\), przechodzimy po krawędzi do następnego wierzchołka, który jest sąsiadem \(\displaystyle{ u}\) ale nie jest sąsiadem \(\displaystyle{ v}\) - niech będzie to wierzchołek \(\displaystyle{ a}\).
Od wierzchołka \(\displaystyle{ a}\) przechodzimy do jego sąsiada \(\displaystyle{ b}\), który nie jest sąsiadem \(\displaystyle{ u}\) i nie jest sąsiadem \(\displaystyle{ v}\). Następnie wierzchołek \(\displaystyle{ c}\), który jest sąsiadem \(\displaystyle{ b}\), ale nie jest sąsiadem \(\displaystyle{ u}\), \(\displaystyle{ v}\) oraz \(\displaystyle{ a}\) . Postępujemy tak do wyczerpania wszystkich wierzchołków - otrzymujemy sprzeczność, ponieważ pozostają nam dwa wierzchołki stopnia \(\displaystyle{ 1}\) - ostatni wybrany wierzchołek oraz wierzchołek \(\displaystyle{ v}\).
A przecież każdy z tych wierzchołków powinien mieć jeszcze co najmniej jednego sąsiada.
Łącząc dane wierzchołki z dowolnym wierzchołkiem (spełniając warunek grafu prostego) otrzymujemy cykl.

I tu zastanawia mnie przypadek grafów z mostem:

miodzio1988 · Post autor: **miodzio1988** » 26 cze 2009, o 23:31

Szemek pisze: I tu zastanawia mnie przypadek grafów z mostem:

Taki graf jest właśnie kontrprzykładem

Wierzchołek \(\displaystyle{ d}\) nie należy do żadnego cyklu prostego Koniec
Nie każde twierdzenie musi być prawdziwe, wiesz?

Szemek · Post autor: **Szemek** » 26 cze 2009, o 23:34

miodzio1988 pisze:Nie każde twierdzenie musi być prawdziwe, wiesz?

Miałem okazję przekonać się przy tw. Diraca czy Orego.
Dobra, poszukam jakieś zadanie dla Ciebie