Запутанность (теория графов)
Запутанность ориентированного графа — это числовая характеристика, отражающая степень переплетённости циклов в графе. Данное понятие определяется через игру преследования, в которой участвуют n полицейских и один грабитель, перемещающийся по рёбрам графа. Как и другие параметры графов, например циклический ранг, запутанность позволяет эффективно решать определённые алгоритмические задачи, такие как проверка выполнимости формул логики первого порядка, на графах с ограниченным значением этого показателя.
Определение[править | править код]
Игра в запутанность разыгрывается на ориентированном графе G между n полицейскими и одним грабителем. В начальный момент все полицейские находятся вне графа, а грабитель выбирает любую вершину v в качестве стартовой. Ходы совершаются поочерёдно. На своём ходе каждый полицейский может либо оставаться на месте, либо занять вершину, где в данный момент находится грабитель. Грабитель обязан переместиться из текущей вершины в соседнюю по направлению ребра, при условии что она не занята полицейским. Даже при отсутствии преследования грабитель должен совершать ход. Если у грабителя не остаётся доступных вершин для перемещения, он считается пойманным, и победа присуждается полицейским. Грабитель выигрывает, если избегает поимки неограниченно долго.
Запутанность графа G равна n, если n полицейских гарантированно ловят грабителя в этой игре, а n−1 полицейских для этого недостаточно.
Свойства и приложения[править | править код]
Графы с нулевой и единичной запутанностью допускают следующее описание:
- Запутанность G равна 0 тогда и только тогда, когда G является ориентированным ациклическим графом.
- Запутанность G равна 1 тогда и только тогда, когда G содержит циклы, и в каждой компоненте сильной связности существует вершина, удаление которой делает эту компоненту ациклической.
Кроме того, концепция запутанности сыграла важную роль в доказательстве строгости иерархии переменной квантификации.
Примечания[править | править код]
Ссылки[править | править код]
Онлайн-версия игры доступна по адресу: [указать ссылку, если известна].