szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Online
PostNapisane: 7 sie 2018, o 13:01 
Użytkownik

Posty: 53
Lokalizacja: Warszawa
Cześć.
Mam takie zadanie
Niech G=(V,E) będzie grafem, w którym E \neq \emptyset i w którym każdy wierzchołek ma parzysty stopień.
1)Rozważając nietrywialne składowe pokzać że G ma cykl.
2) Pokazać również że jeśli usuniemy z grafu krawędzie należące do tego cyklu to w nowym grafie każdy wierzchołek w dalszym ciągu ma parzysty stopień.
3)Wywnioskować, że w G istnieje zbiór cykli zawierający każdą krawędź z E dokładnie jeden raz.

Chciałbym poprosić kogoś o sprawdzenie mojej próby zrobienia tego zadania i może podzielenie się swoim pomysłem.

1)G ma nietrywialną składową z założenia niepustości E. Nazwijmy ją G'=(V',E') gdzie V'=(v1,v2,...,vn). Weźmy dowolny wierzchołekvi _{1} gdzie i_{1}  \in \left\{1,2,...,n \right\}. Wiemy że v1 ma stopień niezerowy a więc dobierzmy dowolny wierzchołek który jest jego sąsiadem i oznaczmy go v2. Ponieważ v2 ma stopień parzysty to istnieje inny od v1 wierzchołek któr również jest sąsiadem v2 i oznaczymy go v3. Będziemy powtarzać ten proces aż natrafimy na wierzchołek (na pewno tak się zdarzy ponieważ liczba wierzchołków jest skończona) vi_{k} gdzie i_{k}  \in \left\{1,2,...,n \right\} który pojawił się już wcześniej w naszym ciągu vj \in (v1,v2,v3,...,v(k-1))  \wedge 
 vj=vk. Mamy cykl vjv(j+1)v(j+2)...v(k-1)vk.

2) Po usunięciu krawędzi należących do naszego cyklu suma stopni przy każdym wierzchołku który należy do naszego cyklu zmniejszy się o dwa, a więc ich parzystość nie ulegnie zmianie. (Nie umiem w sumie tego uzasadnić dlaczego akurat o dwa ale wydaje się dość oczywiste)

3)Oznaczmy cykl C_{1} który w znaleźliśmy w naszym grafie G i usuńmy go, a a nasz graf bez cyklu oznaczmy G'. Ponieważ suma stopni w G jest dalej parzysta (wynika to bezpośrednio z 2)) to istnieje w nim cykl oznaczmy go C_{2} i usuńmy go. Powtarzając ten proces usuwając kolejne cykle C_{i} (liczba ich jest skończona ponieważ liczba krawędzi jest skończona) dojdziemy do momentu w którym otrzymamy graf pusty bez cykli. A zbiór \left\{C_{1},C_{2},...,C_{m} \right\} będzie zbiorem cykli zawierających każdą krawędź dokładnie raz.


Najbardziej mi zależy na podpunkcie 1) i jego zgrabnym zapisaniu. Proszę o porady!
Góra
Mężczyzna Offline
PostNapisane: 16 paź 2018, o 18:40 
Użytkownik
Avatar użytkownika

Posty: 3489
Lokalizacja: blisko
Tak w skrócie do 1

Weźmy:

v_{0} - dowolny wierzchołek grafu.
Twórzmy drogę D, dopóki D nie jest cyklem robimy:

niech.: v_{i}

będzie sąsiadem .: v_{i-1}

wybór jest możliwy ponieważ:

deg(v_{i-1}) \ge 2

jeśli v_{i} - jest wierzchołkiem należącym do drogi.: v_{i−1}, ..., v_{0}
to droga D zawiera cykl.

jeśli nie to:

v_{i}

dołączamy do drogi.: v_{i},v_{i−1}, ..., v_{0}

takie pierdu, pierdu...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 czy istnieje graf o stopniach wierzchołków  anilahcim  2
 graf prosty - zadanie 2  olkab  5
 Ile drzew spinających ma graf  De Moon  3
 Graf doskonaly.  RobiMethod  1
 graf dwudzielny  kamil.jack  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl