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