Преобразование произвольного покрытия в покрытие вершин

Дан плоский план $G=(V,E)$ и пусть $\mathcal{G}$ обозначает его вложение в плоскость st, каждое ребро которого имеет длину . Кроме того, у меня есть множество точек в которых каждая точка содержится в . Кроме того, для любой точки в верно, что существует с геодезическим расстоянием до не более единицы. (Расстояние измеряется как кратчайшее расстояние в .) $1$ $C$ $c \in C$ $\mathcal{G}$ $p$ $\mathcal{G}$ $c \in C$ $p$ $\mathcal{G}$

Я хочу утверждать, что, учитывая для которого выполняется указанное выше условие, я могу легко преобразовать его в покрытие вершины или, другими словами, преобразовать его в той же мощностью, что любой помещен в в вершине и по- прежнему охватывает . $C$ $C'$ $c \in C'$ $\mathcal{G}$ $G$ $C'$ $G$

Мой подход состоял в том, чтобы ориентировать края и перемещать точки в в конечной вершине дуги. Но до сих пор я не нашел правильную ориентацию , которое дает от . $C$ $C'$ $C$

У кого-нибудь есть идея?

algorithms graph-theory set-cover user695652
источник

Я не совсем понимаю проблему. Что означает «

»? Как именно вы измеряете расстояния? Если вы имеете в виду, что

всегда находится на ребре, то кажется, что если вы поместите его с любого конца, то каждая точка на расстоянии не более

от него, а именно обе конечные точки, все еще находится на расстоянии не более

от него. Для любой ориентации.

p

$p$

G

$\mathcal{G}$

p

$p$

1

$1$

1

$1$

Юваль Фильмус

@Yuval Филмус

является жордановой дугой рисунка

, то есть подмножество

просто означает, что точка должна содержаться на чертеже, а не просто где-нибудь на плоскости. Расстояние измеряется как геодезическое расстояние в

, т.е. кратчайший путь, соединяющий две точки на чертеже. Для вашего последнего замечания возьмите 4 цикла и поместите две точки в середине первого и третьего ребра. Это покрывает весь граф, но если вы теперь переместите одну точку в конечную точку вершины по часовой стрелке и одну точку в конечную точку вершины против часовой стрелки, это действительно необходимо

G

$\mathcal{G}$

G

$G$

\mathhbb R^{2}

$\mathhbb{R}^2$

p \in G

$p \in \mathcal{G}$

G

$\mathcal{G}$

user695652

Ответы:

Если нет точек в не лежат точно на средней точке ребра в , то достаточно , чтобы связать каждую точку в до ближайшей вершины в . Я оставлю это в качестве упражнения для читателя, чтобы доказать это (подсказка: доказать противоречие). $C$ $\mathcal{G}$ $C$ $\mathcal{G}$

С другой стороны, если точкам в разрешено лежать на средней точке ребер, мы можем предоставить контрпример: $C$

введите описание изображения здесь

Синие линии и круги и красные кресты . $\mathcal{G}$ $C$

ИЗМЕНЕНО ДЛЯ ДОБАВЛЕНИЯ: пример с двусвязным графом

введите описание изображения здесь

mhum
источник

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

user695652

Я не думаю, что двойная связь спасет вас. Я отредактировал свой ответ новым примером.

mhum

Это довольно другой вопрос. Возможно, имеет смысл опубликовать это отдельно.

Мм

@mhum Как вы делали снимки графиков? Существует ли какая-то программа для этого?

Tacet

@Tacet Я не помню точно, как я это сделал. Я думаю, что первым мог быть MS Paint или GIMP. Второй может быть или GIMP или Geogebra.

mhum