Dopelnienie grafu, jak policzyc powstale grafy

Odpowiedz Nowy wątek
2006-11-05 14:26

Rejestracja: 13 lat temu

Ostatnio: 8 lat temu

0

Nigdzie nie moge znalezc odpowiedzi na pytanie jak policzyc grafy powstale w wyniku utworzenia dopelnienia grafu.

Mam liste sasiedztwa wierzcholkow (lub jesli to moze ulatwic to bardzo latwo moge uzyskac spis wszystkich krawedzi).

Przykladowa lista sasiedztwa:
1: 2,4
2: 3,5
3: 4,5
4: 5

Graf jest nieskierowany, dlatego jesli 5 jest sasiadem 4 to i 4 jest sasiadem 5.

Dopelnienie grafu powinno wygladac tak:
1: 3,5
2: 4

Sasiadujace wierzcholki tworza krawedzie, ktorych nie bylo w pierwotnym grafie. Powstaly dwa grafy.

Mozna to zaimpementowac tak ze dla kazdego wierzcholka po kolei bede sprawdzal czy jest sasiadem kolejnych wierzcholkow. Jesli nie to do kolejki dorzuce ten nie sasiadujacy wierzcholek. Byloby to jakby przejscie po nowo powstalym grafie. Gdy skoncza sie wierzcholki, mozna wziasc kolejny nie odwiedzony i zrobic to samo, w miedzyczasie podliczajac ze przechodzi sie juz po kolejnym powstalym grafie. Jednak takie rozwiazanie ma zlozonosc kwadratowa. Jest na to jakis prostrzy sposob?

Pozostało 580 znaków

2006-11-06 19:27

Rejestracja: 16 lat temu

Ostatnio: 6 lat temu

0

Wsytarczy wypełnić macież sąsiedztw. Pozostałe puste miejsca są dopełnieniem.

Pozostało 580 znaków

spływaj
2006-11-06 20:16
spływaj
0

1) Macierz macierzą, ale tutaj chodzi o macierz 100000 x 100000 ;>
2) To zadanie z Olimpiady informatycznej. W oi chodzi o samodzielne rozwiązywanie zadań...

Pozostało 580 znaków

2006-11-07 15:05

Rejestracja: 13 lat temu

Ostatnio: 8 lat temu

0
spływaj napisał(a)

1) Macierz macierzą, ale tutaj chodzi o macierz 100000 x 100000 ;>
2) To zadanie z Olimpiady informatycznej. W oi chodzi o samodzielne rozwiązywanie zadań...

Masz racje, ze chodzi o zadanie z OI. Rzeczywiscie moze o zbyt wiele spytalem. :)

Macierz jest dobra dla malych liczb, ale w tym wypadku zajmowalaby duzo za duzo. ;) Jest na to inny sposob, choc ten ktory wymyslilem jest nieco wadliwy.

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0