Dowody i uzasadnienia - Grafy

[laki_me]

a) Udowodnić że suma stopni wierzchołków dowolnego grafu spójnego jest dwa razy większa od liczby jego wierzchołków
b) Uzasadnić, że w grafie pełnym o n wierzchołkach istnieje droga Hamiltona, a następnie wyznaczyć liczbę takich dróg
c) Podać przykład grafu spójnego o co najmniej czterech wierzchołkach, w którym nie istnieje droga Euloera. W którym momencie przestaje działać algorytm Fleury'ego?

[miodzio1988]

b) SKorzystaj z twierdzenia:
\(\displaystyle{ G=(V,E)}\)
Niech \(\displaystyle{ n= \left|V \right| \ \forall v \in V \ degv> \frac{n-1}{2} \Rightarrow G}\) ma cykl Hamiltona
A liczbę takich drog łatwo wyznaczyc. Pomyśl
a) Elementarne zadanie. Musisz znac podstawowe pojecia takie jak spojnosc i stopien wierzcholka, żeby je zrobic. Znasz te pojecia? Jesli nie to czemu? Jesli tak to jaki jest problem? Narysuj kilka grafow i zobacz czy to jest prawda najpierw

c) Niech jeden wierzcholek będzie wierzcholekiem izolowanym. I niech ten wierzcholek będzie sąsiadem wierzcholka stopnia 3. Dalszę konstrukcję zostawiam Tobie(no juz duzo w tym zadania myslec nie trzeba). Twierdzenie Eulera sobie przypomnij

[laki_me]

c) Niech jeden wierzcholek będzie wierzcholekiem izolowanym. I niech ten wierzcholek będzie sąsiadem wierzcholka stopnia 3.

no wiesz, jak dla mnie w grafie spójnym nie może być wierzchołka izolowanego, chyba że chodziło ci żebym w ten sposób budował graf, no ale rację miałeś, wystarczyło przypomnieć sobie że przecież taki graf może mieć albo dwa albo 0 wierzchołków o stopniu parzystym

co do podpunktu a) to wiem co to jest stopień i graf spójny, tyle że nie wiem jak to nie udowodnić, a no i rysowałem parę grafów i było jak było...
co do b) dzięki, rozumiem

[miodzio1988]

c) Chodziło mi o wierzchołek stopnia jeden Nazwy mi się pomyliły;]
Więc z tym zadaniem nie mamy problemu....
b) banał już
Jeszcze a)
Pewny jestes , że to dobrze napisales? Narysuj kilka grafow spojnych i zobacz czy się zgadza

[laki_me]

No sprawdzałem: grafy petersena, różne spójne, ale na logikę biorąc...moim zdaniem nie ma,no ale jak możesz to weź mi zaproponuj jakiś spójny graf który tego warunku nie spełnia? Ja przyznam że nie potrafię udowodnić tego że każdy jest taki chyba że jakoś na podstawie tego że mam jedno krawędziowy graf z dwoma wierzchołkami

[miodzio1988]

że jakoś na podstawie tego że mam jedno krawędziowy graf z dwoma wierzchołkami

Dwa wierzchołki, suma stopni rowna 2. \(\displaystyle{ 2=2}\) Graf ten jest kontprzykladem. No chyba, że dodamy kilka zalozen do twierdzenia , ale w takiej postaci twierdzenie prawdziwe nie jest

[Inkwizytor]

a) Udowodnić że suma stopni wierzchołków dowolnego grafu spójnego jest dwa razy większa od liczby jego wierzchołków

Czy na pewno? a nie powinno być: "Suma stopni 2x większa od liczby krawędzi"

Weźmy chociażby dwa wierzchołki i jedną krawędź między nimi i juz obaliłem punkt a)
Jeśli mam racje to dowód jest prosty:

Macierz incydencji:
wiersze to kolejne wierzchołki (n) kolumny to krawędzie (m)
wartości w tabeli to 0,1,2
0 - krawędz nie skojarzona z danym wierzchołkiem
1 - krawedz ma jeden z konców w danym wierzchołku
2 - pętla
sumujemy poziomo i mamy stopien wierzchołka
sumujemy pionowa i zawsze 2
i otrzymamy suma stopni = 2m

[laki_me]

panowie, tu był haczyk, i moja głupota że dokładnie nie czytam treści zadań, czytałem wierzchołki myślałem krawędzie, serdeczne dzięki

[Inkwizytor]

c) Podać przykład grafu spójnego o co najmniej czterech wierzchołkach, w którym nie istnieje droga Euloera. W którym momencie przestaje działać algorytm Fleury'ego?

Drzewo nietrywialne