Vertex cover или вершинное покрытие

@Dimitrij1 · Регистрация: 31.01.2016

Author24 — интернет-сервис помощи студентам

Дано: Вершинное покрытие (VC) это подмножество вершин которые покрывают все рёбра в графе G.
Формально, дан граф G = {V,E}, VC это подмножество вершин $https://www.cyberforum.ru/cgi-bin/latex.cgi?V' \subseteq{V}$ (размера к) такое что если $https://www.cyberforum.ru/cgi-bin/latex.cgi?(u,v)$ это ребро в G тогда когда $https://www.cyberforum.ru/cgi-bin/latex.cgi?u\in V'$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?v \in V'$ или оба $https://www.cyberforum.ru/cgi-bin/latex.cgi?v,u \in V'$ .
n = Количество вершин. n = |V|

Правильно ли что тогда все те вершины которые в V\V' (которые являются независимым множеством в G) соединены ребром с вершинами которые в V' ?

@Shamil1 · 25.01.2019, 11:24

Добавьте на свой рисунок вершину без рёбер.

@Dimitrij1 3 / 3 / 8 Регистрация: 31.01.2016 Сообщений: 129
		1
	Vertex cover или вершинное покрытие 25.01.2019, 01:16. Показов 2531. Ответов 1 Метки нет (Все метки) Дано: Вершинное покрытие (VC) это подмножество вершин которые покрывают все рёбра в графе G. Формально, дан граф G = {V,E}, VC это подмножество вершин $https://www.cyberforum.ru/cgi-bin/latex.cgi?V' \subseteq{V}$ (размера к) такое что если $https://www.cyberforum.ru/cgi-bin/latex.cgi?(u,v)$ это ребро в G тогда когда $https://www.cyberforum.ru/cgi-bin/latex.cgi?u\in V'$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?v \in V'$ или оба $https://www.cyberforum.ru/cgi-bin/latex.cgi?v,u \in V'$ . n = Количество вершин. n = \|V\| Правильно ли что тогда все те вершины которые в V\V' (которые являются независимым множеством в G) соединены ребром с вершинами которые в V' ? Миниатюры 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	25.01.2019, 11:24	2
	Сообщение было отмечено Dimitrij1 как решение Решение Добавьте на свой рисунок вершину без рёбер. 0

Опции темы

Vertex cover или вершинное покрытие

Решение