Discussion:Liste des algorithmes de la théorie des graphes

Titre un peu ambitieux ?

Bonjour. Merci d'avoir crée cette page. Je trouve le titre un peu ambitieux. Pourquoi pas quelques algorithmes (importants) de la théorie des graphes ? Ou bien quelques algorithmes de graphes ? Ou algorithmique des graphes ? Tchai 3 septembre 2006 à 19:08 (CEST)

Bonsoir. Dans la lignée des suggestions de Tchai, je proposerais : « Algorithmes en théorie des graphes », quoique la proposition « Algorithmique des graphes » de Tchai me paraît à la fois globale, concise et simple. --nha de Lyon 3 septembre 2006 à 22:26 (CEST)

Présentation unifiée des algorithmes

Bonsoir,

Après une première lecture de ce "nouvel" article, j'émettrais les suggestions et remarque suivantes :

• Passage de la sous-section actuelle « Présentation unifiée... » au niveau section ;
• Dans la sous-section « Matrice associée à un graphe », l'ensemble Q est introduit sans spécification. Bien qu'on devine sa nature dans le présent contexte, une définition explicite serait probablement bienvenue ;
• Dans la sous-section « Chemin optimal », il est indiqué que plusieurs chemins optimaux peuvent exister. Un chemin optimal serait donc plutôt supérieur ou égal à tout autre chemin ;
• Dans la sous-section « Algorithme de Warshall généralisé », la notation d'élément de matrice avec une parenthèse fermante et sans parenthèse ouvrante correspondante est-elle intentionnelle ?
• On pourrait faire un rapprochement entre la présentation unifiée et la représentation statique de graphe, sur laquelle la première repose, quoique la représentation statique exposée dans l'article homonyme ne soit pas aussi développée qu'ici.

Merci en tous cas à Claude pour sa contribution. ;-) Cordialement --nha de Lyon 3 septembre 2006 à 23:05 (CEST)

pour la deuxième remarque, il s'agit d'une erreur de ma part (une suppression intempestive du début) que je viens de corriger.Claudeh5 4 septembre 2006 à 12:30 (CEST)

pour la quatrième (algorithme de warshall), il s'agit également d'une erreur de ma part, que je corrige.Claudeh5 4 septembre 2006 à 12:35 (CEST)

Concernant le point 3, il n'y a formellement aucune erreur: j'ai défini supérieur par la relation a>>b qui est une relation d'ordre. Je rappelle qu'une relation d'ordre n'est jamais stricte. Cela dit, je comprends aussi que l'on ajoute éventuellement "ou égal" ...Claudeh5 4 septembre 2006 à 13:53 (CEST)

Merci pour les précisions et rectifications, Claude. J'en ai profité pour "éclaircir" un peu la présentation visuelle de la section sur l'algorithme de Warshall généralisé. On peut bien entendu revenir à l'état originel si cette visualisation n'est pas acceptable.

A propos de la relation d'ordre, ma remarque sur une explicitation de cet état d'ordre suivait une antérieure ambiguïté que j'avais repérée dans un ouvrage. En tous cas, vous m'avez conforté dans mon interprétation du supérieur en supérieur ou égal dans ce contexte (certes implicite) — et c'est probablement l'essentiel.

Néanmoins, autant elle est large dans le contexte de la section sur le chemin optimal, autant quelque chose m'échappe sur votre rappel selon lequel une relation d'ordre n'est jamais stricte (contre-exemple : ordre strict et total sur la puissance d'un ensemble ou sur un ensemble transitif). Vouliez-vous dire que, mentionnée sans précision et dans la pratique, une relation d'ordre est large par défaut... ? Ceci est sans doute un autre débat. ;) --nha de Lyon 5 septembre 2006 à 02:03 (CEST)

Une relation d'ordre est par définition reflexive, anti-sysmétrique et transitive. Elle ne peut donc jamais être stricte puisqu'elle est reflexive ! Autrement dit: une relation d'ordre stricte n'est pas une relation d'ordre ! Claudeh5 5 septembre 2006 à 12:56 (CEST)

Pour confirmation Relation d'ordre !

Cela dit, la présentation actuelle est plus claire que celle que j'avais faite.Claudeh5 5 septembre 2006 à 13:03 (CEST)

Merci pour la justification ultime, Claude. Et désolé de vous avoir poussé aussi loin. Je suis désormais "pleinement" convaincu et m'incline. :-) J'en étais resté à la définition d'un ordre comme un semi-ordre actuel... D'ailleurs, cette nuance entre ordre et ordre strict me rappelle un fait récemment médiatisé dans le domaine de l'astronomie à propos de Pluton, classée dorénavant non plus dans la catégorie des planètes mais dans celle des... planètes naines. --nha de Lyon 7 septembre 2006 à 01:30 (CEST)

P.S. : J'ai re-cadré nos réponses car le décalage risque de dénaturer l'affichage à mon goût. Inverser l'effet si souhaité.

J'ai réécrit la section Chemin Optimal qui n'était pas très claire. En particulier, le poids d'un chemin est définit comme le produit des valuations, et non la somme. Le cadre d'étude proposé (celui des semi-anneaux) me semble trop large puisque dans certains cas, ne permet pas la définition de chemin optimal, je propose donc de parler plutôt de dioïdes comme le font Michel Gondran et Michel Minoux dans l'ouvrage de référence Graphes, Dioïdes et Semi-anneaux, qui par ailleurs mériterait d'être cité. --82.237.177.72 (d) 18 mai 2008 à 15:10 (CEST)

La présentation faite résulte de notes prises il y a plus de vingt ans (trente peut-être) sur l'article original de J. Ferland et P. Robert "Généralisation de l'algorithme de Warshall" RIRO 7, 1968, p71-85 mais il est tout à fait possible qu'une erreur s'y soit glissée.Claudeh5 (d) 20 mai 2008 à 15:53 (CEST)

Problèmes de cheminement et Liste des algorithmes de la théorie des graphes

La présentation unifiée des algorithmes de cheminement est intéréssante mais n'a pas tellement sa place dans une liste d'algorithmes sur les graphes. Je proposer de déplacer cette section vers la page Problèmes de cheminement, qui par ailleurs n'est qu'une ébauche, et d'éventuellement la compléter (par exemple, en montrant comment l'algorithme de Dijkstra rentre dans le cadre général des dioides sélectifs, et pourquoi pas en y mettant la preuve générale de l'algorithme) 82.237.177.72 (d) 20 mai 2008 à 14:07 (CEST)

Pas de problème pour moi. Je suis d'accord.Claudeh5 (d) 20 mai 2008 à 15:49 (CEST)