Kostka n-wymiarowa - usuwanie krawędzi

[kamaz08]

Kostka n-wymiarowa to graf skierowany, którego wierzchołkami są \(\displaystyle{ n}\)-ki zero-jedynkowe, \(\displaystyle{ \mathcal{G}_n =\{ (a_1,a_2,...,a_n) : a_i \in \{0,1\} \}}\), wierzchołki \(\displaystyle{ a = (a_1, a_2, ..., a_n), b = (b_1, b_2, ... ,b_n)}\) połączone są krawędzią tylko gdy różnią się na jednym miejscu \(\displaystyle{ j \in \{1,2,...,n\} : a_j = 0, b_j = 1}\).
Z kostki usuwamy k-krawędzi. Obliczyć wartość oczekiwaną oraz wariancje na ilość dróg z wierzchołka (0,0,...,0) do (1,1,...,1).

Co mam z zadania:
Ilość dróg w grafie \(\displaystyle{ n!}\)
Długość drogi \(\displaystyle{ n}\)
Ilość krawędzi \(\displaystyle{ n2^{n-1}}\)

I nie wiem jak się zabrać za to.
Myślałem żeby:
Zmienna losowa, która mówi czy dana droga została usunięta
\(\displaystyle{ X_i = \{ 1 -}\) gdy z grafu usuwamy drogę; \(\displaystyle{ 0 -}\) w p.p. \(\displaystyle{ \}}\)
Ale nie wychodzi

[Gosda]

Wskazówka: rozpatrzmy przypadek \(\displaystyle{ n=3}\). Nasz graf to sześcian, więc łatwo sobie wszystko wyobrazić i policzyć na palcach.

Zastanówmy co dzieje się, jeśli usuwamy pojedynczą krawędź. Możemy to zrobić na \(\displaystyle{ 12}\) sposobów, w \(\displaystyle{ 6}\) z nich będzie pięć dróg między skrajnymi wierzchołkami, w \(\displaystyle{ 6}\) będą cztery drogi.

Co jeśli usuwamy dwie krawędzie? \(\displaystyle{ 9}\) razy dwie drogi, \(\displaystyle{ 30}\) razy trzy drogi, \(\displaystyle{ 27}\) cztery drogi.

Co jeśli usuwamy trzy krawędzie? \(\displaystyle{ 2}\) razy nie będzie żadnej drogi (jeśli usuniemy wszystkie krawędzie z początkowego lub końcowego wierzchołka), \(\displaystyle{ 30}\) razy jedna droga, \(\displaystyle{ 96}\) razy dwie drogi, \(\displaystyle{ 86}\) razy trzy drogi, \(\displaystyle{ 6}\) razy będą cztery drogi. Uff, trochę tego liczenia było.

Jeśli się to wszystko powymnaża i pododaje, wychodzą ładne wyniki:

\(\displaystyle{ 6 \cdot 9, 6 \cdot 36, 6 \cdot 84}\)

Albo jeszcze inaczej:

\(\displaystyle{ 3! \cdot {9 \choose 1}, 3! \cdot {9 \choose 2}, 3! \cdot {9 \choose 3}}\)

Wydaje mi się, że łącznie wszystkich dróg będzie

\(\displaystyle{ n! \cdot {{n \cdot (2^{n-1} - 1)} \choose k}}\)

albo coś podobnego do tego. Żeby dostać wartość oczekiwaną, trzeba podzielić przez ilość sposobów, na które możemy skasować \(\displaystyle{ k}\) spośród \(\displaystyle{ n \cdot 2^{n-1}}\) wierzchołków. Dziwne zadanie Z pewnością da się je zrobić dużo bardziej wprost.

[matmatmm]

A masz jakąś metodę na zliczenie tego w ogólności? Ja przeliczyłem zadanie dla \(\displaystyle{ k=1}\) i dowolnego \(\displaystyle{ n\in\NN}\). Wzór wyszedł identyczny, jak ten który podejrzewasz. Myślę, że dałbym jeszcze radę przeliczyć dla \(\displaystyle{ k=2}\), ale nie mam pojęcia jak to zrobić dla dowolnego \(\displaystyle{ k}\).

[arek1357]

Do zliczania dróg proponuję macierz sąsiedztwa

I tak warto zamienić nasz graf na graf skierowany w bardzo prosty sposób:

\(\displaystyle{ (a_{1}^0);(a_{1}^1,a_{2}^1,...,a_{ {n \choose 1} }^1);(a_{1}^2,a_{2}^2,...,a_{ {n \choose 2} }^2),...,(a_{ {n \choose n}^n })}\)

Wypisałem wszystkie wierzchołki grafu skierowanego grupując je pod względem ilości jedynek w wierzchołku, np:

\(\displaystyle{ a_{1}^2=(1,1,0,0,...,0); a_{2}^2=(1,0,1,0,0,...,0);...}\)

potęga u góry oznacza ilość jedynek w wierzchołku...

I teraz dla grafu skierowanego tworzymy macierz sąsiedztwa...

np załóżmy, że jest to krawędź.:

\(\displaystyle{ \left( a_{1}^0 \rightarrow a_{1}^1\right) }\)

wtedy wartość tej komórki w macierzy ma wartość jeden

\(\displaystyle{ a_{1}^1=(1,000,...,0),a_{k}^2=(0,0,1,1,0,...,0)}\)

A między tymi wierzchołkami jest wartość zero bo nie ma połączeń...

I teraz tworzymy macierz sąsiedztwa będzie to taka górno trójkątna, na głównej przekątnej same zera..., pod przekątną też zera...

I teraz szukamy ilości dróg między:

\(\displaystyle{ a_{1}^0 \rightarrow a_{1}^n}\)

Jak widać jest to ilość dróg o długości n...

Szuka się tego potęgują macierz , nazwijmy ją A

\(\displaystyle{ A^n}\)

Jest to macierz:

\(\displaystyle{ 2^n \times 2^n}\)

element macierzy.: \(\displaystyle{ A^n}\) :

\(\displaystyle{ c_{1,2^n}}\)

Jest odpowiedzią na pytanie ile jest ścieżek między pierwszym wierzchołkiem a ostatnim...

A usuwanie krawędzi polega na usuwaniu jedynek w górnym trójkącie i takim samym zliczaniu dróg od pierwszego do ostatniego wierzchołka...

Oczywiście działa to dla grafu skierowanego...

[Dasio11]

Ogólnie: jeśli \(\displaystyle{ S \subseteq X \times Y}\), gdzie \(\displaystyle{ X, Y}\) są zbiorami skończonymi, to

\(\displaystyle{ \sum_{x \in X} \# \{ y \in Y : \left< x, y \right> \in S \} = |S| = \sum_{y \in Y} \# \{ x \in X : \left< x, y \right> \in S \}}\).

W zadaniu dla każdego wyboru \(\displaystyle{ k}\) różnych krawędzi chcemy wyznaczyć liczbę ścieżek nieprzechodzących przez żadną z tych krawędzi, a następnie dodać otrzymane liczby. Na mocy powyższego wzoru, do tego samego wyniku prowadzi zliczenie dla każdej ścieżki, ile jest zestawów \(\displaystyle{ k}\) różnych krawędzi nienależących do tej ścieżki, i zsumowanie tych liczb.

Dla ustalonej ścieżki taki zestaw oczywiście wiąże się z wyborem \(\displaystyle{ k}\) krawędzi spośród wszystkich \(\displaystyle{ n2^{n-1} - n}\) krawędzi nieleżących na ścieżce, a więc jest ich \(\displaystyle{ \binom{n 2^{n-1} - n}{k}}\). Szukaną liczbę otrzymujemy więc mnożąc ten wynik przez liczbę wszystkich możliwych ścieżek, co daje \(\displaystyle{ n! \cdot \binom{n 2^{n-1} - n}{k}}\), tak jak zauważył Gosda.

[kamaz08]

Czyli dla wartości oczekiwanej:
\(\displaystyle{ X_i}\) - zmienna losowa przyjmująca wartości \(\displaystyle{ \{0,1\}}\), czy \(\displaystyle{ i}\)-ta droga pozostaje w grafie po usunięciu k-krawędzi.
\(\displaystyle{ E(X) = E \left( \sum^{n!}_{i=1} X_i \right) = \sum^{n!}_{i=1} E(X_i) = n!E(X_i) }\)
\(\displaystyle{ E(X_i) = 0 * P(X_i = 0) + 1 * P(X_i = 1) = P(X_i = 1)= \frac{\binom{n2^{n-1}-n}{k}}{\binom{n2^{n-1}}{k}}}\)
Czyli wartość oczekiwana ilości pozostałych dróg to
\(\displaystyle{ E(X) = n! \frac{\binom{n2^{n-1}-n}{k}}{\binom{n2^{n-1}}{k}} = n! \frac{(n2^{n-1} - n)! (n2^{n-1}-k)!}{(n2^{n-1})!(n2^{n-1} - k - n)!} }\)

Teraz wariancja:

\(\displaystyle{ Var(X) = E(X^2) - (EX)^2}\)

\(\displaystyle{ (EX)^2}\) już obliczone
\(\displaystyle{ X^2}\) Oznacza ilość pozostałych par dróg w grafie.
\(\displaystyle{ E(X^2) = E \left( \sum^{n!}_{i=1} X_i^2 \right) + 2E \left( \sum_{i \neq j}^{\binom{n!}{2}}X_i X_j \right)}\)
\(\displaystyle{ E \left( \sum^{n!}_{i=1} X_i^2 \right) }\) - to \(\displaystyle{ EX}\)

I teraz myślałem żeby zrobić iloma krawędziami różnią się dane drogi i tutaj nie jestem pewien.
\(\displaystyle{ E(X_i X_j) = \sum_{i=1}^n \left( \frac{\binom{n2^{n-1}-n-i}{k}}{\binom{n2^{n-1}}{k}}\right)}\)