Zadania z matematyki dyskretnej do sprawdzenia #3

[gardner]

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 \(\displaystyle{ \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 \(\displaystyle{ 2}\) wierzchołkach istnieje wierzchołek \(\displaystyle{ u}\) taki, że \(\displaystyle{ 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 \(\displaystyle{ 2}\) liście).
W grafie spójnym w którym \(\displaystyle{ \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 \(\displaystyle{ G}\) jest drzewem wtedy i tylko wtedy gdy istnieje takie uporządkowanie \(\displaystyle{ \{v_{1},...,v_{n}\}}\) zbioru \(\displaystyle{ V(G)}\), że dla każdego \(\displaystyle{ k>1}\) wierzchołek \(\displaystyle{ v_{k}}\) ma dokładnie jednego sąsiada w zbiorze \(\displaystyle{ {v_{1},...,v_{k-1}}}\)
\(\displaystyle{ " \Rightarrow "}\)
\(\displaystyle{ [G]}\) jest drzewem więc między każdym \(\displaystyle{ u,v}\)istnieje dokładnie jedna droga. Każdy wierzchołek drogi oznaczmy kolejno numerem \(\displaystyle{ (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.
\(\displaystyle{ \Leftarrow}\)
Spójność oczywista. Przypuśćmy,że \(\displaystyle{ G}\) nie jest drzewem -istnieje więc cykl w grafie \(\displaystyle{ G}\). Ale założyliśmy, że w zbiorze \(\displaystyle{ \left\{ v_{1}.v_{2},...,v_{k-1}\right\}}\) wierzchołek \(\displaystyle{ v_{k}}\) ma \(\displaystyle{ 1}\) sąsiada. Sprzeczność z założeniem.
3.5. Spójny graf o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ 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 \(\displaystyle{ \ge 2}\). Przypuśćmy, że drzewo ma \(\displaystyle{ 1}\) liść. Wtedy wszystkie pozostałe wierzchołki są stopnia \(\displaystyle{ \ge 2}\). Usuńmy tego liścia z grafu (usuwamy wierzchołek z jedną krawędzią więc go nie rozspójnimy) \(\displaystyle{ \Rightarrow}\)spójny i \(\displaystyle{ deg(v) \ge 2 \Rightarrow}\) istnieje cykl -sprzeczność,że rozpatrywaliśmy drzewo.
3.7. \(\displaystyle{ T}\) jest drzewem rozpinającym spójnego grafu \(\displaystyle{ G}\) wtedy i tylko gdy \(\displaystyle{ T}\) jest minimalnym podgrafem spójnym w \(\displaystyle{ G}\).
\(\displaystyle{ \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)
\(\displaystyle{ \Rightarrow\ T}\) jest podgrafem z minimalną wagą krawędzi \(\displaystyle{ \Rightarrow\ T}\) jest minimalnym podgrafem.
\(\displaystyle{ \Leftarrow}\)
\(\displaystyle{ T}\) minimalny podgraf i spójny w \(\displaystyle{ G}\)
minimalny podgraf oznacza,że nie ma w nim cykli i spójny\(\displaystyle{ \Rightarrow}\)drzewo, które jest minimalnym podgrafem \(\displaystyle{ \Rightarrow}\) drzewo rozpinające
3.8. \(\displaystyle{ T}\) jest drzewem rozpinającym spójnego grafu \(\displaystyle{ G}\) wtedy i tylko gdy \(\displaystyle{ T}\) jest maksymalnym podgrafem acyklicznym w \(\displaystyle{ G}\).
\(\displaystyle{ \Rightarrow}\)
\(\displaystyle{ 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 \(\displaystyle{ G}\)
\(\displaystyle{ \Leftarrow}\)
Maksymalny, więc zawiera wszystkie wierzchołki i acykliczny więc jest drzewem - dodanie kolejnego spowoduje pojawienie się cyklu - \(\displaystyle{ T}\)jest 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 \(\displaystyle{ G}\) zawiera drzewo rozpinające grafu \(\displaystyle{ G}\).
Weźmy dowolny spójny podgraf grafu \(\displaystyle{ G}\)Usuńmy z niego krawędzie tworzące cykle. Otrzymujemy drzewo rozpinające grafu \(\displaystyle{ 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.

[wiedzmac]

3.5. Spójny graf o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ n}\) krawędziach ma dokładnie jeden cykl.
Jak to "ładnie" pokazać?

Zauważ, że graf spójny o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ 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.

[gardner]

Ok,sprytne z tym drzewem Dzięki za wskazówkę. Co do sposobu pisania to postaram się następnym razem ładnie to zapisać.

[bakala12]

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 \(\displaystyle{ 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
\(\displaystyle{ \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 \(\displaystyle{ 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.

minimalny podgraf oznacza,że nie ma w nim cykli

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

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.

[gardner]

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 \(\displaystyle{ 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.

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.

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?

3.8

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ę.

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.

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.