Witam,
Dostałem kilka zadań, których odpowiedzi i ich uzasadnień nie jestem pewien.
1. Niech dany będzie nieskierowany spójny graf \(\displaystyle{ G}\). Okazało się, że po usunięciu jednej krawędzi \(\displaystyle{ e}\) z grafu \(\displaystyle{ G}\) graf pozostał nadal spójny. Co można powiedzieć o krawędzi \(\displaystyle{ e}\). Odpowiedź uzasadnij.
No i tutaj nie wiem, patrzyłem po definicjach ze skryptu i jedyne co to może, że krawędź \(\displaystyle{ e}\) jest rozcięciem? Natomiast pewności nie mam...
2.Udowodnić, że jeśli graf \(\displaystyle{ G= (V,E)}\) jest grafem spójnym i \(\displaystyle{ |E|<|V|}\), to\(\displaystyle{ G}\)zawiera co najmniej dwa wierzchołki stopnia pierwszego...
Tutaj co? Powoływać się na jakiś lemat o uściskach dłoni? Czy są po prostu jakieś własności grafu spójnego o których ja nie wiem..
3.Które grafy pełne maja cykle Eulera? Odpowiedz uzasadnij.
Tutaj zauważyłem, że cykle Eulera posiadają tylko grafy pełne gdy \(\displaystyle{ n}\) - liczba wierzchołków jest nieparzysta, bo z własności grafów pełnych stopnie wierzchołków grafów pełnych wynosi \(\displaystyle{ n-1}\), a z tw. o cyklu Eulera wiemy, że stopień każdego wierzchołka musi być parzysty aby istniał cykl Eulera.
4.Które z grafów platońskich posiadają cykl Eulera, a które cykl Hamiltona. Odpowiedz uzasadnij.
Tutaj nie zauważyłem jakiegoś "schematu" na istnienie tych cykli, aczkolwiek pojedynczo wiem jak to sprawdzić. Istnieje pewien schemat na to?
5.Ile krawędzi ma n wierzchołkowy graf spójny i acykliczny. Odpowiedz uzasadnij.
Graf spójny i acykliczny to drzewo, a z własności drzewa mamy, że drzewo posiada \(\displaystyle{ n-1}\) krawędzi. Wystarcza to?
6.Udowodnij, ze jeśli t jest liczba liści, a p liczba rodziców w drzewie pełnym o m rozgałęzieniach, to \(\displaystyle{ t=\left( m-1\right)p +1}\)niezależnie od wysokości drzewa
Tutaj 0 pojęcia, totalnie nic..
7. Ile można zbudować n-wierzchołkowych drzew oznakowanych. Odpowiedz uzasadnij.
Można zbudować takich drzew \(\displaystyle{ n ^{n-2}}\). Na zajęciach otrzymałem taki dowód tego:
Każdemu drzewu oznakowanemu o \(\displaystyle{ n}\) wierzchołkach odpowiada dokładnie 1 kod Pruffera, a każdy kod Pruffera można rozważać jako \(\displaystyle{ n-2}\) elementową wariację z powtórzeniami ze zbioru \(\displaystyle{ n}\) elementowego, daną wzorem \(\displaystyle{ n^{n-2}}\).
Naprawdę z góry dziękuję za pomoc na tym forum, wiele mi to pomaga.
Grafy - kilka uzasadnień.
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Grafy - kilka uzasadnień.
1. Ta krawędź nie jest mostem (krawędzią rozcinającą).
2. Stopnia pierwszego?? Raczej chyba chodziło o stopień równy jeden. Jeżeli graf składa się tylko z jednego wierzchołka to warunki są spełnione, ale nie ma wierzchołków o stopniu jeden, więc treść nie jest do końca poprawna. Rozpatrując grafy składające się z przynajmniej dwóch wierzchołków treść już jest ok - drzewo jest jedynym spójnym grafem w którym \(\displaystyle{ |E| < |V|}\) (dokładnie \(\displaystyle{ |E| = |V| - 1}\)), w takim drzewie zawsze są min. \(\displaystyle{ 2}\) liście, czyli wierzchołki stopnia \(\displaystyle{ 1}\) (można to np. udowodnić indukcyjnie).
3. Ok.
4. Grafy platońskie są regularne - każdy wierzchołek ma ten sam stopień - łatwo sprawdzić czy jest cykl Eulera. Cykl Hamiltona można sprawdzić ręcznie.
5. Tak.
6. Tutaj wykładowca wprowadza jakieś chyba tylko sobie znane pojęcia rozgałęzienia i rodzica...
7. Ok. To jest twierdzenie Cayley'a.
2. Stopnia pierwszego?? Raczej chyba chodziło o stopień równy jeden. Jeżeli graf składa się tylko z jednego wierzchołka to warunki są spełnione, ale nie ma wierzchołków o stopniu jeden, więc treść nie jest do końca poprawna. Rozpatrując grafy składające się z przynajmniej dwóch wierzchołków treść już jest ok - drzewo jest jedynym spójnym grafem w którym \(\displaystyle{ |E| < |V|}\) (dokładnie \(\displaystyle{ |E| = |V| - 1}\)), w takim drzewie zawsze są min. \(\displaystyle{ 2}\) liście, czyli wierzchołki stopnia \(\displaystyle{ 1}\) (można to np. udowodnić indukcyjnie).
3. Ok.
4. Grafy platońskie są regularne - każdy wierzchołek ma ten sam stopień - łatwo sprawdzić czy jest cykl Eulera. Cykl Hamiltona można sprawdzić ręcznie.
5. Tak.
6. Tutaj wykładowca wprowadza jakieś chyba tylko sobie znane pojęcia rozgałęzienia i rodzica...
7. Ok. To jest twierdzenie Cayley'a.
-
karpiuch
- Użytkownik
- Posty: 249
- Rejestracja: 18 maja 2013, o 22:20
- Płeć: Mężczyzna
- Lokalizacja: Zamość
- Podziękował: 29 razy
- Pomógł: 3 razy
Grafy - kilka uzasadnień.
Tak definiuje wykładowca rzeczy z zadania 6.
Drzewo, w którym wyróżniono jeden z wierzchołków nazywamy drzewem z wyróżnionym korzeniem, a ten wyróżniony wierzchołek nazywa się korzeniem. Drzewo z wyróżnionym korzeniem, w którym oprócz korzenia i liści pozostałe wierzchołki mają stopień równy trzy nazywa się drzewem przeszukiwań binarnych.
Drzewo z wyróżnionym korzeniem jako graf skierowany ma następujące własności:
- liście są wierzchołkami nie będącymi początkiem żadnej krawędzi,
- korzeń jest wierzchołkiem nie będącym końcem żadnej krawędzi,
- jeśli \(\displaystyle{ \left( v,w\right)}\) jest krawędzią, to \(\displaystyle{ v}\) nazywamy rodzicem lub przodkiem, a \(\displaystyle{ w}\) nazywamy dzieckiem lub potomkiem,
- każdy wierzchołek poza korzeniem ma jednego rodzica,
- każdy rodzic może mieć kilkoro dzieci, a w drzewie przeszukiwań binarnych co najwyżej dwoje
Drzewo, w którym wyróżniono jeden z wierzchołków nazywamy drzewem z wyróżnionym korzeniem, a ten wyróżniony wierzchołek nazywa się korzeniem. Drzewo z wyróżnionym korzeniem, w którym oprócz korzenia i liści pozostałe wierzchołki mają stopień równy trzy nazywa się drzewem przeszukiwań binarnych.
Drzewo z wyróżnionym korzeniem jako graf skierowany ma następujące własności:
- liście są wierzchołkami nie będącymi początkiem żadnej krawędzi,
- korzeń jest wierzchołkiem nie będącym końcem żadnej krawędzi,
- jeśli \(\displaystyle{ \left( v,w\right)}\) jest krawędzią, to \(\displaystyle{ v}\) nazywamy rodzicem lub przodkiem, a \(\displaystyle{ w}\) nazywamy dzieckiem lub potomkiem,
- każdy wierzchołek poza korzeniem ma jednego rodzica,
- każdy rodzic może mieć kilkoro dzieci, a w drzewie przeszukiwań binarnych co najwyżej dwoje
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Grafy - kilka uzasadnień.
6. Ok, już rozumiem.
Przez liczbę rozgałęzień wierzchołka rozumiemy stopień wychodzący wierzchołka będącego rodzicem.
W takim razie \(\displaystyle{ mp}\) to liczba wszystkich krawędzi w drzewie, bo liczba krawędzi to suma stopni wychodzących (każda krawędź skądś wychodzi), a każdy z \(\displaystyle{ p}\) wierzchołków będących rodzicami ma stopień \(\displaystyle{ m}\).
\(\displaystyle{ |V| = t + p}\) (każdy wierzchołek to liść lub rodzic).
\(\displaystyle{ |E| = mp}\)
W drzewie: \(\displaystyle{ |V| = |E| + 1}\), czyli \(\displaystyle{ t + p = mp + 1}\), \(\displaystyle{ t = (m - 1)p + 1}\), cnd.
Przez liczbę rozgałęzień wierzchołka rozumiemy stopień wychodzący wierzchołka będącego rodzicem.
W takim razie \(\displaystyle{ mp}\) to liczba wszystkich krawędzi w drzewie, bo liczba krawędzi to suma stopni wychodzących (każda krawędź skądś wychodzi), a każdy z \(\displaystyle{ p}\) wierzchołków będących rodzicami ma stopień \(\displaystyle{ m}\).
\(\displaystyle{ |V| = t + p}\) (każdy wierzchołek to liść lub rodzic).
\(\displaystyle{ |E| = mp}\)
W drzewie: \(\displaystyle{ |V| = |E| + 1}\), czyli \(\displaystyle{ t + p = mp + 1}\), \(\displaystyle{ t = (m - 1)p + 1}\), cnd.