Описание тега vertex-cover

Вопросы с тегом
1 ответ

Докажите, что любое минимальное покрытие вершин клики размера n должно иметь ровно n-1 вершин.

Как доказать, что любое минимальное покрытие вершин клики размера n должно иметь ровно n-1 вершин? Спасибо
18 апр '14 в 15:19
0 ответов

Чехол Vertex для жадного подхода к дереву

Вопрос: Пусть T будет деревом с n узлами, корнем которого является некоторый узел r. Мы хотим разместить как можно меньше защитных элементов в узлах T, так что каждое ребро T охраняется: ребро между родительским узлом v и его дочерним элементом w ох…
10 дек '18 в 21:34
0 ответов

Сокращение от Vertex Cover до LP

Я хочу свести проблему покрытия вершин к конкретной проблеме решения. Это решение проблемы заключается в следующем: У меня есть nxn матрица A, вектор b в R^n и положительное целое число k. Существует ли в R^n вектор x, содержащий не более k ненулевы…
19 мар '17 в 05:54
1 ответ

Минимальный вес вершинной оболочки дерева

Существует существующий вопрос, касающийся деревьев, где вес вершины равен ее степени, но меня интересует случай, когда вершины могут иметь произвольные веса. Это не домашняя работа, но это один из вопросов в руководстве по разработке алгоритма, кот…
17 дек '14 в 00:54
0 ответов

Покрытие вершин для графов со степенью ровно 3

Ограничена ли проблема покрытия вершин графами, где все узлы имеют степень ровно 3 NP-Hard? Я знаю, что когда степень составляет не более 3, проблема является NP-сложной, но мне нужно знать сложность особого случая, когда она равна точно 3 для каждо…
27 июл '18 в 15:48
0 ответов

Покрытие вершин мощности с максимальным соответствием за полиномиальное время

Решается ли проблема покрытия вершин мощности с использованием максимального соответствия за полиномиальное время? Какой коэффициент аппроксимации? Помогите мне, пожалуйста
26 окт '17 в 09:16
1 ответ

Граф G имеет минимальное покрытие вершин размером |V| - 1 тогда и только тогда, когда G полна. Это правда?

Сетка может быть примером полной G. Где каждый узел связан с каждым другим узлом. Поэтому минимальный размер покрытия вершины для такого графа не должен быть равен 1.
12 сен '17 в 14:08
1 ответ

Как конвертировать SPOJ Quest4 в Minimum Vertex Cover

Ниже приведена проблема соответствия максимального двудольного: http://www.spoj.com/problems/QUEST4/ Через форумы я узнал, что эту проблему можно превратить в проблему минимального покрытия вершин, которая, в свою очередь, может быть решена с помощь…
09 окт '13 в 06:22
0 ответов

Ошибка "Import Main" в JavaScript. Работа с графиками и матрицами смежности

Я беру курс Udacity "Введение в теоретическую информатику", в котором рассматриваются алгоритмы, связанные с графами (то есть с вершинами и ребрами). Как часть курса, мне пришлось написать программу, которая а) проверяет, оставит ли конкретный макет…
07 авг '18 в 19:04
0 ответов

Модифицированный алгоритм покрытия вершин - может проходить только 2 вершины от исходной вершины

Я ищу алгоритм, который по существу является тем максимальным покрытием вершин, где покрытие ограничено двумя вершинами: Например Если вы выберете вершину 1, у вас может быть вершина 4, но если вы выберете 2, у вас не будет других вершин (так как вс…
01 ноя '17 в 02:07
1 ответ

Как получить минимальное покрытие вершин, когда вы можете решить, содержит ли граф покрытие вершин определенного размера?

У кого-нибудь есть идеи, как решить этот вопрос? Предположим, что в O (2 ^ k kn) можно решить, содержит ли граф с n узлами покрытие вершин максимального размера k> = 0. Покажите, что вы можете решить вариант оптимизации типа 1 задачи в O (2 ^ k n lo…
26 фев '19 в 22:48
0 ответов

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

Существует множество алгоритмов для нахождения покрытия вершин графа, но вы хотите знать лучший алгоритм, который можно использовать в качестве параллельного подхода для нахождения покрытия вершин на большом графе, так что же лучше? Поскольку я зада…
28 июл '14 в 10:32
1 ответ

Как мне доказать правильность моего жадного алгоритма для покрытия вершин на дереве?

Задача покрытия вершин на деревьях заключается в следующем. Вход: ациклический простой неориентированный граф G Вывод: набор вершин W такой, что для каждого ребра uv, u ∈ W или v ∈ W. Мы хотим минимизировать размер W. Мой жадный алгоритм - инициализ…
09 окт '14 в 00:51
1 ответ

Как выполнить релаксацию целочисленного линейного программирования формулировки покрытия вершин графа?

Я реализую алгоритмы оптимизации из алгоритмов кернелизации для задачи покрытия вершин: теория и эксперименты (PDF). Я немного застрял в главе 2.3: Ядро с помощью линейного программирования. Идея этого метода (в формулировке ILP) заключается в назна…
20 июл '14 в 15:32
0 ответов

Оптимизация в алгоритме покрытия вершин методом грубой силы

Я пишу алгоритм перебора для решения покрытия вершин следующим образом: BruteForceVertexCover( Graph G = (V,E) ){ for size= 1 ... |V| vector<int> v = {0...size-1} do{ if(test(G, v)) return v; //test if v covers G } while(v has next combination…
05 окт '16 в 03:57
1 ответ

(Возможный) контрпример к общему минимальному покрытию вершин на дереве Алго и мой подход

В прошлом было много сообщений на эту тему из быстрого поиска на сайте, многие из которых используют это повторение динамического программирования: C (x) = min (1 + сумма (C (i) для i у детей x), len (дети x)) + sum(C(i) для i у внуков x)) Предполаг…
07 июл '17 в 08:15
1 ответ

Недетерминированный алгоритм для покрытия вершин

У меня была проблема в моей викторине, чтобы написать недетерминированный алгоритм для Vertex Cover. Мы обсудили решение с нашим инструктором, и он сказал, что уровень неопределенности не должен быть слишком высоким. Это должно быть разумно хорошо.Я…
24 ноя '15 в 21:00
1 ответ

Вариант минимального покрытия вершин

В своем исследовании я сталкиваюсь с одним из вариантов проблемы покрытия вершин следующим образом: Учитывая граф G, вершину v и число k, чтобы решить, имеет ли G покрытие вершины размера k, которое содержит v. Я искал всю литературу и не смог найти…
22 янв '14 в 18:24
0 ответов

Не в состоянии понять это свойство графа

Я прочитал это в простом графе, | минимальное покрытие вершин | <= 2*| максимальное совпадение |. Рассмотрим графическое представление здесь:- Здесь минимальное покрытие вершин может быть {B,C,D,E}, которое имеет размер 4, а размер максимального соо…
23 июн '17 в 08:02
1 ответ

Networkx min_weighted_vertex_cover в python возвращает весь набор вместо покрытия вершин

У меня есть матрица смежности A с nodes = {0, 1, 2, 3, 4, 5} A = [[0,1,1,0,0,0],[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,0,0,1,1],[0,0,1,1,0,0],[0,0,0,1,0,0]] Я хочу найти минимальный вес покрытия вершин этого графа. Я преобразовал эту матрицу смежности с g…
02 авг '17 в 04:53