szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 sie 2018, o 14:01 
Użytkownik

Posty: 49
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!
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Na przyjęciu jest 19 osób, gdzie każdy ma min. 10 znajomych  Stefaniak1916  3
 Graf petersena  Ceplusplusik  1
 Niespójny graf Eulera  mis02  2
 Kolorówanie - graf dopełniony i zwykły  matinf  5
 Teoria grafów, graf EULERA  flexii  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl