Entanglement (grafmått)

I grafteorin är intrassling av en riktad graf ett tal som mäter hur starkt grafens cykler är sammanflätade . Det definieras i termer av ett matematiskt spel där n poliser försöker fånga en rånare, som flyr längs grafens kanter. I likhet med andra grafmått, såsom cycle rank , kan vissa algoritmiska problem, t.ex. paritetsspel , effektivt lösas på grafer av bounded entanglement.

Definition

Entanglement -spelet spelas av n poliser mot en rånare på en riktad graf G . Inledningsvis är alla poliser utanför grafen och rånaren väljer en godtycklig startpunkt v för G . Längre fram rör sig spelarna i tur och ordning. I varje drag stannar poliserna antingen där de är eller placerar en av dem på den hörn som för närvarande är upptagen av rånaren. Rånaren måste flytta från sin nuvarande vertex, längs en kant, till en efterträdare som inte är upptagen av en polis. Rånaren måste röra sig om ingen polis följer efter honom. Om det inte finns någon fri efterträdare som rånaren kan flytta till, fångas hon och polisen vinner. Rånaren vinner om hon inte kan fångas, dvs om pjäsen kan fås att vara för evigt.

En graf G har entanglement n om n poliser vinner i entanglementspelet på G men n − 1 poliser förlorar spelet.

Egenskaper och applikationer

Grafer för sammantrassling noll och ett kan karakteriseras enligt följande:

• intrassling av G är 0 om och endast om G är acyklisk
• intrassling av G är 1 om och endast om G inte är acyklisk, och i varje starkt ansluten komponent av G finns det en nod vars borttagande gör komponenten acyklisk.

Entanglement har också varit en nyckeluppfattning för att bevisa att variabelhierarkin för den modala mu-kalkylen är strikt.

externa länkar

Du kan spela entanglement-spelet online på tPlay .