szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 lut 2017, o 16:55 
Użytkownik

Posty: 246
Lokalizacja: Zamość
Witam,
Dostałem kilka zadań, których odpowiedzi i ich uzasadnień nie jestem pewien.

1. Niech dany będzie nieskierowany spójny graf G. Okazało się, że po usunięciu jednej krawędzi e z grafu G graf pozostał nadal spójny. Co można powiedzieć o krawędzi e. Odpowiedź uzasadnij.

No i tutaj nie wiem, patrzyłem po definicjach ze skryptu i jedyne co to może, że krawędź e jest rozcięciem? Natomiast pewności nie mam...

2.Udowodnić, że jeśli graf G= (V,E) jest grafem spójnym i |E|<|V|, toGzawiera 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 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 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 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 t=\left( m-1\right)p +1niezależ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 n ^{n-2}. Na zajęciach otrzymałem taki dowód tego:
Każdemu drzewu oznakowanemu o n wierzchołkach odpowiada dokładnie 1 kod Pruffera, a każdy kod Pruffera można rozważać jako n-2 elementową wariację z powtórzeniami ze zbioru n elementowego, daną wzorem n^{n-2}.


Naprawdę z góry dziękuję za pomoc na tym forum, wiele mi to pomaga.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 lut 2017, o 22:11 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
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 |E| < |V| (dokładnie |E| = |V| - 1), w takim drzewie zawsze są min. 2 liście, czyli wierzchołki stopnia 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.
Góra
Mężczyzna Offline
PostNapisane: 3 lut 2017, o 22:42 
Użytkownik

Posty: 246
Lokalizacja: Zamość
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 \left( v,w\right) jest krawędzią, to v nazywamy rodzicem lub przodkiem, a 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
Góra
Mężczyzna Offline
PostNapisane: 4 lut 2017, o 00:55 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
6. Ok, już rozumiem.
Przez liczbę rozgałęzień wierzchołka rozumiemy stopień wychodzący wierzchołka będącego rodzicem.
W takim razie 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 p wierzchołków będących rodzicami ma stopień m.
|V| = t  + p (każdy wierzchołek to liść lub rodzic).
|E| = mp
W drzewie: |V| = |E| + 1, czyli t + p = mp + 1, t = (m - 1)p + 1, cnd.
Góra
Mężczyzna Offline
PostNapisane: 4 lut 2017, o 14:36 
Użytkownik

Posty: 246
Lokalizacja: Zamość
Dziękuję bardzo.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Grafy Hamiltonowski i Eulerowski  devonsix  1
 pętla i kilka zadan  rohrl  1
 Grafy-cykl Hamiltona  Anonymous  6
 Kilka zadań. Kombinatoryka .  jigaboo  2
 Znajdź wszystkie grafy  netsprint  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl