algorytm wielomianowy - prawdopodobnie przepływy

TrzyRazyCztery · Post autor: **TrzyRazyCztery** » 12 lut 2016, o 15:15

Witam mam takie zadanie:
Zbiór $\displaystyle{ k}$ psów,$\displaystyle{ k}$ kotów i $\displaystyle{ k}$ chomików chcemy podzielić na trójki (pies,kot,chomik). o Kazdym psie wiemy z którymi kotami może być w trójce, i to samo o kocie. Musimy podac wielomianowy algorytm który stwierdza że można podzielić zwierzeta na k rozłącznych trójek lub że jest to niemożliwe.

Jedyne na co wpadlem to że moge zrobić z tego graf skierowany (krawedz skierowana pies -> kot jesli pies może byc w trojce z kotem) i to samo dla reszty i wtedy w jakis sposob oznaczyc maksymalnosc przeplywu na takiej krawedzi (ale nie wiem czy przez może $\displaystyle{ 1}$?) dodac wierzcholek $\displaystyle{ v}$ jako źródło i dac krawedz do kazdego psa z nieskonczonym przepływem i tak samo od kazdego chomika krawedz do nowego wierzcholka $\displaystyle{ u}$ który bedzie ujściem i wtedy użyć algorytmu np Forda i Fulkersona i sprawdzic czy przeplyw w takim grafie jest przynajmniej $\displaystyle{ k}$, bo jesli tak to znaczy ze mamy przynajmniej k ścieżek wierzchołkowo rozłącznych z których każda ma przepływ $\displaystyle{ 1}$. a jesli przepływ jest mniejszy niż $\displaystyle{ k}$ to znaczy że sie nie da. Czy to dobre rozumowanie? jak to uściślić i opisać by bylo to algorytmem wielomianowym?
Pozdrawiam

arek1357 · Post autor: **arek1357** » 13 lut 2016, o 20:26

Nie wiem ale na mój chłopski rozum bym zrobił macierz trójwymiarową:

$\displaystyle{ i}$ -pies

$\displaystyle{ j}$ - kot

$\displaystyle{ l}$- chomik

jeżeli i-ty pies może siedzieć a j-tym kotem , oraz z l-tym chomikiem to wartość:

$\displaystyle{ a_{ijl}}$ - na przecięciu się$\displaystyle{ i j l}$ dałbym jeden, w przeciwnym przypadku zero.

Otrzymałbym macierz trójwymiarową zero-jedynkową i starałbym się uogólnić twierdzenie Halla...

Czyli suma jedynek w każdym wierszu(wzdłużnym i wszerznym)(oraz w każdej kolumnie)

wynosi tyle samo macierz jest $\displaystyle{ k \times k \times k}$

norwimaj · Post autor: **norwimaj** » 13 lut 2016, o 22:01

TrzyRazyCztery, Twój pomysł wymaga poprawki.

$\displaystyle{ \begin{picture}(0,0)
\put(0,0){\circle*{3}}
\multiput(20,-20)(40,0){3}{\multiput(0,0)(0,40){2}{\circle*{3}}}
\put(120,0){\circle*{3}}
\put(-8,-3){$v$}
\put(14,-29){$P_2$}
\put(14,24){$P_1$}
\put(54,-29){$K_2$}
\put(54,24){$K_1$}
\put(94,-29){$C_2$}
\put(94,24){$C_1$}
\put(122,-3){$u$}
\put(0,0){\vector(1,-1){20}}
\put(0,0){\vector(1,1){20}}
\put(20,20){\vector(1,-1){40}}
\put(20,20){\vector(1,0){40}}
\put(60,20){\vector(1,0){40}}
\put(60,-20){\vector(1,0){40}}
\put(100,20){\vector(1,-1){20}}
\put(100,-20){\vector(1,1){20}}
\put(5,-18){$0$}
\put(5,12){$2$}
\put(36,24){$1$}
\put(36,-10){$1$}
\put(76,24){$1$}
\put(76,-16){$1$}
\put(109,-18){$1$}
\put(109,12){$1$}
\end{picture}}$

TrzyRazyCztery · Post autor: **TrzyRazyCztery** » 13 lut 2016, o 22:08

norwimaj, tak też pomyslalem bo zdalem sobie sprawe pozniej ze otrzymam drogi krawędziowo rozłączne ew a to mnie nie urządza :/

norwimaj · Post autor: **norwimaj** » 13 lut 2016, o 22:28

Możesz ograniczyć przepustowość krawędzi wychodzących z $\displaystyle{ v,}$ ale to jeszcze nie będzie ostatnia poprawka w tym sposobie.

Jest też inny sposób. Skoro pytanie jest tylko o istnienie $\displaystyle{ k}$ trójek, a nie o wyznacznie maksymalnej liczby trójek, to możesz problem podzielić na dwa niezależne: istnienie pełnego skojarzenia w grafie złożonym z psów i kotów oraz istnienie pełnego skojarzenia w grafie złożonym z kotów i chomików.

TrzyRazyCztery · Post autor: **TrzyRazyCztery** » 13 lut 2016, o 23:41

Masz na mysli jakiś algorytm który bierze graf złożony z psów i kotów a potem sprawdza czy suma stopni wierzchołków w każdym zbiorze psów o liczności $\displaystyle{ l}$ jest $\displaystyle{ \ge l}$ Bo to by oznaczało że wychodzi z niego conajmniej $\displaystyle{ l}$ krawędzi (bo miedzy psami nie ma krawędzi) i po sprawdzeniu wszystkich $\displaystyle{ l}$-elementowych podzbiorów dla $\displaystyle{ 1 \le l \le k}$ jesli we wszystkich warunek byłby spełniony to taki graf ma pełne skojarzenie? Czy tak sie interpretuje Twierdzenie Halla dla skojarzeń w grafie? i potem robie to samo z drugim grafem i jesli oba posiadają skojarzenia pełne to znaczy że mamy $\displaystyle{ k}$ takich trójek?

Edit. Nabrałem wątpliwości co do algorytmu który by sprawdzał wszystkie 1,2,3....k elementowe podzbiory wierzchołków np psów. A raczej wątpliwości co do jego wielomianowości

Edit 2. Czy przerobienie takiego grafu dodając jednak wierzchołek źródlowy o krawędzi 1 do każdego psa i ujsciowy o krawędzi 1 od kazdego kota a potem zastosowanie algorytmu Forda-Fulkersona i sprawdzenie czy przepływ jest wiekszy równy k nie zda tu egzaminu? a jesli zda to czy jest konieczne rozbijanie tego na 2 grafy?

norwimaj · Post autor: **norwimaj** » 14 lut 2016, o 14:54

Sprawdzenie, czy istnieje pełne skojarzenie w grafie dwudzielnym, można wykonać wielomianowo za pomocą algorytmu Forda-Fulkersona tak jak piszesz: przepustowości równe $\displaystyle{ 1}$ na krawędziach od źródła do psów i od kotów do ujścia.

Rozbijanie na dwa grafy nie jest konieczne. Każdy sposób jest dobry, byle poprawny.