szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
 Tytuł: teoria grafów
PostNapisane: 25 paź 2015, o 14:26 
Użytkownik

Posty: 25
Lokalizacja: katowice
Witam :)
Mam problem z trzema zadaniami:

1. Czy graf regularny stopnia r mający 2r + 1 wierzchołków musi być eulerowski?

2. Dla jakich n graf pełny K_n można przedstawić w postaci dwóch dopełniających się grafów
częściowych eulerowskich?

3. W grafie spójnym G, 2k wierzchołków ma stopień nieparzysty, a pozostałe wierzchołki są stopnia parzystego. Pokaż, że w G istnieje k krawędziowo rozłącznych dróg, które pokrywają wszystkie krawędzie G. (Rozkład grafu na tzw. drogi jednobieżne.)

Czy byłby w stanie ktoś mi pomóc z ich rozwiązaniem i wytłumaczeniem dlaczego tak jest?
z góry dzięki :)
Góra
 Tytuł: teoria grafów
PostNapisane: 25 paź 2015, o 14:38 
Użytkownik
1) 2|E(G)| =r(2r+1) skąd r musi być parzyste a więc G jest grafem eulerowskim.
Góra
Mężczyzna Offline
 Tytuł: teoria grafów
PostNapisane: 3 wrz 2016, o 17:01 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
2) W grafie, w którym istnieje cykl Eulera każdy wierzchołek ma parzysty stopień i jest to graf spójny. Dla n parzystego każdy wierzchołek ma stopień nieparzysty, wiec w pewnym z podgrafów ten wierzchołek musiałby występować w stopniu nieparzystym - sprzeczność.
Dla n = 3 widać, że się nie da.
Dla nieparzystego n \ge  5 bierzemy następujący podział: cykl Hamiltona tej kliki (kolejno wierzchołki 1, 2, 3, ..., n, 1 połączone krawędziami) i graf złożony z pozostałych krawędzi. Cykl Hamiltona ma wierzchołki parzystego stopnia, więc ten drugi graf też ma. Ten drugi graf jest spójny, bo ma drzewo rozpinające złożone ze wszystkich wierzchołków kliki - wierzchołek 1 jest połączony ze wszystkimi pozostałymi poza 2 i n, ale 2 jest połączone z n i n - 1 z 2.
Odpowiedź: nieparzyste n \ge  5.

3) Łączymy krawędziami specjalnymi pary wierzchołków nieparzystego stopnia. W tak utworzonym grafie każdy wierzchołek ma stopień parzysty, czyli jest cykl Eulera. Bierzemy ten cykl i usuwamy z niego te k krawędzi specjalnych. Dwie krawędzie specjalne nie mogą na tym cyklu być kolejnymi krawędziami, bo nie mają wspólnych wierzchołków. Po usunięciu krawędzi cykl rozpada się na k krawędziowo rozłącznych ścieżek, cnd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Teoria Grafów - zadanie 11  lukasz1143  1
 teoria grafów - zadanie 2  dusia17  4
 Teoria grafów - zadanie 3  flake  1
 Teoria grafów - zadanie 9  kiler69  2
 Teoria grafów - zadanie 16  Ewellka1312  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl