Wykres moralny
W teorii grafów graf moralny jest używany do znajdowania równoważnej nieskierowanej formy skierowanego grafu acyklicznego . Jest to kluczowy krok algorytmu drzewa połączeń , wykorzystywanego w propagacji przekonań na modelach graficznych .
Umoralniony odpowiednik skierowanego grafu acyklicznego jest tworzony przez dodanie krawędzi między wszystkimi parami niesąsiadujących węzłów, które mają wspólnego potomka, a następnie uczynienie wszystkich krawędzi grafu niekierowanymi. Równoważnie, graf moralny skierowanego acyklicznego grafu G jest grafem nieskierowanym, w którym każdy węzeł pierwotnego G jest teraz połączony ze swoim kocem Markowa . Nazwa wywodzi się z faktu, że w grafie moralnym dwa węzły, które mają wspólne dziecko, muszą zostać połączone przez dzielenie krawędzi.
Moralizację można również zastosować do grafów mieszanych , zwanych w tym kontekście „wykresami łańcuchowymi”. W grafie łańcuchowym spójny składnik podgrafu nieskierowanego nazywany jest łańcuchem. Moralizacja dodaje nieukierunkowaną krawędź między dowolnymi dwoma wierzchołkami, z których oba mają krawędzie wychodzące z tego samego łańcucha, a następnie zapomina o orientacji skierowanych krawędzi grafu.
Słabo rekurencyjnie uproszczone
Graf jest słabo rekurencyjnie uproszczony, jeśli ma wierzchołek uproszczony , a podgraf po usunięciu wierzchołka uproszczonego i niektórych krawędzi (prawdopodobnie żadnej) między jego sąsiadami jest słabo rekurencyjnie uproszczony. Wykres jest moralny wtedy i tylko wtedy, gdy jest słabo rekurencyjnie uproszczony.
Graf akordowy (inaczej rekurencyjny uproszczony) jest szczególnym przypadkiem słabo rekurencyjnego uproszczenia, gdy żadna krawędź nie jest usuwana podczas procesu eliminacji. Dlatego wykres akordowy jest również moralny. Ale wykres moralny niekoniecznie jest akordowy.
Rozpoznawanie wykresów moralnych
W przeciwieństwie do grafów akordowych, które można rozpoznać w czasie wielomianowym, Verma i Pearl (1993) udowodnili, że decyzja o tym, czy graf jest moralny, jest NP-zupełna.
Zobacz też
- Verma, TS; Pearl, J. (1993), „Decydowanie o moralności grafów jest NP-zupełne”, Niepewność w sztucznej inteligencji : 391–399, arXiv : 1303,1501 , doi : 10.1016 / B978-1-4832-1451-1.50052-4 , ISBN 9781483214511 , S2CID 14690613 .