Zapletení (míra grafu) - Entanglement (graph measure)

v teorie grafů, zapletení a řízený graf je číslo měřící, jak silně se cykly grafu prolínají. Je definována v pojmech a matematická hra ve kterémn policisté se pokusí zajmout lupiče, který unikne po okrajích grafu. Podobně jako u jiných grafických opatření, jako je hodnost cyklu, některé algoritmické problémy, např. paritní hra, lze efektivně řešit na grafech omezeného zapletení.

Definice

The zapletená hra[1] hraje n policisté proti lupiči ona řízený graf G. Zpočátku jsou všichni policajti mimo graf a lupič vybere libovolný počáteční vrcholproti z G. Dále se hráči pohybují postupně. Při každém pohybu policajti buď zůstanou tam, kde jsou, nebo jednoho z nich umístí na vrchol, který aktuálně okupuje lupič. Lupič se musí přesunout ze svého současného vrcholu podél hrany k nástupci, který není obsazen policajtem. Lupič se musí pohnout, pokud ho žádný policista nenásleduje. Pokud neexistuje žádný volný nástupce, ke kterému by se lupič mohl přestěhovat, je chycena a policajti vyhrají. Lupič vyhraje, pokud jej nelze chytit, tj. Pokud lze hru nechat hrát navždy.

Graf G má zapletení n -li n policajti vyhrávají ve hře zapletení G ale n - 1 policista prohrává hru.

Vlastnosti a aplikace

Grafy zapletení nula a jedna lze charakterizovat následovně:[1]

  • zapletení G je 0 právě tehdy G je acyklický
  • zapletení G je 1 právě tehdy G není acyklický a ve všech silně připojená součást z G existuje uzel, jehož odstranění způsobí, že komponenta bude acyklická.

Zapletení bylo také klíčovým pojmem při dokazování, že proměnná hierarchie modálu mu kalkul je přísný.[2]

Reference

  1. ^ A b D. Berwanger a E. Grädel,Zapletení - opatření pro složitost směrovaných grafů s aplikacemi pro logiku a hry Sborník ze dne LPAR '04, roč. 3452 z LNCS, s. 209–223 (2004)
  2. ^ D. Berwanger, E. Grädel a G. Lenzi,Variabilní hierarchie mu-kalkulu je přísná, Theory of Computing Systems, roč. 40, s. 437–466 (2007)

externí odkazy

Zapletenou hru můžete hrát online na Přehrát.