szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lut 2016, o 15:15 
Użytkownik

Posty: 101
Lokalizacja: Wro
Witam mam takie zadanie:
Zbiór k psów,k kotów i 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 1?) dodac wierzcholek 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 u który bedzie ujściem i wtedy użyć algorytmu np Forda i Fulkersona i sprawdzic czy przeplyw w takim grafie jest przynajmniej k, bo jesli tak to znaczy ze mamy przynajmniej k ścieżek wierzchołkowo rozłącznych z których każda ma przepływ 1. a jesli przepływ jest mniejszy niż k to znaczy że sie nie da. Czy to dobre rozumowanie? jak to uściślić i opisać by bylo to algorytmem wielomianowym?
Pozdrawiam
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2016, o 20:26 
Użytkownik
Avatar użytkownika

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

i -pies

j - kot

l- chomik

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

a_{ijl} - na przecięciu się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 k \times k \times k
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2016, o 22:01 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
TrzyRazyCztery, Twój pomysł wymaga poprawki.

\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}
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2016, o 22:08 
Użytkownik

Posty: 101
Lokalizacja: Wro
norwimaj, tak też pomyslalem bo zdalem sobie sprawe pozniej ze otrzymam drogi krawędziowo rozłączne ew a to mnie nie urządza :/
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2016, o 22:28 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Możesz ograniczyć przepustowość krawędzi wychodzących z v, ale to jeszcze nie będzie ostatnia poprawka w tym sposobie.

Jest też inny sposób. Skoro pytanie jest tylko o istnienie 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.
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2016, o 23:41 
Użytkownik

Posty: 101
Lokalizacja: Wro
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 l jest \ge l Bo to by oznaczało że wychodzi z niego conajmniej l krawędzi (bo miedzy psami nie ma krawędzi) i po sprawdzeniu wszystkich l-elementowych podzbiorów dla 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 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 :cry:

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?
Góra
Mężczyzna Offline
PostNapisane: 14 lut 2016, o 14:54 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
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 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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Algorytm Dijkstry - odtworzenie grafu  PoisonPrince  0
 algorytm dijkstry  artti  0
 Algorytm RSA - obliczanie współczynnika d  Seahawk  1
 Matematyka dyskretna - Algorytm  tyrla  1
 Algorytm wież Hanoi  nedroxn  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl