Теория графов. Внешне устойчивые множества , помогите разобраться

Здравствуйте!
Проверьте, пожалуйста, решение одной задачи. Я её (как мне кажется) решил. Но сильно сомневаюсь в правильности решения

Дан граф.

ImageShack.com

Необходимо найти все минимальные внешне устойчивые множества вершин, наименьшие доминирующие множества и число внешней устойчивости

Моё решение:

ImageShack.com

Сообщение отредактировано: new_sergei - 06.12.09, 12:54

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

Теперь по решению. Доминирующее верно - 13. Но если предположить, что просто под внешне устойчивыми понимались доминируемые, то можно найти минимальнее - 24. Потому что доминирующее - это множество вершин, от которых идут дуги во все остальные, а доминируемое - множество вершин, в которые идут дуги от всех остальных.

Формальный метод поиска использует матрицу смежности. Для доминируемых составляется конъюнкция дизъюнкций вида "номер строки | дизъюнкция номеров столбцов, в которых в этой строке единицы". Для доминирующих то же самое - но по столбцам. Потом скобки раскрываются, производятся необходимые склеивания и поглощения, после чего остается дизъюнкция конъюнкций, каждая их которых (конъюнкций) - это и есть одно искомое минимальное множество. В общем случае минимальных множеств может быть несколько, и они не обязаны иметь равную мощность. В звездном неорграфе, например, внешне устойчивых множеств два: одно - центральная вершина (мощность = 1), а другое - все периферийные (мощность = n-1). И то, и другое - минимально (потому что нельзя убрать ни одну из вершин без потери свойства устойчивости)

У Вас, например, доминируемые будут искаться так:

Цитата

(v1|v1|v4)*(v2|v4)*(v3|v2|v3)*(v4|v2)=(v1|v4)*(v2|v4)*(v2|v3)*(v2|v4)=
(v4|v1*v2)(v2|v3*v4)=v2*v4

Число доминирования, кстати, в Вашем примере будет равно числу доминируемости и равно 2.

Добавлено 06.12.09, 18:01
А "просто внешне устойчивые" можно искать, только если граф неориентированный. Это внутренней устойчивости все равно, орграф или неор.

Цитата vk @ 06.12.09, 18:00

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

Теперь по решению. Доминирующее верно - 13. Но если предположить, что просто под внешне устойчивыми понимались доминируемые, то можно найти минимальнее - 24. Потому что доминирующее - это множество вершин, от которых идут дуги во все остальные, а доминируемое - множество вершин, в которые идут дуги от всех остальных.

Формальный метод поиска использует матрицу смежности. Для доминируемых составляется конъюнкция дизъюнкций вида "номер строки | дизъюнкция номеров столбцов, в которых в этой строке единицы". Для доминирующих то же самое - но по столбцам. Потом скобки раскрываются, производятся необходимые склеивания и поглощения, после чего остается дизъюнкция конъюнкций, каждая их которых (конъюнкций) - это и есть одно искомое минимальное множество. В общем случае минимальных множеств может быть несколько, и они не обязаны иметь равную мощность. В звездном неорграфе, например, внешне устойчивых множеств два: одно - центральная вершина (мощность = 1), а другое - все периферийные (мощность = n-1). И то, и другое - минимально (потому что нельзя убрать ни одну из вершин без потери свойства устойчивости)

У Вас, например, доминируемые будут искаться так:

Цитата

(v1|v1|v4)*(v2|v4)*(v3|v2|v3)*(v4|v2)=(v1|v4)*(v2|v4)*(v2|v3)*(v2|v4)=
(v4|v1*v2)(v2|v3*v4)=v2*v4

Число доминирования, кстати, в Вашем примере будет равно числу доминируемости и равно 2.

Добавлено 06.12.09, 18:01
А "просто внешне устойчивые" можно искать, только если граф неориентированный. Это внутренней устойчивости все равно, орграф или неор.

Большое спасибо за ответ.

Хотелось бы задать Вам несколько уточняющих вопросов

1.Насчёт доминирующих/доминируемых. В задании написано, что необходимо найти именно доминирующих.

2. Я немного не понял из того, что вы написали, правильно ли всё-таки моё решение или нет? Само исходное логическое выражение и результат его преобразования верно?

3. Само логическое выражение я составлял по аналогии с тем, как оно было составлено в примере. И меня очень удивило, что оно не совпадало с тем выражением для данного случая, каким оно должно быть если использовать матрицы смежности.

1 и 2.
Вы писали:

Цитата new_sergei @ 06.12.09, 12:51

найти все минимальные внешне устойчивые множества вершин, наименьшие доминирующие множества и число внешней устойчивости

. Доминирующие Вы нашли. 13. Это верно. НО. Просто "внешне устойчивые" в орграфе найти нельзя. Можно найти только внешне устойчивые в соотнесенном неорграфе. У Вас орграф. Там могут быть либо доминируемые, либо доминирующие.

3. Покажите пример. И расскажите, как составляются логические выражения там.

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

Добавлено 09.12.09, 21:27
И не цитируйте меня целиком, трудно проматывать. Цитируйте выборочно, только то, о чем хотите спросить, ладно? Или совсем не цитируйте, раз уж мы тут тет-а-тет.

2 vk.

Большое спасибо за ответ.

На счёт моего третьего вопроса.

Вот пример, на который я ориентировался.

Сам граф



Логическое выражение



Формула, на которую ссылается пример



Как я понимаю, каждая коньюнкция здесь - это дизьюнкции тех переменных, соотнесённые вершины которым "входят" в каждую первую переменную каждой коньюнкции. Т.е., грубо говоря, в вершину 1(1-ая вершина коньюнкции) входят стрелки от 2-ой и 4-ой.

Правильно понимаете (о последнем предложении). Но это же и составляется по матрице смежности, правда? Каждый дизъюнкт состоит из номера столбца и номеров всех строк с единицами в этом столбце. Дизъюнктов столько, сколько столбцов. И это все для доминируемых внешне устойчивых. Для доминирующих то же самое - но по строкам. А для неорграфа нет деления на доминирующие и доминируемые, поскольку матрица симметрична.

Добавлено 14.12.09, 21:06
Я к тому, что если правильно составить выражение по матрице, оно совпадет с правильно составленным выражением по графу. Но по графу обычно выражения не составляют, если количество вершин больше 5. Просто неудобно