szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 paź 2015, o 04:32 
Użytkownik

Posty: 80
Lokalizacja: Wałbrzych
Witam,

mam problem z wyznaczaniem kliki w grafie permutacji.

Mam poniższy graf:
1 3
1 5
1 4
2 4
2 3
2 5
3 4

lub w formie graficznej, żeby było wszystko jasne
Obrazek

Na podstawie grafu stworzyłem jego permutacje:
(4 3 5 1 2)

Zgodnie z pierwszą kropką z wiki: https://en.wikipedia.org/wiki/Permutati ... algorithms

Najdłuższy malejący ciąg powinien określać wielkość największej kliki w grafie. Jak widać w moim przypadku to nie zadziałało - najdłuższy ciąg malejący w mojej permutacji wynosi 2, a największa klika wynosi 3.

Proszę o pomoc we wskazaniu błedu. Domyślam się, że jest on związany z permutacją wyliczoną przeze mnie, ale nie mogę dojść gdzie się pomyliłem.

Z góry dziękuję za pomoc.

pozdrawiam
Antek
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 paź 2015, o 20:42 
Gość Specjalny

Posty: 5781
Lokalizacja: Toruń
U Ciebie najdłuższy malejący podciąg to 4,3,1, więc nie widzę niezgodności.
Góra
Mężczyzna Offline
PostNapisane: 2 paź 2015, o 22:52 
Użytkownik

Posty: 80
Lokalizacja: Wałbrzych
faktycznie... patrzyłem na to 10 razy i tego nie zauważyłem :/
Bardzo Ci dziękuję za pomoc!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest permutacji zbioru  le3o  1
 Grafy eulerowskie, półeulerowski i droga w grafie.  squared  6
 Składanie permutacji. - zadanie 2  myszka9  1
 Liczba wierzchołków w grafie regularnym  michalalex132  2
 Drzewa spinajace w grafie dwudzielnym  mol_ksiazkowy  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl