BD-2st-1.2-w08.tresc-1.1-Slajd38
Graf uszeregowalności (2)
Można pokazać, że dana realizacja r(T ) jest uszeregowalna wtedy i tylko wtedy, gdy można skonstruować dla niej acykliczny skierowany graf uszeregowalności SG(r(T )). Problem weryfikacji, czy dana realizacja jest uszeregowalna, jest problemem NP.-zupełnym, to znaczy, problemem obliczeniowo trudnym. Trudność weryfikacji krytetium uszeregowalności wynika z konstrukcji tego grafu. Z definicji grafu uszeregowalności wynika, że wynikowy graf jest poligrafem (patrz warunek 2). Z teorii grafów wynika, że weryfikacja czy dany poligraf zawiera cykl jest problemem NP.-zupełnym. Stąd, w praktyce, kryterium uszeregowalności zastąpiono łatwiejszym do weryfikacji kryterium konfliktowej uszeregowalności. Problem weryfikacji, czy dana realizacja jest realizacją konfliktowo-uszeregowalną jest problemem obliczeniowo łatwym (problem należy do klasy problemów P).
