Transformer une couverture arbitraire en une couverture de vertex

Donné est un graphe planaire et soit dénoter son encastrement dans le plan st chaque arête a la longueur . J'ai en outre un ensemble de points où chaque point est contenu dans . De plus, il tient pour tout point dans qu'il existe un avec une distance géodésique à au plus un. (La distance est mesurée comme la distance la plus courte dans .) $G=(V,E)$ $\mathcal{G}$ $1$ $C$ $c \in C$ $\mathcal{G}$ $p$ $\mathcal{G}$ $c \in C$ $p$ $\mathcal{G}$

Je veux faire valoir que, étant donné un pour lequel la condition ci-dessus est remplie, je peux facilement le transformer en un vertex cover, ou le mettre différemment, le transformer en un de même cardinalité st tout est placé dans à un sommet de et couvre encore . $C$ $C'$ $c \in C'$ $\mathcal{G}$ $G$ $C'$ $G$

Mon approche consistait à orienter les bords et à déplacer les points en au sommet de l'arc. Mais jusqu'à présent , je ne l' ai pas trouvé une orientation correcte qui donne de . $C$ $C'$ $C$

Est-ce que quelqu'un a une idée?

algorithms graph-theory set-cover user695652
la source

Je ne comprends pas très bien le problème. Que signifie "

dans

"? Comment mesurez-vous exactement les distances? Si vous voulez dire que

est toujours sur une arête, alors il semble que si vous le mettez à l'une ou l'autre extrémité, alors chaque point à une distance d'au plus

de lui - à savoir les deux extrémités - est toujours à une distance d'au plus

de lui. Pour n'importe quelle orientation.

p

$p$

G

$\mathcal{G}$

p

$p$

1

$1$

1

$1$

Yuval Filmus

@Yuval Filmus

est un dessin à l'arc jordanien de

, c'est-à-dire un sous-ensemble de

signifie simplement que le point doit être contenu dans le dessin et pas n'importe où dans le plan. La distance est mesurée comme la distance géodésique en

, c'est-à-dire le chemin le plus court reliant deux points du dessin. Pour votre dernière remarque, prenez un cycle de 4 et mettez deux points au milieu du premier et du troisième bord. Cela couvre tout le graphique, mais si vous déplacez maintenant un point à son extrémité de sommet dans le sens des aiguilles d'une montre et un point à son extrémité de sommet dans le sens inverse des aiguilles d'une montre, il couvre

G

$\mathcal{G}$

G

$G$

\mathhbb R^{2}

$\mathhbb{R}^2$

p \in G

$p \in \mathcal{G}$

G

$\mathcal{G}$

user695652

Réponses:

Si aucun point se situent exactement sur le point médian d'un bord en , il suffit d'associer chaque point au sommet le plus proche dans . Je laisserai au lecteur le soin de le prouver (indice: prouver par contradiction). $C$ $\mathcal{G}$ $C$ $\mathcal{G}$

D'un autre côté, si les points en peuvent se situer au milieu des bords, alors nous pouvons fournir un contre-exemple: $C$

entrez la description de l'image ici

Les lignes bleues et les cercles sont et les croix rouges sont . $\mathcal{G}$ $C$

MODIFIÉ POUR AJOUTER: Un exemple avec un graphique biconnecté

entrez la description de l'image ici

mhum
la source

Merci beaucoup pour le contre-exemple. Êtes-vous d'accord que si nous limitons les graphiques à être biconnectés, la revendication est vraie, même si tous les points sont au milieu?

user695652

Je ne pense pas que la bi-connectivité vous sauvera. J'ai édité ma réponse avec un nouvel exemple.

mhum

C'est une question assez différente. Il pourrait être judicieux de l'afficher séparément.

mhum

@mhum Comment avez-vous fait des photos de graphiques? Existe-t-il un programme pour cela?

Tacet

@Tacet Je ne me souviens pas exactement comment j'ai fait ça. Je pense que le premier pourrait avoir été MS Paint ou GIMP. Le deuxième pourrait être GIMP ou Geogebra.

mhum