Algorytmy kombinatoryczne w bioinformatyce − Zadanie II

Przed przystąpieniem do realizacji zadania proszę zapoznać się z wykładem 2 (sekwencjonowanie cz. 1).

Definicje:

1-graf jest grafem, w którym niedopuszczone są krawędzie wielokrotne.

Graf sprzężony (adjoint) G=(V,A) grafu skierowanego H=(U,V) jest 1-grafem, którego wierzchołki reprezentują łuki z H i który posiada łuk od x do y wtedy i tylko wtedy, gdy w H wierzchołek końcowy łuku x jest wierzchołkiem początkowym łuku y.

Skierowany graf liniowy to graf sprzężony G 1-grafu H. Innymi słowy, jeśli H jest 1-grafem, to G jest jego grafem sprzężonym oraz liniowym, jeśli H nie jest 1-grafem, to G jest jego grafem sprzężonym, ale nie liniowym.

1-graf G=(V,A) jest grafem sprzężonym wtedy i tylko wtedy, gdy następująca własność jest spełniona dla każdej pary x,y ∈ V:
N⁺(x) ∩ N⁺(y) ≠ Ø ⇒ N⁺(x) = N⁺(y)
gdzie N⁺(x) jest zbiorem następników x. Czyli, dla każdej pary wierzchołków grafu, ich zbiory (bezpośrednich) następników muszą być albo rozłączne, albo identyczne.

Dla grafów skierowanych: graf sprzężony jest grafem liniowym wtedy i tylko wtedy, gdy nie zawiera jako podgrafu żadnej z następujących struktur:

Każda z powyższych struktur odpowiada bowiem łukom wielokrotnym w grafie H.

Źródło:
C. Berge, Graphs and Hypergraphs, North-Holland Publishing Company, London, 1973.
J. Błażewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Applied Mathematics 98, 1-19, 1999.

Treść zadania:

Należy zaimplementować algorytm dokładny o złożoności wielomianowej realizujący następujące czynności:
− wczytanie dowolnego grafu skierowanego z pliku tekstowego,
− sprawdzenie, czy wczytany graf jest grafem sprzężonym,
− jeśli graf jest grafem sprzężonym, sprawdzenie, czy jest grafem liniowym,
− wypisanie komunikatu o wyniku powyższego sprawdzenia,
− jeśli graf jest grafem sprzężonym, przekształcenie go w jego graf oryginalny (H),
− zapisanie grafu wynikowego H do pliku tekstowego innego niż wejściowy, lecz w tym samym formacie.

Graf na wejściu może być dowolnym nieważonym grafem skierowanym, tzn. może być spójny bądź nie, może zawierać pętle własne, wierzchołki izolowane, krawędzie wielokrotne. Można założyć, że graf nie będzie miał więcej niż 20 wierzchołków. Format zapisu grafu w pliku tekstowym jest dowolny, ale musi być jednoznaczny i czytelny dla użytkownika. Przykładowo, nie wystarczy grafu zapisać w postaci zestawu łuków (x,y), gdyż w ten sposób pomijane są wierzchołki izolowane. Reprezentacja macierzowa jest nierekomendowana ze względu na trudność edycji przy większej liczbie wierzchołków. Aby upewnić się, że plik wyjściowy jest w tym samym formacie co wejściowy, proszę przeprowadzić testy, podając wyjście na wejście programu.

Przekształcenie grafu G w graf H można zrealizować wg uznania, jednak moim zdaniem najprostszym sposobem jest podany poniżej. Każdy wierzchołek z G zamieniamy najpierw na osobny łuk w H. Następnie, dla każdego łuku w G realizujemy odpowiednie połączenie w H poprzez przeindeksowanie wierzchołków z H. Przykładowo, dla grafu G złożonego z łuków (a,b), (b,c), (b,d), (d,a), tworzymy graf H najpierw jako taki zbiór rozłącznych łuków: (1,2), (3,4), (5,6), (7,8), które reprezentują odpowiednio wierzchołki a, b, c, d. Następnie należy odtworzyć jeden do jednego połączenia obecne w G w następujący sposób. Mamy łuk (a,b) w G, czyli w H musi być przejście ze zgodnym zwrotem z łuku odpowiadającego a do łuku odpowiadającego b. Dla rozłącznych obecnie łuków (1,2) i (3,4) potrzebujemy więc skompresować wierzchołki 2 i 3 do jednego, co łatwo uczynić przez przeindeksowanie w zbiorze wszystkich wystąpień 3 na 2. Otrzymujemy łuki (1,2), (2,4), (5,6), (7,8). Tak samo należy postąpić dla wszystkich łuków z G po kolei. Po zastosowaniu tej procedury graf na wyjściu nie będzie miał wierzchołków poindeksowanych po kolei, można albo tak zostawić (tylko wtedy format zapisu grafu musi taką sytuację uwzględnić), albo wierzchołki przeindeksować, żeby były po kolei.

Gotowy program należy przetestować na wygenerowanych we własnym zakresie instancjach, wśród których znajdzie się co najmniej 10 grafów będących grafami sprzężonymi (część z nich także grafami liniowymi) o rozmiarze co najmniej 10 wierzchołków. Grafy powinny być różnorodne, żeby testy mogły wykryć ewentualne błędy w programie, generalnie powinny charakteryzować się odpowiednią złożonością, np. nie powinny być drzewami, warto uwzględnić długie przeplatające się cykle. Integralną częścią testów jest "ręczne" sprawdzenie, czy wynik transformacji grafu jest poprawny.

W sprawozdaniu należy zamieścić: opis zastosowanego formatu zapisu grafu, opis algorytmu, oszacowanie złożoności algorytmu, opis przeprowadzonych testów wraz z wizualizacją przykładowych transformacji przeprowadzonych przez algorytm (tzn. rysunki grafów wejściowych G i ich grafów oryginalnych H, dla co najmniej czterech transformacji na grafach o co najmniej 10 wierzchołkach), wnioski. Rysując grafy, proszę unikać przedstawiania powiązań za pomocą łuków dwukierunkowych (jeden łuk o dwóch zwrotach), a łuki grafu H proszę opisać indeksem odpowiadającego mu wierzchołka grafu G.

Termin realizacji:

Omówienie zadania: 15 października (grupa wtorkowa), 16 października (grupa środowa) i 10 października (grupy czwartkowe).
Oddanie sprawozdania i zaliczenie zadania: 19 listopada (grupa wtorkowa), 20 listopada (grupa środowa) i 14 listopada (grupy czwartkowe).