Podgrafy izomorficzne

Sylakenth · Post autor: **Sylakenth** » 27 maja 2012, o 16:22

Mam problem z niniejszym zadaniem, szukałem rozwiązań, ale niestety nie mołgem nigdzie znaleźć.
Wyznacz liczbę podgrafów pełnego trójdzielnego grafu \(\displaystyle{ K _{3,5,8}}\) które są izomorficzne z grafem \(\displaystyle{ K _{1,9}}\)

aussie · Post autor: **aussie** » 21 sie 2012, o 00:25

Podpisuję się pod tym zadaniem, szukałam w wielu źródłach i nie mogłam znaleźć wytłumaczenia.

norwimaj · Post autor: **norwimaj** » 21 sie 2012, o 11:59

Jest jeden taki podgraf (z dokładnością do izomorfizmu).

A teraz poważnie. Ile jest w \(\displaystyle{ K _{3,5,8}}\) wierzchołków, które mają co najmniej \(\displaystyle{ 9}\) sąsiadów?

aussie · Post autor: **aussie** » 21 sie 2012, o 23:26

Wydaje mi się, że jest \(\displaystyle{ 8}\) takich wierzchołków.

norwimaj · Post autor: **norwimaj** » 22 sie 2012, o 00:27

Dobrze, jest ich dokładnie \(\displaystyle{ 3+5}\). To spośród nich musi pochodzić szczególny wierzchołek podgrafu \(\displaystyle{ K_{1,9}}\). Na ile sposobów można wybrać pozostałe wierzchołki (w zależności od tego, jaki wybraliśmy pierwszy wierzchołek)?

aussie · Post autor: **aussie** » 22 sie 2012, o 10:40

Następne \(\displaystyle{ 9}\) wierzchołków wybieramy spośród \(\displaystyle{ 15}\) pozostałych. Czyli to będzie \(\displaystyle{ \frac{15!}{6!}}\).

norwimaj · Post autor: **norwimaj** » 22 sie 2012, o 12:19

Na pewno każdy z pozostałych \(\displaystyle{ 15}\) wierzchołków można wybrać?

aussie · Post autor: **aussie** » 22 sie 2012, o 16:42

Idąc analogią, jeżeli na początku miałam znaleźć liczbę wierzchołków które mają co najmniej \(\displaystyle{ 9}\) sąsiadów, to teraz mam znaleźć liczbę wierzchołków z co najmniej \(\displaystyle{ 1}\) sąsiadem, czyli będzie to dowolny wierzchołek. Pierwsze wybranie wierzchołka musi być dokonane spośród \(\displaystyle{ 8}\), a następne wydaje mi się że to będzie każdy wierzchołek z pozostałych, nie wiem gdzie jest błąd.

norwimaj · Post autor: **norwimaj** » 22 sie 2012, o 20:57

No to spróbuj tak zrobić i zobacz czy w ten sposób otrzymasz \(\displaystyle{ K_{1,9}}\).

aussie · Post autor: **aussie** » 22 sie 2012, o 22:18

Jeżeli wybór wierzchołka z co najmniej \(\displaystyle{ 9}\) sąsiadami będzie dotyczył grupy \(\displaystyle{ 3}\) wierzchołków nie sąsiednich to wybór \(\displaystyle{ 9}\) pozostałych będzie się ograniczał do \(\displaystyle{ 13}\)(czyli \(\displaystyle{ 2}\) pozostałe w grupie nie można wybrać), jeżeli wybór będzie dotyczył grupy \(\displaystyle{ 5}\) wierzchołków nie sąsiednich to wybór \(\displaystyle{ 9}\) pozostałych będzie się ograniczał do \(\displaystyle{ 11}\)(czyli \(\displaystyle{ 4}\) pozostałe w grupie nie można wybrać), tak to widzę.

norwimaj · Post autor: **norwimaj** » 22 sie 2012, o 22:41

To w takim razie wszystkich możliwości jest \(\displaystyle{ 3\cdot\binom{13}9+5\cdot\binom{11}9}\).

aussie · Post autor: **aussie** » 22 sie 2012, o 22:51

A odpowiedzią do tego zadania będzie kombinacja bez powtórzeń \(\displaystyle{ 8}\) po \(\displaystyle{ 1}\) pomnożona przez powyższe możliwości wybrania \(\displaystyle{ 9}\) wierzchołków?

norwimaj · Post autor: **norwimaj** » 22 sie 2012, o 22:57

Dlaczego chcesz to jeszcze mnożyć przez \(\displaystyle{ 8}\)? Został już wybrany wierzchołek szczególny i pozostałe \(\displaystyle{ 9}\) wierzchołków, to już chyba podgraf jest ustalony?

aussie · Post autor: **aussie** » 22 sie 2012, o 23:15

No tak, to jak się ma tutaj wybór tego \(\displaystyle{ 1}\) wierzchołka z \(\displaystyle{ 8}\), nie uwzględniamy tego?
Chodzi mi już o ostateczną liczbę podgrafów.

norwimaj · Post autor: **norwimaj** » 23 sie 2012, o 13:04

\(\displaystyle{ 8=3+5}\). Wybór jednego wierzchołka z ośmiu to wybór jednego wierzchołka z trzech albo z pięciu. To są dwa rozłączne przypadki, więc stosujemy regułę dodawania.