Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 188632
12.01.2016, 17:48
0.00 руб.
12.01.2016, 18:18
0 2 1
Образование
Здравствуйте! У меня возникли сложности с таким вопросом:
Помогите найти ядро графа.


Число внутренней устойчивости графа нашёл путём приведения выражения к ДНФ (построил таблицу истинности, потом выписал для единиц парные дизъюнкции).

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

Обсуждение

давно
Гордиенко Андрей Владимирович
Мастер-Эксперт
17387
18346
17.01.2016, 09:44
общий
Адресаты:
Какое выражение Вы имеете в виду, когда пишете
Цитата: Пользователь из России
Число внутренней устойчивости графа нашёл путём приведения выражения к ДНФ
Об авторе:
Facta loquuntur.
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
17.01.2016, 20:10
общий
это ответ
Здравствуйте, Сергей В.!
Подмножество N графа G=(E, Г) будет ядром, если N - одновременно внутренне и внешне устойчивое множество, т.е.
([$8704$]Хi [$8712$] N) N [$8745$] ГХi = [$8709$],
([$8704$]Хi [$8713$] N) N [$8745$] ГХi [$8800$] [$8709$].
Соответствия для данного графа имеют следующий вид:
Г(Х1) = {X2, X3, X4}
Г(Х2) = {X1}
Г(Х3) = {X1}
Г(Х4) = {X3}
Проверим найденные множества внутренней устойчивости:
1) N = {X2,X3}
N [$8745$] Г(Х2) = {X2,X3} [$8745$] {X1} = [$8709$]
N [$8745$] Г(Х3) = {X2,X3} [$8745$] {X1} = [$8709$]
N [$8745$] Г(Х1) = {X2,X3} [$8745$] {X2, X3, X4} [$8800$] [$8709$]
N [$8745$] Г(Х4) = {X2,X3} [$8745$] {X3} [$8800$] [$8709$]
N = {X[sub]2[/sub],X[sub]3[/sub]} является ядром графа G
2) N = {X2,X4}
N [$8745$] Г(Х2) = {X2,X4} [$8745$] {X1} = [$8709$]
N [$8745$] Г(Х4) = {X2,X4} [$8745$] {X3} = [$8709$]
N [$8745$] Г(Х1) = {X2,X4} [$8745$] {X2, X3, X4} [$8800$] [$8709$]
N [$8745$] Г(Х3) = {X2,X4} [$8745$] {X1} = [$8709$] [$8658$] N = {X2,X4} не является ядром
3) N = {X1}
N [$8745$] Г(Х1) = {X1} [$8745$] {X2, X3, X4} = [$8709$]
N [$8745$] Г(Х2) = {X1} [$8745$] {X1} [$8800$] [$8709$]
N [$8745$] Г(Х3) = {X1} [$8745$] {X1} [$8800$] [$8709$]
N [$8745$] Г(Х4) = {X1} [$8745$] {X3} = [$8709$] [$8658$] N = {X1} не является ядром
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа