Program MODGRAF służy do rozwiązywania problemów decyzyjnych za pomocą modeli i algorytmów grafowych bądź sieciowych. TYPOWY PROCES MODELOWANIA I ROZWIĄZYWANIA PROBLEMU: =================================================== 1) Zdefiniowanie grafu w postaci pliku tekstowego ("Plik/Nowy graf") lub wczytanie grafu z istniejącego pliku ("Plik/Wczytaj graf"). 2) Po wczytaniu pliku ze zdefiniowanym grafem może wystąpić jedna z trzech sytuacji: * Graf wczytuje się poprawnie i w głównym oknie pojawia się jego graficzna reprezentacja. W zależności od potrzeb poszczególne wierzchołki grafu można wtedy przesuwać za pomocą przeciągania myszą z wciśniętym jej lewym klawiszem. Przesunięcie całego grafu realizowane jest podobnie, ale z wciśniętym klawiszem Shift. Zmienione rozmieszczenie wierzchołków grafu może zostać dopisane do pliku wejściowego i zapamiętane poprzez wybranie z menu "Plik" pozycji "Zachowaj topologię jako". * Graf wczytuje się poprawnie, ale pojawia się komunikat informujący, że graf nie będzie wyświetlany. Następuje to w przypadku wczytywania dużych grafów. Ich pełna reprezentacja graficzna jest wtedy niemożliwa, a w głównym oknie wyświetlona jest tylko zastępcza winieta, która informuje o parametrach wczytanego grafu. Pomimo braku reprezentacji graficznej wszystkie algorytmy i operacje na grafie są dostępne. * Pojawia się komunikat o błędzie i numer linii, w której zidentyfikowano błąd. W takim przypadku należy poprawić opis grafu w pliku tekstowym, wybierając z menu "Plik" pozycję "Edytuj graf". 3) Wybranie odpowiedniego algorytmu (patrz opis poniżej) spowoduje rozwiązanie problemu i wyświetlenie wyniku, skąd może on zostać zapisany w osobnym pliku. W większości przypadków rozwiązanie zobrazowane jest także w postaci reprezentacji graficznej. ZESTAW DOSTĘPNYCH OPCJI PROGRAMU: ==================================== [Plik] - OPERACJE NA PLIKACH {Nowy graf} Otwiera okno edycyjne, pozwalające zdefiniować graf w postaci pliku tekstowego (patrz "Format pliku wejściowego"). {Wczytaj graf} Wczytuje graf z wcześniej zapisanego pliku, utworzonego za pomocą opcji "Plik/Nowy graf" lub zewnętrznego edytora tekstowego. {Edytuj graf} Otwiera okno edycyjne, zawierające opis aktualnie wczytanego grafu, pozwalając na zmodyfikowanie jego postaci. {Zachowaj topologię jako} Pozwala na zapisanie w pliku akualnego położenia wierzchołków grafu na ekranie. {Koniec} Wyjście z programu. ------------------------------------ [Trasy] - ALGORYTMY WYZNACZANIA TRAS {Drzewo rozpinające} Algorytm znajduje podgraf analizowanego grafu, który jest drzewem zawierającym wszystkie jego wierzchołki i suma wag krawędzi jest najmniejsza (minimalne drzewo rozpinające) lub największa (maksymalne drzewo rozpinające). Algorytmy wymagają grafu nieskierowanego. Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - reprezentujący wagę krawędzi. {Najkrótsze drogi - Alg. Dijkstry} Algorytm znajduje najkrótsze drogi z podanego wierzchołka do wszystkich pozostałych wierzchołków grafu. Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - wagę krawędzi. Wagi krawędzi muszą być nieujemne. {Najkrótsze drogi - Alg. Floyda} Algorytm znajduje najkrótsze drogi pomiędzy wszystkimi parami wierzchołków. Jako wynik powstaje tablica odległości pomiędzy wierzchołkami. Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - wagę krawędzi. {Komiwojażer} Problem komiwojażera polega na znalezieniu w grafie cyklu, który przechodziłby przez każdy jego wierzchołek dokładnie raz, a suma wag poszczególnych krawędzi cyklu była najmniejsza z możliwych. Algorytmy Near i FI znajdują pewne zgrubne przybliżenie rozwiązania o najmniejszej sumie wag i mogą zostać poprawione poprzez zastosowanie dodatkowych heurystyk poprawy: 2Opt i 3Opt. Istota algorytmu 2Opt nie pozwala na zastosowanie go do grafu skierowanego. Algorytm dokładny znajduje optymalne rozwiązanie problemu komiwojażera, zarówno dla grafów skierowanych, jak i nieskierowanych. Możliwość znalezienia rozwiązania dokładnego okupiona jest jednak znacznym wydłużeniem czasu obliczeń. Krawędzie grafu powinny mieć zdefiniowany jeden parametr - wagę krawędzi. {Cykl Eulera} Algorytm znajduje taki cykl w grafie, w którym każda krawędź (łuk) występuje dokładnie raz. Po wykonaniu algorytmu kolejność przechodzenia krawędzi zaznaczona jest numerami. Krawędzie grafu nie muszą mieć podanych żadnych parametrów liczbowych. ------------------------------------ [Przepływy] - ALGORYMY WYZNACZANIA PRZEPŁYWÓW W SIECIACH {Maksymalny przepływ} Algorytm wyznacza maksymalny przepływ pomiędzy podaną parą wierzchołków. Krawędzie grafu powinny mieć określony jeden parametr - przepustowość krawędzi (łuku). {Najtańszy przepływ} Algorytm wyznacza najtańszy przepływ o zadanej wielkości pomiędzy podaną parą wierzchołków. Krawędzie grafu powinny mieć dwa parametry. Pierwszy parametr oznacza górną przepustowość krawędzi (dolne ograniczenie na przepływ jest przyjmowane jako 0). Drugi parametr określa jednostkowy koszt przepływu przez krawędź. ------------------------------------ [Kolorowanie] - ALGORYTMY KOLOROWANIA GRAFÓW {Kolorowanie wierzchołków} Problem ten polega na takim pokolorowaniu wierzchołków, aby żadne dwa wierzchołki ze sobą połączone nie miały przypisanego takiego samego koloru i liczba użytych kolorów była jak najmniejsza. Do dyspozycji znajduje się kilka algorytmów heurystycznych o różnych dokładnościach i czasach działania. {Kolorowanie krawędzi} Algorytm przyporządkowuje kolory krawędziom grafu w taki sposób, aby żadne dwie krawędzie wychodzące z jednego wierzchołka nie były pomalowane takim samym kolorem i liczba użytych kolorów była jak najmniejsza. W obu modelach kolorowania krawędzie nie muszą mieć określonych parametrów liczbowych. ------------------------------------ [Skojarzenia] - ALGORYTMY WYZNACZANIA SKOJARZEŃ {Maksymalne skojarzenie} Algorytm wyznacza maksymalną liczbę krawędzi w grafie, spośród których żadne dwie nie wychodzą z tego samego wierzchołka. {Maksymalna klika} Maksymalna klika, to największy podgraf grafu, w którym wszystkie pary wierzchołków są ze sobą połączone. Dostępne są dwa algorymy wyznaczania maksymalnej kliki - przybliżony i dokładny. W obu powyższych modelach krawędzie nie muszą mieć określonych parametrów liczbowych. ------------------------------------ [Pomoc] - POMOC PODRĘCZNA ------------------------------------