Graf z wierzchołkami k-razy połączonymi krawędziami.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Summum Malum
Użytkownik
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.

Post autor: Summum Malum »

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.
Ostatnio zmieniony 11 kwie 2013, o 11:40 przez Summum Malum, łącznie zmieniany 1 raz.
Kartezjusz
Użytkownik
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.

Post autor: Kartezjusz »

Ja rozumieć kąty przyległe w grafie?
Summum Malum
Użytkownik
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.

Post autor: Summum Malum »

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ą.
Kartezjusz
Użytkownik
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.

Post autor: Kartezjusz »

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ę
Summum Malum
Użytkownik
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.

Post autor: Summum Malum »

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.
Ostatnio zmieniony 11 kwie 2013, o 12:23 przez Summum Malum, łącznie zmieniany 1 raz.
Kartezjusz
Użytkownik
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.

Post autor: Kartezjusz »

A z każdego wyboru grafu \(\displaystyle{ G}\) można wyjąć \(\displaystyle{ \tau (G)}\)drzew
Summum Malum
Użytkownik
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.

Post autor: Summum Malum »

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.
Kartezjusz
Użytkownik
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.

Post autor: Kartezjusz »

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.
Summum Malum
Użytkownik
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.

Post autor: Summum Malum »

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.
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
Użytkownik
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.

Post autor: Kartezjusz »

Myślę,że chodzi tu o drzewa pełne. CZyli \(\displaystyle{ v}\) -wierzchołkowe.
Summum Malum
Użytkownik
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.

Post autor: Summum Malum »

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

Post autor: »

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