Graf z wierzchołkami k-razy połączonymi krawędziami.
-
- Użytkownik
- Posty: 12
- Rejestracja: 9 kwie 2013, o 15:23
- Płeć: Mężczyzna
- Lokalizacja: Infernus
- Podziękował: 1 raz
Graf z wierzchołkami k-razy połączonymi krawędziami.
Witam.
Nie mam zupełnie pomysłu na następujące zadanie. Byłbym wdzięczny za pomoc.
Zadanie 1.
Niech \(\displaystyle{ G}\) będzie grafem prostym, a \(\displaystyle{ H}\) grafem, w którym każde dwa wierzchołki przyległe w \(\displaystyle{ G}\) są połączone dokładnie \(\displaystyle{ k}\) krawędziami. Pokaż, że:
\(\displaystyle{ \tau(H) = k^{\nu-1}\tau(G)}\).
----
edit:
I jeszcze jedno:
Zadanie 2.
Pokaż, że:
\(\displaystyle{ \tau(K_{2,n}) = n2^{n-1}}\).
Wykorzystać należy zadanie 1. oraz następujące twierdzenie:
Niech graf \(\displaystyle{ H}\) będzie grafem otrzymanym z grafu \(\displaystyle{ G}\) bez pętli przez zastąpienie każdej krawędzi z \(\displaystyle{ G}\) ścieżką o długości \(\displaystyle{ k}\). Wtedy:
\(\displaystyle{ \tau(H) = k^{\varepsilon - \nu+1}\tau(G)}\).
Wyjaśnię jeszcze oznaczenia bo nie wiem na ile one są standardowe:
\(\displaystyle{ \tau(X)}\) - ilość drzew rozpiętych w grafie \(\displaystyle{ X}\)
\(\displaystyle{ \nu}\) - ilość wierzchołków w grafie
\(\displaystyle{ \varepsilon}\) - ilość krawędzi w grafie
\(\displaystyle{ K_{m,n}}\) - graf pełny dwudzielny z dwupodziałem \(\displaystyle{ (X,Y)}\), gdzie \(\displaystyle{ |X| = m}\), \(\displaystyle{ |Y| = n}\).
Dzięki.
Nie mam zupełnie pomysłu na następujące zadanie. Byłbym wdzięczny za pomoc.
Zadanie 1.
Niech \(\displaystyle{ G}\) będzie grafem prostym, a \(\displaystyle{ H}\) grafem, w którym każde dwa wierzchołki przyległe w \(\displaystyle{ G}\) są połączone dokładnie \(\displaystyle{ k}\) krawędziami. Pokaż, że:
\(\displaystyle{ \tau(H) = k^{\nu-1}\tau(G)}\).
----
edit:
I jeszcze jedno:
Zadanie 2.
Pokaż, że:
\(\displaystyle{ \tau(K_{2,n}) = n2^{n-1}}\).
Wykorzystać należy zadanie 1. oraz następujące twierdzenie:
Niech graf \(\displaystyle{ H}\) będzie grafem otrzymanym z grafu \(\displaystyle{ G}\) bez pętli przez zastąpienie każdej krawędzi z \(\displaystyle{ G}\) ścieżką o długości \(\displaystyle{ k}\). Wtedy:
\(\displaystyle{ \tau(H) = k^{\varepsilon - \nu+1}\tau(G)}\).
Wyjaśnię jeszcze oznaczenia bo nie wiem na ile one są standardowe:
\(\displaystyle{ \tau(X)}\) - ilość drzew rozpiętych w grafie \(\displaystyle{ X}\)
\(\displaystyle{ \nu}\) - ilość wierzchołków w grafie
\(\displaystyle{ \varepsilon}\) - ilość krawędzi w grafie
\(\displaystyle{ K_{m,n}}\) - graf pełny dwudzielny z dwupodziałem \(\displaystyle{ (X,Y)}\), gdzie \(\displaystyle{ |X| = m}\), \(\displaystyle{ |Y| = n}\).
Dzięki.
Ostatnio zmieniony 11 kwie 2013, o 11:40 przez Summum Malum, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
-
- Użytkownik
- Posty: 12
- Rejestracja: 9 kwie 2013, o 15:23
- Płeć: Mężczyzna
- Lokalizacja: Infernus
- Podziękował: 1 raz
Graf z wierzchołkami k-razy połączonymi krawędziami.
Kartezjusz pisze:Ja rozumieć kąty przyległe w grafie?
Kąty przyległe w grafie? Nie mam pojęcia, ale ja nic nie pisałem o kątach przyległych.
Wierzchołki przyległe to za to wierzchołki połączone tę samą krawędzią, tzn są incydentne z tą samą krawędzią.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Graf z wierzchołkami k-razy połączonymi krawędziami.
1.Ponumeruj krawędzie wyrastające z każdego wierzchołka liczbami od 1 do k. Dla każdego wierzchołka z\(\displaystyle{ G}\) dobierz krawędź z \(\displaystyle{ H}\),która z niego wyrasta. Z ostatniego nic nie wyrasta,więc możesz pominąć,a że numery kolejnych krawędzi mogą się powtarzać jest to kombinacja z powtórzeniami i stąd mamy tezę
-
- Użytkownik
- Posty: 12
- Rejestracja: 9 kwie 2013, o 15:23
- Płeć: Mężczyzna
- Lokalizacja: Infernus
- Podziękował: 1 raz
Graf z wierzchołkami k-razy połączonymi krawędziami.
Dzięki, ale...
Jak dla mnie to dowodzi, że mamy \(\displaystyle{ k^{\nu -1}}\) możliwości wybrania grafu \(\displaystyle{ G_i}\) z grafu \(\displaystyle{ H}\). Dla grafu \(\displaystyle{ G_i}\) mamy \(\displaystyle{ \tau (G_i)}\) drzew rozpinających. Skąd pewność, że żadne drzewo rozpinające z grafu \(\displaystyle{ \tau (G_i)}\) nie powtarza się z jakimś drzewem rozpinającym z grafu \(\displaystyle{ \tau (G_j)}\).
I co z drugim zadanie.
Jak dla mnie to dowodzi, że mamy \(\displaystyle{ k^{\nu -1}}\) możliwości wybrania grafu \(\displaystyle{ G_i}\) z grafu \(\displaystyle{ H}\). Dla grafu \(\displaystyle{ G_i}\) mamy \(\displaystyle{ \tau (G_i)}\) drzew rozpinających. Skąd pewność, że żadne drzewo rozpinające z grafu \(\displaystyle{ \tau (G_i)}\) nie powtarza się z jakimś drzewem rozpinającym z grafu \(\displaystyle{ \tau (G_j)}\).
I co z drugim zadanie.
Ostatnio zmieniony 11 kwie 2013, o 12:23 przez Summum Malum, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Graf z wierzchołkami k-razy połączonymi krawędziami.
A z każdego wyboru grafu \(\displaystyle{ G}\) można wyjąć \(\displaystyle{ \tau (G)}\)drzew
-
- Użytkownik
- Posty: 12
- Rejestracja: 9 kwie 2013, o 15:23
- Płeć: Mężczyzna
- Lokalizacja: Infernus
- Podziękował: 1 raz
Graf z wierzchołkami k-razy połączonymi krawędziami.
Kartezjusz pisze:A z każdego wyboru grafu \(\displaystyle{ G}\) można wyjąć \(\displaystyle{ \tau (G)}\)drzew
Doszedłem do tego zanim to przeczytałem. Poprzedni post edytowałem chyba z 10 razy, za każdym razem uzmysławiając sobie kolejną rzecz. Ale nadal nie widzę dlaczego drzewa rozpinających grafów prostych nie mogą się powtarzać i co z kolejnym zadaniem.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Graf z wierzchołkami k-razy połączonymi krawędziami.
Bo jak grafy są równe,to zbiory krawędzi i wierzchołków będą takie same,a my dobieramy za każdym razem nowy zbiór krawędzi.
-
- Użytkownik
- Posty: 12
- Rejestracja: 9 kwie 2013, o 15:23
- Płeć: Mężczyzna
- Lokalizacja: Infernus
- Podziękował: 1 raz
Graf z wierzchołkami k-razy połączonymi krawędziami.
Ale wybierzmy graf \(\displaystyle{ G_i}\) różniący się tylko jedną krawędzią od grafu \(\displaystyle{ G_j}\). Dlaczego nie jesteśmy w stanie wybrać z grafu \(\displaystyle{ G_i}\) i \(\displaystyle{ G_j}\) dokładnie takiego samego drzewa rozpinającego.Kartezjusz pisze:Bo jak grafy są równe,to zbiory krawędzi i wierzchołków będą takie same,a my dobieramy za każdym razem nowy zbiór krawędzi.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Graf z wierzchołkami k-razy połączonymi krawędziami.
Myślę,że chodzi tu o drzewa pełne. CZyli \(\displaystyle{ v}\) -wierzchołkowe.
-
- Użytkownik
- Posty: 12
- Rejestracja: 9 kwie 2013, o 15:23
- Płeć: Mężczyzna
- Lokalizacja: Infernus
- Podziękował: 1 raz
Graf z wierzchołkami k-razy połączonymi krawędziami.
Kartezjusz pisze:Myślę,że chodzi tu o drzewa pełne. CZyli \(\displaystyle{ v}\) -wierzchołkowe.
Może ten obrazek wyjaśni o co mi chodzi:
link do wyższej rozdzielczości:
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Graf z wierzchołkami k-razy połączonymi krawędziami.
Zadanie 1:
Rozważmy dowolne drzewo \(\displaystyle{ D}\) rozpinające graf \(\displaystyle{ G}\). Ma ono oczywiście \(\displaystyle{ v-1}\) krawędzi. W miejscu każdej takiej krawędzi drzewa \(\displaystyle{ D}\) w grafie \(\displaystyle{ H}\) jest \(\displaystyle{ k}\) krawędzi - jeśli więc chcemy otrzymać drzewo rozpinające graf \(\displaystyle{ H}\) z krawędziami "w tych samych miejscach" (tzn. między tymi samymi wierzchołkami), to na każdym "miejscu" musimy wybrać jedną z \(\displaystyle{ k}\) krawędzi. "Miejsc" jest \(\displaystyle{ v-1}\), więc możliwych wyborów jest \(\displaystyle{ k^{v-1}}\). Skoro więc każde drzewo rozpinające grafu \(\displaystyle{ G}\) generuje tyle różnych drzew rozpinających graf \(\displaystyle{ H}\), to tych drugich jest \(\displaystyle{ k^{v-1}}\) razy więcej, co dowodzi wzoru.
Zadanie 2:
Rozważmy graf o dwu wierzchołkach, które połączone są \(\displaystyle{ n}\) krawędziami. Oczywiście ma on \(\displaystyle{ n}\) drzew rozpinających. Zastąpmy teraz każdą krawędź przez ścieżkę długości \(\displaystyle{ 2}\) (czyli "w środek" każdej krawędzi wstawmy wierzchołek). Otrzymany graf będzie grafem \(\displaystyle{ K(2,n)}\) i będzie miał \(\displaystyle{ n+2}\) wierzchołków i \(\displaystyle{ 2n}\) krawędzi. Stąd na mocy twierdzenia dostajemy, że będzie miał on:
\(\displaystyle{ n\cdot 2^{2n- (n+2)+1} = n2^{n-1}}\)
drzew rozpinających.
Q.
Rozważmy dowolne drzewo \(\displaystyle{ D}\) rozpinające graf \(\displaystyle{ G}\). Ma ono oczywiście \(\displaystyle{ v-1}\) krawędzi. W miejscu każdej takiej krawędzi drzewa \(\displaystyle{ D}\) w grafie \(\displaystyle{ H}\) jest \(\displaystyle{ k}\) krawędzi - jeśli więc chcemy otrzymać drzewo rozpinające graf \(\displaystyle{ H}\) z krawędziami "w tych samych miejscach" (tzn. między tymi samymi wierzchołkami), to na każdym "miejscu" musimy wybrać jedną z \(\displaystyle{ k}\) krawędzi. "Miejsc" jest \(\displaystyle{ v-1}\), więc możliwych wyborów jest \(\displaystyle{ k^{v-1}}\). Skoro więc każde drzewo rozpinające grafu \(\displaystyle{ G}\) generuje tyle różnych drzew rozpinających graf \(\displaystyle{ H}\), to tych drugich jest \(\displaystyle{ k^{v-1}}\) razy więcej, co dowodzi wzoru.
Zadanie 2:
Rozważmy graf o dwu wierzchołkach, które połączone są \(\displaystyle{ n}\) krawędziami. Oczywiście ma on \(\displaystyle{ n}\) drzew rozpinających. Zastąpmy teraz każdą krawędź przez ścieżkę długości \(\displaystyle{ 2}\) (czyli "w środek" każdej krawędzi wstawmy wierzchołek). Otrzymany graf będzie grafem \(\displaystyle{ K(2,n)}\) i będzie miał \(\displaystyle{ n+2}\) wierzchołków i \(\displaystyle{ 2n}\) krawędzi. Stąd na mocy twierdzenia dostajemy, że będzie miał on:
\(\displaystyle{ n\cdot 2^{2n- (n+2)+1} = n2^{n-1}}\)
drzew rozpinających.
Q.