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?