Dulmage – Mendelsohnův rozklad - Dulmage–Mendelsohn decomposition

v teorie grafů, Dulmage – Mendelsohnův rozklad je oddíl vrcholů a bipartitní graf do podmnožin, s vlastností, že dva sousední vrcholy patří do stejné podmnožiny právě tehdy, když jsou spolu spárovány perfektní shoda grafu. Je pojmenována po A. L. Dulmage a Nathan Mendelsohn, který jej publikoval v roce 1958. Zobecněním jakéhokoli grafu je Edmonds – Gallaiův rozklad, za použití Blossom algoritmus.

Hrubý rozklad

Nechat G = (X + Y,E) být bipartitní graf, a nechť D být množina vrcholů v G které nejsou spárovány alespoň v jednom maximální shoda z G. Pak D je nutně nezávislá sada, tak G lze rozdělit na tři části:

  • Vrcholy dovnitř D ∩ X a jejich sousedé;
  • Vrcholy dovnitř D ∩ Y a jejich sousedé;
  • Zbývající vrcholy.

Každé maximum shody G se skládá ze shody v první a druhé části, které odpovídají všem sousedům D, společně s a perfektní shoda zbývajících vrcholů.

Alternativní hrubý rozklad

Alternativní definice hrubého rozkladu je uvedena v [1] (připisuje se [2] kdo to zase připisuje [3]).

Nechat G být bipartitní graf, M maximální shoda v G, a PROTI0 množina vrcholů G bezkonkurenční M („volné vrcholy“). Pak G lze rozdělit na tři části:

Rozklad E-O-U
  • E - dokonce vrcholy - vrcholy dosažitelné z PROTI0 podle M-střídavá dráha rovnoměrné délky.
  • Ó - zvláštní vrcholy - vrcholy dosažitelné z PROTI0 podle M- alternativní cesta liché délky.
  • U - nedosažitelný vrcholy - vrcholy nedosažitelné z PROTI0 podle M- alternativní cesta.

Ilustrace je zobrazena vlevo. Tučné čáry jsou okraje M. Slabé čáry jsou další hrany G. Červené tečky jsou vrcholy bezkonkurenční M.

Na základě tohoto rozkladu lze hrany v G rozdělit na šest částí podle jejich koncových bodů: E-U, E-E, O-O, O-U, E-O, U-U. Tento rozklad má následující vlastnosti: [2]

  1. Sady E, Ó, U jsou párově disjunktní.
  2. Sady E, Ó, U nezávisí na maximální shodě M (tj. jakékoli maximum shody definuje přesně stejný rozklad).
  3. G obsahuje pouze O-O, O-U, E-O a U U hrany.
  4. Jakékoli maximum shody v G obsahuje pouze E-O a U U hrany.
  5. Jakékoli maximum shody v G nasycuje všechny vrcholy v Ó a všechny vrcholy v U.
  6. Velikost maximální shody v G je |Ó| + |U| / 2.

Jemný rozklad

Třetí sadu vrcholů v hrubém rozkladu (nebo všechny vrcholy v grafu s dokonalou shodou) lze navíc rozdělit do podmnožin pomocí následujících kroků:

  • Najděte perfektní shodu G.
  • Formulář a řízený graf H jehož vrcholy jsou shodné hrany G. Pro každou nepřekonatelnou hranu (x, y) v G, přidejte směrovanou hranu dovnitř H od uzavřeného okraje X k uzavřenému okraji y.
  • Najít silně připojené komponenty výsledného grafu.
  • Pro každou složku H, tvoří podmnožinu rozkladu Dulmage – Mendelsohn skládající se z vrcholů v G což jsou koncové body hran v komponentě.

Chcete-li vidět, že toto dělení na podskupiny charakterizuje hrany, které patří k dokonalým shodám, předpokládejme, že dva vrcholy X a y v G patří do stejné podmnožiny rozkladu, ale již se s nimi neshoduje počáteční perfektní shoda. Pak existuje silně propojená součást v H obsahující hranu x, y. Tato hrana musí patřit a jednoduchý cyklus v H (podle definice silné konektivity), která nutně odpovídá střídavému cyklu v G (cyklus, jehož hrany se střídají mezi spárovanými a nepřizpůsobenými hranami). Tento střídavý cyklus může být použit k úpravě počáteční dokonalé shody tak, aby vznikl nový shoda obsahující hranux, y.

Okraj x, y grafu G patří ke všem dokonalým spojením G, právě když X a y jsou jedinými členy jejich množiny v rozkladu. Taková výhoda existuje tehdy a jen tehdy, když odpovídající vyloučení číslo grafu je jedna.

Jádro

Jako další složku rozkladu Dulmage – Mendelsohn definovali Dulmage a Mendelsohn jádro grafu jako spojení jeho maximálních shod.[4] Tuto koncepci je však třeba odlišovat od jádro ve smyslu grafových homomorfismů a z k-jádro vzniklé odstraněním vrcholů nízkého stupně.

Aplikace

Tento rozklad byl použit k rozdělení sítí do analýza konečných prvků a určovat zadané, nespecifikované a nadspecifikované rovnice v soustavách nelineárních rovnic.

Reference

  1. ^ (PDF) http://www.cse.iitm.ac.in/~meghana/matchings/bip-decomp.pdf. Chybějící nebo prázdný | název = (Pomoc)
  2. ^ A b Irving, Robert W .; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (01.10.2006). Msgstr "Maximálně odpovídající pozice". Transakce ACM na algoritmech. 2 (4): 602–610. doi:10.1145/1198513.1198520.
  3. ^ Pulleyblank, W.R. (1995). "Shody a rozšíření". Příručka kombinatoriky. Amsterdam, Severní Holandsko: Elsevier Science. 179–232.
  4. ^ Harary, Franku; Plummer, Michael D. (1967), „Na jádru grafu“, Proceedings of the London Mathematical SocietyTřetí série, 17: 305–314, doi:10,1112 / plms / s3-17.2.305, PAN  0209184.

externí odkazy

  • Dobré vysvětlení jeho aplikace na systémy nelineárních rovnic je k dispozici v tomto článku: [1]
  • Implementace algoritmu open source je k dispozici jako součást knihovny řídkých matic: SPOLICE
  • Graficko-teoretické aspekty řešení omezení v projektu SST: [2]