Я пытаюсь понять разницу между крышкой вершин и доминирующим множеством.
Из того, что понимает в доминирующем множестве множество D содержит вершины, смежные с другими вершинами, не входящими в D (для каждого v из V либо v находится в D, либо оно смежно с одним в D).
В вершинном покрытии все вершины из D покрывают все ребра, но, делая их, смежны с другими вершинами, они не находятся в D. Итак, почему это не доминирующее множество?
Я нашел несколько графиков в статье Википедии Dominating Set, которые иллюстрируют эту разницу.
В этих примерах показаны доминирующие множества (красным), которые не являются вершинными обложками, противоположными тому, что вы задали позже в своем вопросе. Края в (V-D) не позволяют им покрывать вершины.
Предыдущие ответы хороши, однако самый простой пример еще не написан здесь:
Вам нужно всего лишь рассмотреть путь на четырех вершинах, чтобы отличить два понятия. Пусть a, b, c, d - последовательные вершины такого пути. Тогда {a, d} является доминирующим множеством, но не вершинным накрытием (так как он не покрывает ребро bc).
Крышка вершин не может быть доминирующим множеством, если у вас есть вершина нулевой степени вне вершинного покрытия. Крышка вершины "покрывает" все ребра, но вершина нулевой степени не примыкает к вершинному покрытию.
Доминирующее множество не может быть вершинным накрытием, если существует ребро, например e = (u, v), где u и v находятся вне доминирующего множества. Это возможно, если u и v смежны с вершинами в доминирующем множестве другими ребрами.
Каждое покрытие вершин является доминирующим множеством, однако обратное неверно. Например, если у вас есть граф G = (V, E) G = {a, b, c, d, e} и E = {(a, b), (b, c), (c, d), ( e, a), (e, b)}, то Доминирующее множество DS = {b, e} не является вершинным накрытием G. Ребро (c, d) не покрывается.
Для подключенных графов вершинное покрытие должно быть доминирующим множеством. Для изолированных узлов вам необходимо включить это в доминирующий набор, но не нуждаться в нем в вершинном обложке. Тем не менее, доминирующие наборы являются более крупным классом, они не должны быть крышкой вершин, как показано в примере этого ответа.
Я думаю, что основное различие заключается в том, что для вершинной обложки край должен иметь по крайней мере одну из своих конечных точек в наборе вершинной обложки. Тем не менее, для Dominating Set он удовлетворяет, когда узел находится либо в Set или его ближайшем сосете в Set, и, следовательно, возможно, что обе конечные точки ребра не находятся в Set (происходит только тогда, когда они оба подключенных к узлам, находящимся в наборе). Надеюсь, это немного разъясняет.
Крышка вершин: вы можете думать о них как о полиции, которая смотрит на любой проход (края). Таким образом, они могут следить за любым узлом, кроме изолированных, потому что узлы не являются их проблемами. Они должны охватывать все проходы.
Доминирующий набор: это политики, которые следят за любым узлом. Проходы не важны, поэтому, если один из них контролирует узел через ребро, другие ребра, связанные с этим узлом, могут не быть охвачены, потому что отрывки не относятся к этим политикам.
Проверьте изображения этого ответа fooobar.com/info/536439/...