|
|
| (не показано 13 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| − | <big>Цыганова Светлана, 974гр.</big>
| |
| − |
| |
| − | '''Задача'''
| |
| | Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе. | | Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе. |
| | | | |
| − | '''Решение'''
| |
| − |
| |
| − | 1) Клика -> упаковка.
| |
| − | Пусть у нас задан граф на n вершинах, на котором необходимо найти максимальную клику. Сведем задачу к задаче нахождения максимального числа попарно несересекающихся множеств. Для этого воспользуемся тем фактом, что множество вершин независимо тогда и только тогда, когда оно является кликой в дополнении графа. Тогда будем действовать по следующему алгоритму:
| |
| − |
| |
| − | a) Построим дополнение к исходному графу (Это займет полиномиальное время, например, самый простой способ займет <latex>$n^2$</latex>).
| |
| − |
| |
| − | б) Найдем на графе-дополнении максимальное число попарно непересающихся подмножеств на, где каждое подмножество обозначается отдельной вершиной. Если какие-то два подмножества пересекаются, это значит, что они соединены ребром на графе.
| |
| − |
| |
| − | в) Полученные непересекающиеся подмножества образуют клику в исходном графе. Очевидно, что если мы искали максимальное число попарно непересекающихся подмножеств, то и соответствующая им клика тоже будет максимальной. Итого задача о нахождении максимальной клики сводится за полиномиальное время к задаче об упаковке.
| |
| − |
| |
| − | 2) Упаковка -> клика. Пусть есть некоторый набор из n подмножеств. Пронумеруем их от 1 до n. Построим граф "пересекаемости множеств". Каждая вершина графа будет обозначать собой множество, и вершины будут соединены, если множества пересекаются.
| |
| | | | |
| − | После построения графа будем строить дополнение к нему и искать максимальную клику в графе-дополнении. Вершины, входящие в максимальную клику, будут теми попарно непересекающимися множествами, которые надо было найти. Итого задача об упаковки сводится к задаче о нахождении максимальной клики. Покажем, что это действительно полиномиальное сведение: граф строится за <latex> $n^2$</latex>, дополнение к нему - за <latex> $n^2$</latex>. Итого за <latex> $n^2$</latex> операций одну задачу можно свести к другой.
| + | <!--Вообще-то, решения уже есть--> |
| | | | |
| − | [[Category:На проверку]] | + | [[Категория:Решенные задачи]] |
Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.