Grafy doskonałe metodą dziur nieparzystych w automatycznej syntezie sterowników logicznych

摘要

Obserwowany rozwój elektroniki i wszechobecna miniaturyzacja, objawiającą się coraz większą ilością urządzeń realizujących coraz bardziej skomplikowane zadania. Rozwój pociąga za sobą konieczność opracowywania nowych, bardziej efektywnych metod panowania nad ogromem zależności. Złożoność układów dawno przerosła możliwości pojedynczej osoby i obecnie takimi zadaniami obciąża się specjalizowane systemy komputerowe, jednak tego typu system należy odpowiednio przygotować. Pożądane jest, aby dawał wyniki optymalne w jak najkrótszym czasie. Złożoność problemów występujących w czasie automatycznego przygotowania układów cyfrowych powoduje, że w praktyce stosowane są algorytmy heurystyczne, dające wyniki przybliżone i nie zawsze w najkrótszym możliwym czasie. Pogoń za nowymi rozwiązaniami doprowadziła do pomysłu wykorzystania grafów doskonałych, które przez swoje własności pozwalają zmniejszyć wymagania czasowe a zatem i wymaganą moc obliczeniową, dając w zamian wyniki optymalne. Algorytmy wykorzystujące specyficzne własności grafów doskonałych charakteryzują się złożonością obliczeniową na poziomie wielomianowym. Zanim można będzie operować na grafach doskonałych należy sprawdzić czy dany graf jest grafem doskonałym. Najnowsze prace wskazują, że grafy doskonałe można rozpoznawać (pośród innych metod) z użyciem algorytmów wyszukiwania dziur nieparzystych. Jednocześnie obserwuje się, że znacząca większość grafów opisujących rzeczywiste układy zawiera się w podklasach grafów doskonałych. W roku 1960, Claude Berge wysunął tezę mówiącą ze graf jest doskonały wtedy i tylko wtedy, gdy nie zawiera ani dziur nieparzystych ani anty-dziur nieparzystych. Teza jest znana jako Strong Perfect Graph Conjecture. (Chvatal i Sbihi zaproponowali nazwę grafu Bergea) wg propozycji Dziura natomiast, jest bezcięciwowym cyklem o długości przynajmniej cztery, zaś anty-dziura jest dopełnieniem takiego cyklu. Dziury i anty-dziury są natomiast parzyste i nieparzyste zgodnie z parzystością ich liczby wierzchołków.%This paper should to point out potential strenght of prerfect graph algorithms - specially algorithms with use of odd-hole-free graph - for automated synthesis of digital circuits. Typically known problems are NP-complete but using perfect graphs complexity is decreasing to polynomial. Studies in this matter shows that plenty of dependencies describing real sequential circuits can be described using perfect graphs. There shown the analysis of digital controller described in SFC. In analysis was used methods for testing perfect graphs.