Перейти к содержанию

Запутанность (теория графов)

Статья из Авикипедии. Энциклопедии

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

Определение[править | править код]

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

Запутанность графа G равна n, если n полицейских гарантированно ловят грабителя в этой игре, а n−1 полицейских для этого недостаточно.

Свойства и приложения[править | править код]

Графы с нулевой и единичной запутанностью допускают следующее описание:

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

Кроме того, концепция запутанности сыграла важную роль в доказательстве строгости иерархии переменной квантификации.

Примечания[править | править код]

Ссылки[править | править код]

Онлайн-версия игры доступна по адресу: [указать ссылку, если известна].

Ссылки[править | править код]