graphe : sous-ensemble, proximité

[invite1143130f]

Bonjour,
je me posais la question suivante : existe t il une méthode pour extraire un sous-ensemble de sommet de taille minimale tel que tous les sommets du graphe soient à une distance au plus 1 des sommets du sous-ensemble ?
Et pour une distance au plus n ?
Est-ce qu'il existe un problème connu qui serait l'équivalent continu : choisir un nombre minimal de point d'une surface (ou plus simplement en dimension 1 d'un ensemble de réels) tel que tous les points soient à une distance majorée par une constante de l'ensemble de points choisi ?

J'ai fait quelques recherches mais je ne sais pas quels mots taper car je manque un peu de culture mathématique dans ce domaine ...
-----

[Dlzlogic]

Bonjour,
Si vous disiez simplement ce que vous cherchez, sans employer des expressions compliquées.
Il y a un terme que vous devez définir : distance. Est-ce la distance euclidienne telle qu'on l'utilise habituellement, la distance de Manhattan ou une autre ?.

[invite1143130f]

Je n'ai pas cherché à employer des expressions compliquées, au contraire. Je n'ai pas encore un vocabulaire très large dans ce domaine ce qui allonge sûrement les phrases, et ce qui explique aussi pourquoi j'ai posté ce sujet (je n'arrive pas à faire de recherche pertinente sur google car je ne connais pas la formulation usuelle du problème).

A la base je parle de graphes, la distance dont je parle est donc la longueur du plus court chemin entre deux sommets. Pour la version continue du problème, quelle que soit la distance dont on parle, d'éventuelles références m'intéressent.

Merci d'avance !

[invite9dc7b526]

Pour la distance 1 (je suppose que chaque arête compte 1) cherche des informations sur les graphes bipartis et sur la recherche d'une bipartition (ce n'est pas exactement ton problème mais tu peux peut-être trouver des stratégies à adapter).

[A voir en vidéo sur Futura]