Théorie des Graphes

Bonjour,

Je m’intéresse un peu aux bases de la théorie des graphes mais je trouve la terminologie assez compliquée sur Internet.

Prenons par exemple un graphe (complet?) avec 5 noeuds:

Est-ce que le cardinal de ce graphe est bel et bien 5 car c’est le nombres de "segments" à l’extérieur? La longueur du chemin le plus court entre deux noeuds est bien de 1 ?

J’ai représenté ce graphe comme ceci (je ne sais pas si c’est bien ce qu’on appelle un graphe complet à 5 noeuds par contre):

Merci d’avance pour votre aide!

Salut !

Ce graphe est bien ce qu’on appelle un graphe complet, c’est-à-dire que toutes les « arêtes possibles » existent, pour faire simple.

Par contre, le cardinal n’est pas le nombre de « segments extérieurs » mais simplement le nombre de sommets du graphe.

Quand à la distance entre deux sommets, c’est la longueur de la plus petite « chaîne d’arêtes » les reliant. Donc pour un graphe complet, c’est bien 1 pour toute paire de sommets.

EDIT : Tiens, y a pas de cours de théorie des graphes sur ZdS…

EDIT 2 : C’est faux, il y a le tutoriel d’Algue-Rythme.

Ah! Je vais déjà lire le tutoriel d’Algue-Rythme alors.

Hum, ici le nombre de sommet est bien égal à 5 non? En fait, ça sera pas toujours égal au nombre de noeuds (ou je confond?) ?

Merci :-)

Je pense que nœuds et sommets, on parle de la même chose. Et oui, ici c’est bien 5.

Sommet ou noeud, les 2 mots veulent dire la même chose.

Dans ton dessin, les sommets sont disposés 'régulièrement' et forment un pentagone convexe. Donc oui, avec cette disposition, le nombre de sommets coïncide avec le nombre de segments extérieurs.

Mais dispose 4 points en carré, et un cinquième point à l’intérieur du carré. Tu as toujours 5 sommets, mais tu n’as plus que 4 segments extérieurs.