Entanglement (graph measure)
Encyclopedia
In graph theory
, entanglement of a directed graph
is a number measuring how strongly
the cycles of the graph are intertwined. It is defined in terms of a mathematical game
in which
n cops try to capture a robber, who escapes along the edges of the graph. Similar to other
graph measures, such as cycle rank
, some algorithmic problems, e.g. parity game
, can be
efficiently solved on graphs of bounded entanglement.
a directed graph G. Initially, all cops are outside the graph and the robber selects an arbitrary starting vertex
v of G. Further on, the players move in turn. In each move the cops either stay where they are, or place one
of them on the vertex currently occupied by the robber. The robber must move from her current vertex, along an edge,
to a successor that is not occupied by a cop. The robber must move if no cop is following him. If there is
no free successor to which the robber can move, she is caught, and the cops win. The robber wins if she
cannot be caught, i.e. if the play can be made to last forever.
A graph G has entanglement n if n cops win in the entanglement game on G but n − 1 cops lose the game.
Entanglement has also been a key notion in proving that the variable hierarchy
of the modal mu calculus is strict.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, entanglement of a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
is a number measuring how strongly
the cycles of the graph are intertwined. It is defined in terms of a mathematical game
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
in which
n cops try to capture a robber, who escapes along the edges of the graph. Similar to other
graph measures, such as cycle rank
Cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close adigraph is to a directed acyclic graph , in the sense that a DAG has...
, some algorithmic problems, e.g. parity game
Parity game
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of finitely many natural numbers. Two players, 0 and 1, take turns moving a token along the edges of the graph, resulting in a path, called the play.The winner of a finite play is the...
, can be
efficiently solved on graphs of bounded entanglement.
Definition
The entanglement game is played by n cops against a robber ona directed graph G. Initially, all cops are outside the graph and the robber selects an arbitrary starting vertex
v of G. Further on, the players move in turn. In each move the cops either stay where they are, or place one
of them on the vertex currently occupied by the robber. The robber must move from her current vertex, along an edge,
to a successor that is not occupied by a cop. The robber must move if no cop is following him. If there is
no free successor to which the robber can move, she is caught, and the cops win. The robber wins if she
cannot be caught, i.e. if the play can be made to last forever.
A graph G has entanglement n if n cops win in the entanglement game on G but n − 1 cops lose the game.
Properties and applications
Graphs of entanglement zero and one can be characterized as follows:- entanglement of G is 0 if and only if G is acyclicDirected acyclic graphIn mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
- entanglement of G is 1 if and only if G is not acyclic, and in every strongly connected componentStrongly connected componentA directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
of G there is a node whose removal makes the component acyclic.
Entanglement has also been a key notion in proving that the variable hierarchy
of the modal mu calculus is strict.