Witam
Mam problem z trzema zadaniami:
1. Czy graf regularny stopnia \(\displaystyle{ r}\) mający \(\displaystyle{ 2r + 1}\) wierzchołków musi być eulerowski?
2. Dla jakich \(\displaystyle{ n}\) graf pełny \(\displaystyle{ K_n}\) można przedstawić w postaci dwóch dopełniających się grafów
częściowych eulerowskich?
3. W grafie spójnym \(\displaystyle{ G, 2k}\) wierzchołków ma stopień nieparzysty, a pozostałe wierzchołki są stopnia parzystego. Pokaż, że w \(\displaystyle{ G}\) istnieje \(\displaystyle{ k}\) krawędziowo rozłącznych dróg, które pokrywają wszystkie krawędzie \(\displaystyle{ 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
teoria grafów
-
paulina95
- Użytkownik
- Posty: 25
- Rejestracja: 4 kwie 2015, o 12:26
- Płeć: Kobieta
- Lokalizacja: katowice
- Podziękował: 3 razy
teoria grafów
Ostatnio zmieniony 25 paź 2015, o 15:04 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
kicaj
teoria grafów
1) \(\displaystyle{ 2|E(G)| =r(2r+1)}\) skąd \(\displaystyle{ r}\) musi być parzyste a więc \(\displaystyle{ G}\) jest grafem eulerowskim.
-
Mruczek
- Użytkownik
- Posty: 1113
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
teoria grafów
2) W grafie, w którym istnieje cykl Eulera każdy wierzchołek ma parzysty stopień i jest to graf spójny. Dla \(\displaystyle{ 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 \(\displaystyle{ n = 3}\) widać, że się nie da.
Dla nieparzystego \(\displaystyle{ 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 \(\displaystyle{ 1}\) jest połączony ze wszystkimi pozostałymi poza \(\displaystyle{ 2}\) i \(\displaystyle{ n}\), ale \(\displaystyle{ 2}\) jest połączone z \(\displaystyle{ n}\) i \(\displaystyle{ n - 1}\) z \(\displaystyle{ 2}\).
Odpowiedź: nieparzyste \(\displaystyle{ 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 \(\displaystyle{ 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 \(\displaystyle{ k}\) krawędziowo rozłącznych ścieżek, cnd.
Dla \(\displaystyle{ n = 3}\) widać, że się nie da.
Dla nieparzystego \(\displaystyle{ 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 \(\displaystyle{ 1}\) jest połączony ze wszystkimi pozostałymi poza \(\displaystyle{ 2}\) i \(\displaystyle{ n}\), ale \(\displaystyle{ 2}\) jest połączone z \(\displaystyle{ n}\) i \(\displaystyle{ n - 1}\) z \(\displaystyle{ 2}\).
Odpowiedź: nieparzyste \(\displaystyle{ 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 \(\displaystyle{ 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 \(\displaystyle{ k}\) krawędziowo rozłącznych ścieżek, cnd.