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

[new_sergei]

Здравствуйте!
Проверьте, пожалуйста, решение одной задачи.

Дан граф.



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


Логическое выражение для минимальных внешне устойчивых множеств вершин имеет вид
$% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacqaH1o % qzdaWgaaWcbaGaaGymaaqabaGccqGHIaYTdaqadaqaaiabew7aLnaa % BaaaleaacaaIZaaabeaakiaadAfacqaH1oqzdaWgaaWcbaGaaGinaa % qabaGccaWGwbGaeqyTdu2aaSbaaSqaaiaaikdaaeqaaaGccaGLOaGa % ayzkaaGaeyOiGCRaeqyTdu2aaSbaaSqaaiaaiodaaeqaaOGaeyOiGC % 7aaeWaaeaacqaH1oqzdaWgaaWcbaGaaGinaaqabaGccaWGwbGaeqyT % du2aaSbaaSqaaiaaigdaaeqaaOGaamOvaiabew7aLnaaBaaaleaaca % aIYaaabeaaaOGaayjkaiaawMcaaiabg2da9maabmaabaGaeqyTdu2a % aSbaaSqaaiaaisdaaeqaaOGaamOvaiabew7aLnaaBaaaleaacaaIYa % aabeaaaOGaayjkaiaawMcaaiabgkci3oaabmaabaGaeqyTdu2aaSba % aSqaaiaaiodaaeqaaOGaamOvaiabew7aLnaaBaaaleaacaaIXaaabe % aaaOGaayjkaiaawMcaaiabgkci3oaabmaabaGaeqyTdu2aaSbaaSqa % aiaaiodaaeqaaOGaeyOiGCRaeqyTdu2aaSbaaSqaaiaaigdaaeqaaa % GccaGLOaGaayzkaaGaeyypa0ZaaeWaaeaacqaH1oqzdaWgaaWcbaGa % aGinaaqabaGccaWGwbGaeqyTdu2aaSbaaSqaaiaaikdaaeqaaaGcca % GLOaGaayzkaaGaeyOiGC7aaeWaaeaacqaH1oqzdaWgaaWcbaGaaG4m % aaqabaGccqGHIaYTcqaH1oqzdaWgaaWcbaGaaGymaaqabaGccaWGwb % GaeqyTdu2aaSbaaSqaaiaaigdaaeqaaOGaeyOiGCRaeqyTdu2aaSba % aSqaaiaaiodaaeqaaaGccaGLOaGaayzkaaGaeyypa0dabaGaeyypa0 % ZaaeWaaeaacqaH1oqzdaWgaaWcbaGaaGinaaqabaGccaWGwbGaeqyT % du2aaSbaaSqaaiaaikdaaeqaaaGccaGLOaGaayzkaaGaeyOiGC7aae % WaaeaacqaH1oqzdaWgaaWcbaGaaGymaaqabaGccqGHIaYTcqaH1oqz % daWgaaWcbaGaaG4maaqabaaakiaawIcacaGLPaaacqGH9aqpcqaH1o % qzdaWgaaWcbaGaaGymaaqabaGccqGHIaYTcqaH1oqzdaWgaaWcbaGa % aG4maaqabaGccqGHIaYTcqaH1oqzdaWgaaWcbaGaaGinaaqabaGcca % WGwbGaeqyTdu2aaSbaaSqaaiaaigdaaeqaaOGaeyOiGCRaeqyTdu2a % aSbaaSqaaiaaikdaaeqaaOGaeyOiGCRaeqyTdu2aaSbaaSqaaiaaio % daaeqaaOGaai4oaaaaaa!B6F5! \[ \begin{array}{l} \varepsilon _1 \bullet \left( {\varepsilon _3 V\varepsilon _4 V\varepsilon _2 } \right) \bullet \varepsilon _3 \bullet \left( {\varepsilon _4 V\varepsilon _1 V\varepsilon _2 } \right) = \left( {\varepsilon _4 V\varepsilon _2 } \right) \bullet \left( {\varepsilon _3 V\varepsilon _1 } \right) \bullet \left( {\varepsilon _3 \bullet \varepsilon _1 } \right) = \left( {\varepsilon _4 V\varepsilon _2 } \right) \bullet \left( {\varepsilon _3 \bullet \varepsilon _1 V\varepsilon _1 \bullet \varepsilon _3 } \right) = \\ = \left( {\varepsilon _4 V\varepsilon _2 } \right) \bullet \left( {\varepsilon _1 \bullet \varepsilon _3 } \right) = \varepsilon _1 \bullet \varepsilon _3 \bullet \varepsilon _4 V\varepsilon _1 \bullet \varepsilon _2 \bullet \varepsilon _3 ; \\ \end{array} \] $

Значит, минимальные внешне устойчивые множества вершин - это $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiWaaeaaca % WG2bWaaSbaaSqaaiaaigdaaeqaaOGaaiilaiaadAhadaWgaaWcbaGa % aG4maaqabaGccaGGSaGaamODamaaBaaaleaacaaI0aaabeaaaOGaay % 5Eaiaaw2haaaaa!3F47! \[ \left\{ {v_1 ,v_3 ,v_4 } \right\} \] $ и $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiWaaeaaca % WG2bWaaSbaaSqaaiaaigdaaeqaaOGaaiilaiaadAhadaWgaaWcbaGa % aGOmaaqabaGccaGGSaGaamODamaaBaaaleaacaaIZaaabeaaaOGaay % 5Eaiaaw2haaaaa!3F45! \[ \left\{ {v_1 ,v_2 ,v_3 } \right\} \] $

Далее, я так понимаю, наименьшее доминирующее множество - (в данном случае оо будет только одно?) - это $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiWaaeaaca % WG2bWaaSbaaSqaaiaaigdaaeqaaOGaaiilaiaadAhadaWgaaWcbaGa % aG4maaqabaaakiaawUhacaGL9baaaaa!3CA8! \[ \left\{ {v_1 ,v_3 } \right\} \] $

И, соответственно, число внешней устойчивости равно 2.

Правильно ли это?