Запутывание (графическая мера)

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

Определение

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

Граф G имеет запутанность n , если n полицейских выигрывают в игре с запутанностью на G, но n - 1 копов проигрывают.

Свойства и применение

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

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

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

Внешние ссылки

Вы можете сыграть в игру «Запутанность» онлайн на tPlay .