Transformer une couverture arbitraire en une couverture de vertex

16

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 1 C c C G p G c C p Gg=(V,E)g1CcCgpgcCpg

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 G G C GCCcCggCg

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 CCCC

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

user695652
la source
Je ne comprends pas très bien le problème. Que signifie " dans G "? Comment mesurez-vous exactement les distances? Si vous voulez dire que p 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 1 de lui - à savoir les deux extrémités - est toujours à une distance d'au plus 1 de lui. Pour n'importe quelle orientation. pgp11
Yuval Filmus
1
@Yuval Filmus est un dessin à l'arc jordanien de G , c'est-à-dire un sous-ensemble de \ mathhbb R 2 . p G 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 G , 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 couvregg\ mathhbbR2pgg
user695652

Réponses:

5

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

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 C .gC

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