Участник:Rechique/vcover-clique — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
Задачу Clique можно свести по карпу к задаче о клике (просто перебором k). Аналогично с задачей о вершинном покрытии.
 
Задачу Clique можно свести по карпу к задаче о клике (просто перебором k). Аналогично с задачей о вершинном покрытии.
 +
 +
[[Участник:StasFomin|StasFomin]] 03:47, 16 мая 2019 (MSK): «Задачу Clique можно свести по карпу к задаче о клике (просто перебором k). Аналогично с задачей о вершинном покрытии.» Огонь. Задачу о клике можно свести к задаче о клике…  Остановитесь, прочтите условие задачи и распишите сведение по Карпу<ref>это не рыба</ref> — что вы делаете с входными данными и почему это сведение корректно.
 +
  
 
Далее сводим Clique к Indset взятием дополнения графа. А Indset и VertexCover сводятся к друг другу заменой k на n - k, где n - число вершин: если вершинное покрытие задело все ребра, то между оставшиеся вершинами ребер быть не может, иначе эти ребра не были бы задеты. И наоборот, если между оставшимися ребер нет, то все ребра покрыты взятыми.
 
Далее сводим Clique к Indset взятием дополнения графа. А Indset и VertexCover сводятся к друг другу заменой k на n - k, где n - число вершин: если вершинное покрытие задело все ребра, то между оставшиеся вершинами ребер быть не может, иначе эти ребра не были бы задеты. И наоборот, если между оставшимися ребер нет, то все ребра покрыты взятыми.
  
 
[[Категория:На проверку]]
 
[[Категория:На проверку]]

Версия 03:47, 16 мая 2019

Будем работать со следующими задачами:

1)Clique = {(G, k)| в графе есть клика размером k}

2)IndSet = {(G, k)| в графе есть независимое множество из k вершин}

3)VertexCover = {(G, k)| в графе есть вершинное покрытие из k вершин}

Задачу Clique можно свести по карпу к задаче о клике (просто перебором k). Аналогично с задачей о вершинном покрытии.

StasFomin 03:47, 16 мая 2019 (MSK): «Задачу Clique можно свести по карпу к задаче о клике (просто перебором k). Аналогично с задачей о вершинном покрытии.» Огонь. Задачу о клике можно свести к задаче о клике… Остановитесь, прочтите условие задачи и распишите сведение по Карпу[1] — что вы делаете с входными данными и почему это сведение корректно.


Далее сводим Clique к Indset взятием дополнения графа. А Indset и VertexCover сводятся к друг другу заменой k на n - k, где n - число вершин: если вершинное покрытие задело все ребра, то между оставшиеся вершинами ребер быть не может, иначе эти ребра не были бы задеты. И наоборот, если между оставшимися ребер нет, то все ребра покрыты взятыми.
  1. это не рыба