Число внешней устойчивости графа кратко

Привет, сегодня поговорим про число внешней устойчивости графа, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое число внешней устойчивости графа, множество внешней устойчивости , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

Множество ТМX называется внешне устойчивым в графе (Х,Г), если для каждой вершины хПТ существует хотя бы один образ во множестве Т. Числоb(G) = называется числом внешней устойчивости.

Прежде чем определить понятие внешней устойчивости(external stability ), введем правила покрытия графа.

Любая вершина покрывает:

• саму себя;
• смежные вершины;
• инцидентные ребра.

Любое ребро покрывает:

• само себя;
• смежные ребра;
• инцидентные вершины.

Вершинное число внешней устойчивости – минимальная мощность множества вершин, покрывающих все вершины графа, обозначается 0.

Реберное число внешней устойчивости – минимальная мощность множества ребер, покрывающих все ребра графа, обозначается 1. В общем случае число вершинной внешней устойчивости изменяется от n (у пустых графов на n вершинах) до 1 (у полных графов на n вершинах).

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

Примеры: сколько можно поставить ферзей (рис.12) или других фигур, чтобы все поля доски были под ударом (5 ферзей, 8 ладей или слонов, 12 коней), сколько наблюдателей поставить на пересечениях улиц, чтобы все перекрестки были под присмотром.

Существует достаточно простой алгоритм поиска минимального внешне устойчивого множества. Об этом говорит сайт https://intellect.icu . Для графа G=(X,Г) (см. рис.13a) строим граф (X, ,D), где определено отображение D множества X в так, что , если у=x или y является прообразом х (уОГ^-1х) (рис.13b).

Дальнейшие действия:

1. удаляем из (X, , D) вершины х такие, что Dх М Dу для у№х (здесь мы удаляем c,d,f) и исходящие из них ребра;
2. если обнаружится "висячее ребро" (х, ), включаем х в искомое множество Т и удаляем эту вершину и ее образы (здесь а ОТ и из графа исключаетсяа и Dа={};
   
   Рис. 13
3. повторяем предшествующие пункты до тех пор, пока не обнаружится невозможность дальнейшего приведения;
4. одну из оставшихся вершин (например, b) включаем во множество Т и исключаем ее образы Db={};
5. повторяем предшествующие пункты и получаем либо Т=(a,b,e) или Т=(a,b,g).

Пусть - некоторый граф. Подмножество вершин называется множеством внешней устойчивости, если
1)
2)

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

Пример

Множества внешней устойчивости:

Вау!! 😲 Ты еще не читал? Это зря!

• Устойчивость графа
• Внешняя устойчивость орграфа
• граф ма тика ,
• теория графов , графы , граф ,
• число внутренней устойчивости графа ,

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