szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 lip 2015, o 17:47 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
3.1. Każde drzewo jest grafem dwudzielnym.
Weźmy dowolne drzewo. Weźmy najdłuższą drogę w tym drzewie. Zacznijmy kolorowanie wierzchołków od liścia.Kolorujemy kolejne wierzchołki na zmianę- gdy napotkamy wierzchołek stopnia \ge 2 to kontynujemy algorytm kolorowania. Wracając na najdłuższą drogę postępujemy identycznie aż dojdziemy do ostatniego wierzchołka naszej drogi. Żadne sąsiadujące wierzchołki nie są pokolorowane tym samym kolorem -otrzymujemy graf dwudzielny.
3.2. W każdym grafie spójnym o co najmniej 2 wierzchołkach istnieje wierzchołek u taki, że G–u jest spójny.
Weźmy dowolny graf spójny.
Gdy weźmiemy drzewo takim wierzchołkiem będzie dowolny liść (każde drzewo ma co najmniej 2 liście).
W grafie spójnym w którym \forall v \in V(G)\,deg(v) \ge 2 bierzemy dowolny wierzchołek należący do cyklu (z tw.o istnieniu cykl istnieje).
3.3. Graf G jest drzewem wtedy i tylko wtedy gdy istnieje takie uporządkowanie \{v_{1},...,v_{n}\} zbioru V(G), że dla każdego k>1 wierzchołek v_{k} ma dokładnie jednego sąsiada w zbiorze {v_{1},...,v_{k-1}}
" \Rightarrow "
[G] jest drzewem więc między każdym u,vistnieje dokładnie jedna droga. Każdy wierzchołek drogi oznaczmy kolejno numerem (u=v_{1},....,v=v_{k})
Z tego wynika,że każdy wierzchołek naszej drogi ma dokładnie jednego sąsiada w podanym zbiorze.
\Leftarrow
Spójność oczywista. Przypuśćmy,że G nie jest drzewem -istnieje więc cykl w grafie G. Ale założyliśmy, że w zbiorze \left\{ v_{1}.v_{2},...,v_{k-1}\right\} wierzchołek v_{k} ma 1 sąsiada. Sprzeczność z założeniem.
3.5. Spójny graf o n wierzchołkach i n krawędziach ma dokładnie jeden cykl.
Jak to "ładnie" pokazać?
3.6. Każde nietrywialne drzewo ma co najmniej dwa liście.
Nietrywialne drzewo - liczba wierzchołków \ge 2. Przypuśćmy, że drzewo ma 1 liść. Wtedy wszystkie pozostałe wierzchołki są stopnia \ge 2. Usuńmy tego liścia z grafu (usuwamy wierzchołek z jedną krawędzią więc go nie rozspójnimy) \Rightarrowspójny i deg(v) \ge 2 \Rightarrow istnieje cykl -sprzeczność,że rozpatrywaliśmy drzewo.
3.7. T jest drzewem rozpinającym spójnego grafu G wtedy i tylko gdy T jest minimalnym podgrafem spójnym w G.
\Rightarrow
Drzewo rozpinające to z definicji podgraf zawierający wszystkie wierzchołki
zaś zbiór krawędzi jest podzbiorem krawędzi wyjściowego grafu. Oznacza to,że jego krawędzie są jedynie te,które są niezbędne do spójności a to oznacza,że mamy minimalną wagę krawędzi(które są podzbiorem wyjściowego grafu)
\Rightarrow\ T jest podgrafem z minimalną wagą krawędzi \Rightarrow\ T jest minimalnym podgrafem.
\Leftarrow
T minimalny podgraf i spójny w G
minimalny podgraf oznacza,że nie ma w nim cykli i spójny\Rightarrowdrzewo, które jest minimalnym podgrafem \Rightarrow drzewo rozpinające
3.8. T jest drzewem rozpinającym spójnego grafu G wtedy i tylko gdy T jest maksymalnym podgrafem acyklicznym w G.
\Rightarrow
T jest drzewem więc jest grafem acyklicznym.Drzewo rozpajające zawiera wszystkie wierzchołki a dodając kolejny do drzewa spowodujemy pojawienie się cyklu, więc mamy maksymalny podgraf acykliczny w G
\Leftarrow
Maksymalny, więc zawiera wszystkie wierzchołki i acykliczny więc jest drzewem - dodanie kolejnego spowoduje pojawienie się cyklu - Tjest więc drzewem rozpinającym
3.9. Każdy acykliczny podzbiór zbioru krawędzi grafu spójnego można uzupełnić do zbioru
krawędzi drzewa rozpinającego.
Weźmy dowolny acykliczny podzbiór zbioru krawędzi grafu spójnego. Dodawajmy z każdym krokiem dowolną krawędź tak,by połączyć wszystkie wierzchołki. Otrzymamy drzewo rozpinające.
3.10. Każdy rozpinający, spójny podgraf grafu G zawiera drzewo rozpinające grafu G.
Weźmy dowolny spójny podgraf grafu GUsuńmy z niego krawędzie tworzące cykle. Otrzymujemy drzewo rozpinające grafu G.


Wszystkie zadania pisałem na szybko,proszę o wyrozumiałość i wskazanie rażących błędów - niedociągnięcia na pewno są ale miałem mało czasu na ich napisanie- chodzi raczej o ogólną ideę. Proszę o zerknięcie okiem.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 26 lip 2015, o 17:51 
Użytkownik

Posty: 491
Lokalizacja: Sucha/Wrocław
gardner napisał(a):
3.5. Spójny graf o n wierzchołkach i n krawędziach ma dokładnie jeden cykl.
Jak to "ładnie" pokazać?


Zauważ, że graf spójny o n wierzchołkach i n-1 krawędziach to drzewo. Co ci to daje?

PS: Staraj się pisać te zadania oddzielnie i oddzielaj treści do twoich rozwiązań/komentarzy. Strasznie się to czyta.
Góra
Mężczyzna Offline
PostNapisane: 26 lip 2015, o 18:45 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Ok,sprytne z tym drzewem :) Dzięki za wskazówkę. Co do sposobu pisania to postaram się następnym razem ładnie to zapisać.
Góra
Mężczyzna Offline
PostNapisane: 27 lip 2015, o 07:25 
Gość Specjalny

Posty: 3047
Lokalizacja: Gołąb
3.2
Nie do końca rozumiem to co napisałeś.
Weźmy drzewo rozpinające grafu (istnieje, bo graf jest spójny) i w nim liść (istnieje, bo każde drzewo ma przynajmniej 2 liście). Usuńmy ten wierzchołek. Graf się nie rozspójnił, bo gdyby się rozspójnił, rozspójniło by się również to drzewo rozpinające, a usunięcie liścia na pewno nie rozspójnia drzewa.
O to Ci chodziło?
3.3
\Leftarrow Drzewo jest grafem acyklicznym, a każdy graf acykliczny można posortować topologicznie, skąd wynika teza.
Dlaczego spójność jest oczywista? Bez uzasadnienia nie jest. To że każdy wierzchołek ma sąsiada nie oznacza że graf jest spójny. Można na przykład indukcyjnie udowodnić, że istnieje droga między v_{1} a dowolnym innym wierzchołkiem.
3.6
Wynika to wprost z lematu o uściskach dłoni.
3.7
Załóżmy, że jest podgraf spójny mnniejszy (tzn. mający mniej krawędzi) niż drzewo rozpinające. Wynika stąd że jest on niespójny.
Cytuj:
minimalny podgraf oznacza,że nie ma w nim cykli

Uzasadnienie? To oczywiste, ale wypada dbać o takie rzeczy.
3.8
Cytuj:
Drzewo rozpajające zawiera wszystkie wierzchołki a dodając kolejny do drzewa spowodujemy pojawienie się cyklu ,więc mamy maksymalny podgraf acykliczny w G

Chodziło o dodanie krawędzi? Bo argument dodanie kolejnego wierzchołka powoduje powstanie cyklu jest niedorzeczny.
3.9
To co napisałeś brzmi jak oczywistość, ale niestety nie można tego nazwać matematycznym dowodem.

Podsumowując, widać, że mniej więcej to ogarniasz, ale formalizmu brakuje okropnie. Bo niestety zdania pokroju "Teza zachodzi, ponieważ jest prawdziwa" w matematyce ani o milimetr nie przesuwają w stronę dowodu i racjonalnego uzasadnienia.
Góra
Mężczyzna Offline
PostNapisane: 27 lip 2015, o 16:10 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
bakala12 napisał(a):
3.2
Nie do końca rozumiem to co napisałeś.
Weźmy drzewo rozpinające grafu (istnieje, bo graf jest spójny) i w nim liść (istnieje, bo każde drzewo ma przynajmniej 2 liście). Usuńmy ten wierzchołek. Graf się nie rozspójnił, bo gdyby się rozspójnił, rozspójniło by się również to drzewo rozpinające, a usunięcie liścia na pewno nie rozspójnia drzewa.
O to Ci chodziło?

Podałem raczej różne przypadki grafu i wyjaśniłem co w każdym zachodzi-Twój tok rozumowania jest lepszy.

bakala12 napisał(a):
3.7
Załóżmy, że jest podgraf spójny mnniejszy (tzn. mający mniej krawędzi) niż drzewo rozpinające. Wynika stąd że jest on niespójny.
Cytuj:
minimalny podgraf oznacza,że nie ma w nim cykli

Uzasadnienie? To oczywiste, ale wypada dbać o takie rzeczy.

Można napisać,że każdy minimalny podgraf jest drzewem?
bakala12 napisał(a):
3.8
Cytuj:
Drzewo rozpajające zawiera wszystkie wierzchołki a dodając kolejny do drzewa spowodujemy pojawienie się cyklu ,więc mamy maksymalny podgraf acykliczny w G

Chodziło o dodanie krawędzi? Bo argument dodanie kolejnego wierzchołka powoduje powstanie cyklu jest niedorzeczny.

Tak,napisałem z rozpędu taką głupotę.
bakala12 napisał(a):
3.9
To co napisałeś brzmi jak oczywistość, ale niestety nie można tego nazwać matematycznym dowodem.

Hmm zastanowię się nad tym dowodem jeszcze.
bakala12 napisał(a):
Podsumowując, widać, że mniej więcej to ogarniasz, ale formalizmu brakuje okropnie. Bo niestety zdania pokroju "Teza zachodzi, ponieważ jest prawdziwa" w matematyce ani o milimetr nie przesuwają w stronę dowodu i racjonalnego uzasadnienia.


Muszę właśnie nad tym formalizmem popracować. Co najlepiej wyrobi we mnie taką intuicję matematyczną? Czytanie dowodów? Postaram się kolejny zestaw zrobić najformalniej jak umiem. Dzięki za pomoc.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 dziwne zadanie z matematyki dyskretnej  mkarwin  1
 takze dziwne zadanie z matematyki dyskretnej  mkarwin  5
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl