Diamètre d' un graphe

[kadaid]

Bonjour

Je ne comprends pas comment déterminer le diamètre d'un graphe.

Sur le dessin ci-joint on donne 3 pour le diamètre (distance maximale entre deux points: les cornes)
Pour moi, plutôt c'est 4
Merci pour des explications.

[kadaid]

Je le refais car l'image n'apparait pas!

[hdci]

Pourquoi la distance entre les deux points "cornes" serait-elle 4 ?

La distance entre deux points est la mesure du plus petit parcourt entre ces deux points, et la mesure d'un parcourt, c'est le nombre de segments qu'il emprunte.

[hdci]

Et pour compléter : le diamètre est la plus grande des distances, mais pas le plus grand des parcourt !

Si c'était le plus grand des parcourt, le diamètre serait infini ((puisque rien n'interdit de passer deux fois par le même point, on ferait une infinité d'aller-retour).

[aymanemaysae]

Bonjour;

[aymanemaysae]

Bonjour ;

Je rectifie : "le plus grand élément de C" au lieu de "le plus grand de C" .

[pascal16]

On pourrait définir :
_ un diamètre eulérien : le plus long de l'ensemble des chemins les plus courts entre deux sommets qui passe par tous les sommets (ici 4).
_ un diamètre hamiltonien : le plus long de l'ensemble des chemins les plus courts entre deux sommets qui passe par toutes les arêtes (ici 6)

[kadaid]

Merci pour vos réponses!

J'ai compris.
On détermine la distance (chemin le plus court) entre deux points à chaque fois et puis le diamètre est la plus grande de ces distances .

[aviateur]

Bonjour,
Avec cette définition du diamètre quel est alors le diamètre du graphe G de dont l'ensemble des sommets S est :
, et l'ensemble des côtés est constitué des segments
qui relient un sommet aux sommets les plus proches (au sens de la distance euclidienne)?

[pascal16]

majorant : 3n

[aviateur]

Bonjour
Je crois même que c'est 3n

[aviateur]

Je me demande si on ne peut pas compliquer les choses, comme par exemple: soit dans le graphe G dont l'ensemble S des sommets sont de coordonnées entières et sont situés à l'intérieur de l'ellipse d' équation

Deux sommets qcq sont reliés par un côté. Quel est le diamètre de G?

[pascal16]

2 * max(E(a);E(b)) ?