Помогите разобраться с кликой графа

[ZhenyaKa]

Читаю кучу теории и никак не пойму.
вот в этом файле (http://itas.pstu.ru/data/docs-dm/posobie/file2.doc) есть следующие выкладки:


никак не могу понять, почему BDEF - клика, а CDEF - не клика, хотя тоже размером 4 вершины. может есть какие-нить более понятные объяснения?

[Maslov]

Клика - это максимальный полный подграф. Т.е., в клике все вершины попарно связаны. В {B,D,E,F} это требование выполняется, а в {C,D,E,F} - нет (отсутствует ребро CD).

[ZhenyaKa]

Maslov в сообщении #251133 писал(а):

Клика - это максимальный полный подграф. Т.е., в клике все вершины попарно связаны. В {B,D,E,F} это требование выполняется, а в {C,D,E,F} - нет (отсутствует ребро CD).

это понятно, но зачем тогда эта свистопляска с матрицами? если можно по графу определить.

просто у меня задача покрупнее. мне надо найти клику графа из 10 вершин. мне тоже его потом разглядывать - удовлетворяет или нет?

а если граф вообще тока матрицей задан - обязательно придется рисовать?

[Dementor]

Цитата:

а если граф вообще тока матрицей задан - обязательно придется рисовать?

В матрице смежности исходного графа на пересечении строки C и столбца D пустое место.

[ZhenyaKa]

Dementor в сообщении #251139 писал(а):

Цитата:

а если граф вообще тока матрицей задан - обязательно придется рисовать?

В матрице смежности исходного графа на пересечении строки C и столбца D пустое место.

то есть надо еще все конъюкты проверить по матрице смежности?
в алгоритме про это ничего не сказано:



на шаге 3 написано, что множества дают "ВСЕВОЗМОЖНЫЕ ПОЛНЫЕ ПОДГРАФЫ".
но CDEF им никак не является же.

[Maslov]

ZhenyaKa в сообщении #251140 писал(а):

на шаге 3 написано, что множества дают "ВСЕВОЗМОЖНЫЕ ПОЛНЫЕ ПОДГРАФЫ".
но CDEF им никак не является же.

Хотелось бы понять, откуда такой алгоритм взялся. {A,B,D} тоже не является полным подграфом.

[ZhenyaKa]

Maslov в сообщении #251145 писал(а):

ZhenyaKa в сообщении #251140 писал(а):

на шаге 3 написано, что множества дают "ВСЕВОЗМОЖНЫЕ ПОЛНЫЕ ПОДГРАФЫ".
но CDEF им никак не является же.

Хотелось бы понять, откуда такой алгоритм взялся. {A,B,D} тоже не является полным подграфом.

ну это все, что я нашел.

а так в задании рекомендуют воспользоваться алгоритмом Магу-Уэйсмана.



эту задачу я и сам разгрызу, если знать с какой стороны ее грызть

[Maslov]

ZhenyaKa в сообщении #251163 писал(а):

эту задачу я и сам разгрызу, если знать с какой стороны ее грызть

Алгоритмы поиска клик много где описаны, например:
Н.Кристофидес. ТЕОРИЯ ГРАФОВ Алгоритмический подход.
Э.Рейнгольд, Ю.Нивергельт, Н.Део. Комбинаторные алгоритмы.
А.Н.Мелихов, Л.С.Берштейн, В.М.Курейчик. Применение графов для проектирования дискретных устройств.

Все есть в электронном виде. В последней книге кратко описан алгоритм Магу.

[ShMaxG]

ZhenyaKa
Я кажется разобрался.

1) Они ошиблись.

2) Почему они ошиблись: согласно алгоритму, надо найти множество внутренней устойчивости.

Вот у Вас соответствующая форма:

$\[AC \vee CDEF \vee ABD \vee BDEF\]$

Для того, чтобы получить множество внутренней устойчивости, надо, цитирую,

Цитата:

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

.

Так что получим на самом деле $\[FEDB \vee AB \vee EFC \vee AC\]$. И клика, соответственно, $\[FEDB\]$.

3) Очевидно, мы не получили ВСЕ возможные полные подграфы. Но их можно получить из того же множества внутренней устойчивости. Это множество: $\[\{ F,E,D,B\} ,\{ A,B\} ,\{ E,F,C\} ,\{ A,C\} \]$. Берете какую-нибудь скобку, где больше двух точек. Любые две точки из этого множества в исходном графе соединены, любые три будут составлять полный подграф и т.д.

4) Но для получения клики достаточно не влезать внутрь этих фигурных скобок.

5) "Метода пристального вглядывания" не существует. Поэтому люди придумали впихнуть в реализацию алгоритмов матрицы. И вполне естественно от студентов требовать именно работу с матрицами, когда те используют алгоритм.

[Maslov]

ShMaxG в сообщении #251363 писал(а):

2) Почему они ошиблись: согласно алгоритму, надо найти множество внутренней устойчивости.

Вот у Вас соответствующая форма:

$\[AB \vee CDEF \vee ABD \vee BDEF\]$

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

Так что получим на самом деле $\[FEDB \vee AB \vee EFC \vee AC\]$. И клика, соответственно, $\[FEDB\]$.

ShMaxG, поясните, пожалуйста, для бестолковых, а FEDB откуда взялось? Ведь для AB недостающие вершины - FEDC.

-- Вт окт 13, 2009 19:32:11 --

Все, понял - там у Вас опечатка просто. Должно быть не $AB \vee ...$, а $AC \vee ...$

-- Вт окт 13, 2009 20:06:39 --

Осталось понять только, как Шаг 2 делается. В данном случае мы так удачно догадались, что надо из первых трех конъюнкций A выносить, из двух оставшихся - C, а потом скобки раскрывать.
А в общем случае что делать?

И зачем тут вообще матрица смежности приведена?
(Хотя матрицей смежности эту конструкция можно назвать только с большой натяжкой - для неориентированного графа матрица смежности симметрична и содержит единицы на главной диагонали)

[ZhenyaKa]

ShMaxG в сообщении #251363 писал(а):

ZhenyaKa
Я кажется разобрался.

1) Они ошиблись.
$\[AC \vee CDEF \vee ABD \vee BDEF\]$

Для того, чтобы получить множество внутренней устойчивости, надо, цитирую,

Цитата:

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

.

да. все верно. вчера озарение было. так ща методички пишут. 2 дня на эту дыбыльную задачу убил.

да еще дают граф в 10 вершин

[ShMaxG]

Maslov в сообщении #251379 писал(а):

Осталось понять только, как Шаг 2 делается. В данном случае мы так удачно догадались, что надо из первых трех конъюнкций A выносить, из двух оставшихся - C, а потом скобки раскрывать.
А в общем случае что делать?

Вот формула есть такая: $\[\left( {A \vee B} \right)\left( {C \vee D} \right) = AC \vee AD \vee BC \vee BD\]$.

Если вдруг $A=C$, то

$\[\left( {A \vee B} \right)\left( {A \vee D} \right) = AA \vee AD \vee BA \vee BD = A \vee BD\]$, что проверяется подстановкой сначала $A=0$, затем $A=1$.

-- Вт окт 13, 2009 21:59:43 --

Maslov в сообщении #251379 писал(а):

И зачем тут вообще матрица смежности приведена?
(Хотя матрицей смежности эту конструкция можно назвать только с большой натяжкой - для неориентированного графа матрица смежности симметрична и содержит единицы на главной диагонали)

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

[Maslov]

ShMaxG в сообщении #251418 писал(а):

Вот формула есть такая: $\[\left( {A \vee B} \right)\left( {C \vee D} \right) = AC \vee AD \vee BC \vee BD\]$.

Если вдруг $A=C$, то

$\[\left( {A \vee B} \right)\left( {A \vee D} \right) = AA \vee AD \vee BA \vee BD = A \vee BD\]$, что проверяется подстановкой сначала $A=0$, затем $A=1$.

Это-то понятно. Но ведь нужен алгоритм, работающий в общем случае. Мы же не можем все "вдруг" проверить.
Как мы должны в общем случае все клики искать после того, как получили матрицу смежности для дополнительного графа?
Поиск клик графа - NP-полная задача, а в приведенном примере от этой NP-полноты ничего не осталось, т.к. в шаге 2 мы угадали, как надо преобразовать исходную конъюнкцию дизъюнкций.

[Xaositect]

Maslov в сообщении #251429 писал(а):

т.к. в шаге 2 мы угадали, как надо преобразовать исходную конъюнкцию дизъюнкций.

Все здесь однозначно.
Сначала раскрываем все скобки.
Потом применяем правило $XX = X$, пока можем
Потом применяем правило $X\vee XY = X$, пока можем.

Это частный случай стандартного алгоритм приведения КНФ к сокращенной ДНФ

[Maslov]

Xaositect в сообщении #251503 писал(а):

Все здесь однозначно.
Сначала раскрываем все скобки.
Потом применяем правило $XX = X$, пока можем
Потом применяем правило $X\vee XY = X$, пока можем.

Это частный случай стандартного алгоритм приведения КНФ к сокращенной ДНФ

Спасибо! Теперь понятно, куда экспоненциальную сложность спрятали