Dowody i uzasadnienia - Grafy
Dowody i uzasadnienia - Grafy
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?
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?
Dowody i uzasadnienia - Grafy
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
\(\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
Dowody i uzasadnienia - Grafy
miodzio1988 pisze: 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
Dowody i uzasadnienia - Grafy
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
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
Dowody i uzasadnienia - Grafy
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
Dowody i uzasadnienia - Grafy
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że jakoś na podstawie tego że mam jedno krawędziowy graf z dwoma wierzchołkami
- Inkwizytor
- Użytkownik
- Posty: 4105
- Rejestracja: 16 maja 2009, o 15:08
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 1 raz
- Pomógł: 428 razy
Dowody i uzasadnienia - Grafy
Czy na pewno? a nie powinno być: "Suma stopni 2x większa od liczby krawędzi"laki_me pisze:a) Udowodnić że suma stopni wierzchołków dowolnego grafu spójnego jest dwa razy większa od liczby jego wierzchołków
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
Dowody i uzasadnienia - Grafy
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
- Użytkownik
- Posty: 4105
- Rejestracja: 16 maja 2009, o 15:08
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 1 raz
- Pomógł: 428 razy
Dowody i uzasadnienia - Grafy
Drzewo nietrywialnelaki_me pisze: 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?