https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8._%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_NP,_coNP,_NPC/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/Packing%3DMaxClique&feed=atom&action=historyОбсуждение:Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Packing=MaxClique - История изменений2024-03-29T12:25:04ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8._%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_NP,_coNP,_NPC/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/Packing%3DMaxClique&diff=509&oldid=prevStasFomin: Удалено содержимое страницы2011-06-14T22:25:25Z<p>Удалено содержимое страницы</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 22:25, 14 июня 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">== Решение ==</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Представим каждое подмножество как вершину графа. Переберем все пары подмножеств, и если два подмножества не пересекаются - соединим соответствующие им вершины ребрами. Получаем граф. Максимальный подграф, состоящий из вершин, каждая из которых соединена с каждой (это и есть клика) даст нам максимальный набор подмножеств, не пересекающихся друг с другом.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:В обратную сторону задача сводится аналогичным образом. </del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Для каждой вершины v:</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:1) Проходим по всем вершинам v' != v</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:2) Если v' и v не соединены ребром (множества, соответствующие им, должны пересекаться) - добавляем в соответствующие множества уникальный элемент "v-v'", по которому они будут пересекаться друг с другом и ни с каким больше множеством. </del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Сводимость в обратную сторону построена.</del></div></td><td colspan="2"> </td></tr>
</table>StasFominhttps://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8._%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_NP,_coNP,_NPC/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/Packing%3DMaxClique&diff=508&oldid=prevFlid: Решение2011-06-14T12:07:59Z<p>Решение</p>
<p><b>Новая страница</b></p><div>== Решение ==<br />
<br />
Представим каждое подмножество как вершину графа. Переберем все пары подмножеств, и если два подмножества не пересекаются - соединим соответствующие им вершины ребрами. Получаем граф. Максимальный подграф, состоящий из вершин, каждая из которых соединена с каждой (это и есть клика) даст нам максимальный набор подмножеств, не пересекающихся друг с другом.<br />
:<br />
:В обратную сторону задача сводится аналогичным образом. <br />
Для каждой вершины v:<br />
:1) Проходим по всем вершинам v' != v<br />
:2) Если v' и v не соединены ребром (множества, соответствующие им, должны пересекаться) - добавляем в соответствующие множества уникальный элемент "v-v'", по которому они будут пересекаться друг с другом и ни с каким больше множеством. <br />
Сводимость в обратную сторону построена.</div>Flid