Запутанность (мера графика) - Entanglement (graph measure)

В теория графов, запутанность из ориентированный граф - это число, измеряющее, насколько сильно переплетены циклы графа. Он определяется как математическая игра в которомп Менты пытаются поймать грабителя, который убегает по краям графа. Подобно другим мерам графа, таким как ранг цикла, некоторые алгоритмические проблемы, например паритетная игра, может быть эффективно решена на графах ограниченной зацепленности.

Определение

В игра в запутанность[1] играет п копы против грабителя на направленном графе грамм. Изначально все копы находятся за пределами графа и грабитель выбирает произвольную стартовую вершинуv из грамм. Далее игроки ходят по очереди. На каждом ходу полицейские либо остаются на месте, либо помещают одного из них в вершину, занятую в данный момент грабителем. Грабитель должен перейти от своей текущей вершины по ребру к преемнику, который не занят копом. Грабитель должен двигаться, если за ним не идет ни один полицейский. Если нет свободного преемника, к которому грабитель может перейти, ее ловят, и полицейские побеждают. Грабитель побеждает, если ее нельзя поймать, т.е. если игра может длиться вечно.

График грамм запутался п если п полицейские побеждают в игре на запутывание грамм но п - 1 полицейский проиграл игру.

Свойства и приложения

Графы нулевой и единицы запутанности можно охарактеризовать следующим образом:[1]

  • запутывание грамм равно 0 тогда и только тогда, когда грамм является ациклический
  • запутывание грамм равно 1 тогда и только тогда, когда грамм не ацикличен, и в каждом компонент сильной связности из грамм есть узел, удаление которого делает компонент ациклическим.

Запутанность также была ключевым понятием в доказательстве того, что иерархия переменных модального мю-исчисление строго.[2]

Рекомендации

  1. ^ а б Д. Бервангер и Э. Гредель,Запутанность - мера сложности ориентированных графов с приложениями к логике и играм, Труды LPAR '04, т. 3452 из LNCS, стр. 209–223 (2004).
  2. ^ Д. Бервангер, Э. Гредель и Г. Ленци,Иерархия переменных мю-исчисления строгая., Теория вычислительных систем, т. 40. С. 437–466 (2007).

внешняя ссылка

Вы можете играть в игру запутывания онлайн на tPlay.