Discuter:Théorie des graphes

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Théorie des graphes fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
À évaluer Cet article a été classé comme d'Importance ? selon le Tableau d'évaluation du projet.
WikiProjet Informatique
 Théorie des graphes fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Élevée Cet article a été classé comme d'Importance élevée selon le Tableau d'évaluation du projet. (Contester?)

Sommaire

[modifier] Parcours de graphe : un article particulier à faire ?

Je pense qu'il faudrait créer un article particulier sur les algorithmes de parcours de graphe pour être cohérent vu que les autres algos ont leur page propre. En plus ça permettrait d'étoffer la description de ces algos... Any objections? :p

Franckyboy 30 mar 2005 à 23:24 (CEST)

[modifier] Valuation : potentielle multiplicité

Je me permets de retablire <<Une valuation>> car rien n'empeche d'en definir plusieurs sur un meme graphe.
J'ai egalement modifier le corps gras de sommets et aretes et italiques, le corps gras attirant trop l'attention a mon avis.

Dtcube

[modifier] Chemin et graphe connexe : définitions complémentaires

J'ai rajouté la def sur les chemins et sur un graphe connexe. Par contre, il y a un probleme d'homogeneité des notations : sur cette page un graphe est noté (S,A) sommet/arete alors que sur la page de l'algo de Djikstra il est noté (V,E) vertex/edge

Renoo

[modifier] Liste des définitions : ordonner alphabétiquement ?

Une petite question parce que je suis tout nouveau... Le lien sur accessibilité pointe en fait vers l'accessibilité du web ce qui n'a rien a voir. Comment fait-on dans ce cas ? Une autre petite chose, j'ose pas trop encore, la liste des définitions ne serait-elle pas mieux dans l'ordre alphabétique ?

AlphaX

Bonjour, l'ordination alphabétique me semble intéressante. Le (seul ?) inconvénient à mon sens serait l'éloignement relatif de notions de même contexte : par exemple, adjacence et incidence. Cordialement --nha de Lyon. 27 août 2006 à 15:41 (CEST)

[modifier] Article long : découper ?

Je trouve que l'article commence a devenir un peu long, ne pensez vous pas qu'il serait temps de le splitter?

As4

Ca me parait une bonne idée

Ca fait quelques temps que cette proposition est dans l'air. Il est clair que l'article est trop long, avec beaucoup de listes. Est-ce qu'on décide quelque chose ? Je pense qu'un article complet sur les classes de graphes serait réalisable sans trop d'efforts. Je remarque d'ailleurs que d'autres articles font référence à cette section particulière de l'article. Ca me parait donc cohérent d'en faire un article à part, et de laisser une phrase ou deux dans Théorie des graphes pour faire le lien. Qu'en pensez-vous ? --François Clautiaux 3 août 2006 à 11:36 (CEST)

Bonjour, je penche (aussi) en faveur du découpage proposé — article dédié aux classes de graphes, inspiré de la section de cet article. Cordialement --nha de Lyon. 27 août 2006 à 15:36 (CEST)

[modifier] Référence aux graphes parfaits, aux mineurs de graphes

Ca serait bien de faire une petite référence aux graphes parfaits, et aux mineurs de graphes (Seymour et Robertson) ?

Bonjour,
Je me suis permis de placer la proposition ci-dessus dans une "nouvelle" section de manière à rendre la page de discussion un peu plus homogène. J'adresse mes excuses à l'auteur de cette proposition pour ne pas avoir attendu son autorisation (si tenté qu'il eût voulu me l'accorder). Je note d'ailleurs que cet auteur a omis de signer.
A cette heure (précise), aucune référence aux graphes parfaits ni aux mineurs de graphes n'existe dans l'article actuel. Ladite proposition me paraît donc toujours d'actualité. J'émets personnellement un avis favorable.
Cordialement, --nha de Lyon. 20 juillet 2006 à 22:55 (CEST)

En fait, j'avais oublié de me connecter quand j'ai fait cette remarque. J'ai ajouté une référence au graphes triangulés avec un lien sur les mineurs. Reste à ajouter une référence aux graphes parfaits. --François Clautiaux 3 août 2006 à 11:31 (CEST)

Bonjour,
J'ai pris note des références sur les graphes triangulés (et aussi sur les mineurs de graphe) — merci à vous, François.
J'ai inséré de mon côté une entrée sommaire sur la notion de graphe parfait. De fait, j'en ai profité pour compléter la liste de définitions en intégrant les notions de k-coloration (curieusement non abordée aussi formellement qu'on aurait pu s'y attendre dans l'article Coloration de graphe) et de nombre chromatique (tout aussi succinctement développé dans le même article contrairement à la version anglaise par exemple) qui sont utiles pour la définition de graphe parfait.
Question : Une mention (légère ?) sur les théorèmes de caractérisation (initialement : conjectures) forte et faible des graphes parfaits aurait-elle également sa place ici ou dans un autre article (lequel ?) ?
Cordialement --nha de Lyon 28 août 2006 à 03:37 (CEST)

[modifier] Sous graphe : erreur dans la formule ?

Soit G=(S,A) un graphe, un sous-graphe induit ou sous-graphe de G, est un graphe G'=(S',A'), où:

S' ⊆ S

A' ⊆ A ∩ (S' × S') <-- (S × S') ?

Si S = S, G' est un sous graphe couvrant <-- Si S = S' ?

  • Il est écris Si S&#39 = S;, mais ce n'est pas très lisible, il est vrai

Bein non, le deuxième graphe est G' dont l'ensmble de sommet est S', alors ca n'aurait pas de sens d'avoir dans les arcs A' de G' des sommets n'appartenant pas à ce graphe (apprtenant à S et non à S')...

As4

Pour un sous-graphe induit il faut remplacer l'inclusion par l'égalité : A' = A ∩ (S' × S')

En général sous-graphe et sous-graphe induit ont la même signification aujourd'hui. Je note que Claude Berge (et quelques autres encore aujourd'hui) distinguait ces deux termes. Pour ma part je préfère les confondre car dans l'usage international "sous-graphe induit" n'a pas vraiment survécu.

Yjp 25 août 2005 à 12:59 (CEST)

Je n'ai pas le temps d'éclaircir ma pensée maintenant mais aprsè relecture j'invoque le droit de retirer ce que j'ai dit juste au dessus. Comment ai-je pu écrire ça ?!

--Yjp 29 août 2005 à 18:14 (CEST)

Concernant la notation des graphes, adoptés une notation G=(V,E) ( V : vertices, E : edgr) pour les graphes non orientés et G=(V,A) (A : arcs) pour les graphes orientés possède l'interêt de pouvoir savoir de quels type de graphe il s'agit par la notation, et non pas de mélanger les deux. Que pense le peuple d'adopter cette notation?

As4

Bonjour,
Bien qu'une notation différenciée me semble judicieuse entre les deux classes de graphes évoquées, la notation (V, A) ne me convient pas car elle mélange 2 abréviations implicites : V pour Vertex (terme anglais pour sommet) et A pour Arête ou Arc (donc des termes français).
Ceci étant, je suggère qu'on se réfère à la section <<Notations>> ci-dessous pour la poursuite de ce point de discussion.
Cordialement, --nha de Lyon. 20 juillet 2006 à 23:00 (CEST)

[modifier] Distinguer graphes orientés et graphes non orientés

Il me semble aujourd'hui que dans l'usage la définition de graphe non orienté est différente (les arêtes sont décrites comme un ensemble de parties à 2 éléments de l'ensemble des sommets). On peut se référer par exemple à 2 livres qui me viennent à l'esprit:

- celui de Reinhard Diestel (Graph Theory)

- ou en français celui de Claudine Robert et d'Olivier Cogis (Théorie des Graphes)

Je serais pour faire cette distinction. Si personne n'y voit d'inconvénient j'apporterai des modifs dans ce sens dans quelque temps.

Yjp 25 août 2005 à 12:45 (CEST)

Euh.. à vrai dire je ne vois pas vraiment qu'est ce que ca change je trouve que ce qu'il y a et ce que vous proposez revient exactement au même... mais changez si vous pensez que c'est plus clair.

as4 25 août 2005 à 23:20 (CEST)

Il n'y a pas de raison que j'impose mon point de vue. Il peut par ailleur se révéler parfois (souvent ?) un peu brouillé : il faut alors m'aider à y voir plus clair. Pour poursuivre, je souhaiterais citer 4 exemples :

- les opérations ensemblistes peuvent du coup être utilisées et rendre commode l'écriture de preuves et de définitions (en particulier on peut parler d'appartenance d'un sommet à une arête);

- il est courant de présenter les graphes (non orientés) comme des hypergraphes (dont les arêtes sont des ensembles de sommets) particuliers où toutes les arêtes sont de taille 2;

- la plus grande partie des publications scientifiques (sentiment très subjectif) actuelles définit (ou définissent je ne sais plus) une arête d'un graphe non orienté comme un ensemble de 2 sommets;

- les graphes non orientés et orientés-symétriques se révèlent parfois de natures très différentes (par exemple, en algorithmique, il existe des problèmes qui se sont avérés polynomiaux dans un cas et NP-Complet dans l'autre (mais je dois dire pour être complet que dans les exemples que je connais cette différence est étroitement liée aux définitions de chaînes et de chemins, d'ailleurs différentes de celles proposées dans cet article) et réciproquement.

YJP

62.147.48.83 26 août 2005 à 17:00 (CEST)

Je crosi que je commence à comprendre. C'est effectivment quelque chose qui manque depuis longtemps mais qui est sur la vesion anglaise : comment fait on pour représenter mathématiquement un arc ou une arête. Pour une arête je suis totu à fait d'accord qu'il s'agit d'un couple, un ensemble à deux éléments. L'aspect relation binaire reposse également sur cette relation. Je trouve que les deux sont parlant. De toutes facon après un rapide coup d'oeuil sur votre courte page utilisateur je pense que vous êtes mieux placé que moi pour parler du sujet. Je vous sugère de modifier comme vous l'entendez, on pourra de toute facon en rediscuter ;)

as4 26 août 2005 à 22:31 (CEST)

Je voulais juste préciser qu'en effet la définition non orientée n'apporte pas vraiment quelque chose de nouveau dans le sens ou la théorie des graphes orientés englobe celle des graphes non orientés et qu'il s'agit "seulement" de commodité et de "coller" à l'usage pratiqué par les auteurs scientifiques d'aujourd'hui. Je pense d'ailleurs rajouter un jour un petit passage de ce que pensait Berge (dans son livre de 1960 et des poussières) à ce propos comme quoi il n'existe que des graphes orientés, si je me souviens bien... mais il s'agit d'une autre époque (sans jugement de valeur évidemment !!!).

En espérant que mes explications n'auront heurté la sensibilité de personne et qu'elles n'auront finalement pas contribué à rendre tout ça moins clair encore,

Yjp 30 août 2005 à 17:24 (CEST)

Bonjour,
Le caractère général des graphes orientés sur celui des graphes non orientés me semble effectivement l'emporter. Les présentations usuelles privilégient la distinction entre ces deux classes de graphes. Sauf si cela est déjà produit dans le présent article (suite à une inattention de ma part ;-) ), un (sous-)paragraphe pourrait être envisagé sur cette généralisation ou cette spécialisation -selon le sens d'abord- de classe de graphes d'un point de vue "plus formel" ; son positionnement serait judicieusement introductif à l'article.
Je "vote" entre autre pour l'ajout de l'opinion de Claude Berge sur l'"universalité" des graphes orientés. ;-)
YJP, bravo encore à vous pour cet article.
Cordialement, --nha de Lyon. 20 juillet 2006 à 22:46 (CEST)

[modifier] Avis aux bonnes volontés

Bonjour ! Je pense que cet article pourrait être amélioré sans trop de difficultés, mais avec un peu de travail bien sûr. On pourrait commencer par une définition simple et intuitive (celle que vous voulez, orientée ou non, ...) et quelques exemples, avant de faire des rappels historiques et de dresser la liste des notions. Par exemple dans la version http://fr.wikipedia.org/w/index.php?title=Th%C3%A9orie_des_graphes&oldid=5193979 (trouvée par hasard) la partie "définition formelle" me paraît plus accessible. Actuellement elle couvre trop de sujet : remarques historiques, différentes définitions, sans donner beaucoup d'intuition. Bien sûr, comme indiqué plus haut, on pourrait aussi scinder.Tchai 16 juin 2006 à 01:10 (CEST) J'essaierai de préparer un brouillon. En attendant, donnez moi votre avis. Voilà un début de brouillon : Utilisateur:Tchai/Théorie_des_graphes. Tchai 16 juin 2006 à 02:25 (CEST) Il faudrait recycler aussi Graphe (théorie des graphes)

  • Je viens d'ajouter au début la présentation informelle et les définitions élémentaires. Si ça convient, il faudrait récrire un peu la suite, parce que ertaines notions apparaissent maintenant deux fois. J'ai essayé de séparer la définition ensembliste des questions de représentation informatique. On peut envisager aussi un article algorithmique des graphes. IL MANQUE UN DESSIN de graphe orienté. Tchai 16 juin 2006 à 19:21 (CEST)
Bonjour,
Tchai, votre proposition de page sur la théorie des graphes semble intéressante. Certes, comme vous le soulignez, un peu de travail est utile pour poursuivre (disposez-vous vous-même suffisamment de temps à cet effet ?).
Voudriez-vous bien nous dire ce qui a été décidé concernant cette page ? Sert-elle à une ré-écriture effective de l'article actuel ou la manoeuvre est-elle interrompue ?
Par ailleurs, votre page reprend la notation (V, E) pour désigner un graphe, notation confrontée à (S, A) pour les articles en français sur les graphes ici a fortiori.
Merci de vos éclaircissements (sans diligence bien entendu ;-) ).
Cordialement, --nha de Lyon. 20 juillet 2006 à 22:32 (CEST)

[modifier] Notations

Il faudrait faire un effort important de cohérence dans les notations, notamment le nom des ensembles d'arcs et de sommets. Ce n'est jamais deux fois la même dans l'article Dans la littérature (même francophone), un graphe orienté est souvent noté (X,A) et un graphe non orienté (V,E).

En réalité, il ne semble pas avoir de normalisation sur la notation des graphes : on trouve (S, A), (X,A), (V, E) selon les sources. A moins d'exhiber LE document officiel qui précise LA notation francophone utilisée, il se trouvera toujours quelqu'un pour ne pas utiliser celle présente dans l'article. Je ne suis personnellement pas favorable à la notation (V, E) pour des raisons pédagogiques V = Vertex et E = edge n'a de sens qu'en anglais. Il est donc préférable d'utiliser S = sommet et A = arêtes ou arcs qui ont du sens en français. Ce problème de notation se posait déjà en 2004 (voir première discussion) et a conduit à la normalisation (au sens de wikipedia et probablement pas dans tous les articles) G = (S, A). Mais des ajouts nombreux dans cet article, par de multiples contributeurs redonnent encore (X, E) par exemple dans le sous-graphe, et appelle l'arbre A. je suis d'accord que cette absence de cohérence est préjudiciable à l'article. Il serait bon que l'on choisisse une notation et que l'on s'y tienne. HB 18 juillet 2006 à 10:59 (CEST)

Je ne suis pas tout à fait d'accord. En anglais, le X ne correspond pas à la première lettre de vertex. Si on garde (S,A) pour tout, A peut aussi bien vouloir dire Arête que Arc. Mais bon, si c'est ce qui a été décidé, il faut juste respecter la notation qui a été choisie, sinon on ne comprend rien.

Bonjour,
Je penche pour (S, A) en guide de notation d'un graphe dans cet article (et idéalement dans ceux qui en dérive(ro)nt). A noter que, parmi les arguments défavorables, on pourrait (ré-)évoquer le cas de la notation A pour un arbre ; si je devais faire un choix, je m'en tiendrais à (S, A) dans le cas général, et j'adopterais une notation ad hoc dans le cas particulier d'un chapitre ou d'un article spécialisé sur les arbres.
Cordialement, --nha de Lyon. 20 juillet 2006 à 23:06 (CEST)

[modifier] Applications

  • en mécanique du solide, le graphe des liaisons est un outil d'aide à la modélisation cinématique des mécanismes. Les propriétés du graphe ont parfois une signification (nb de cycle, classe etc...).
  • en électronique, il peut servir à déterminer le nombre d'équations indépendantes (loi des mailles) disponibles.

--Ruizo 17 juin 2006 à 11:28 (CEST)

Bonjour. J'ai ajouté 3 lignes dans la section <<Présentation informelle>> de l'article pour donner 2 exemples de graphe en informatique. Ces exemples ne sont sans doute pas représentatifs du domaine... Ce sont ceux qui me viennent à l'esprit (déformation professionnelle ;-) ). Avis aux critiques et à éventuellement une décision de retrait. Cordialement. --nha de Lyon 20 juillet 2006 à 23:21 (CEST)

J'ai ajouté un 3ème exemple de graphe en informatique : graphe de dépendance et parallélisme. --nha de Lyon 20 juillet 2006 à 23:33 (CEST)

il me semble utile de parler de la notion de graphe planaire dont la principale application pratique est la confection des circuits imprimés.

La notion de graphe est également utile pour la détermination des plans de circulation. Claudeh5 3 septembre 2006 à 17:56 (CEST)

[modifier] Graphe complet et clique : précision sur les notion et notation

Bonjour,

La notion de graphe complet - et conséquemment de clique - semble présenter (au moins) 2 variantes :

  • l'une considère un graphe complet et simple (à savoir : sans boucle ni arête multiple entre 2 sommets distincts) ;
  • l'autre désigne un graphe complet et réflexif (c'est-à-dire : avec autant de boucles que de sommets).

Une illustration des figures de Kuratowski correspond à la seconde variante (voir par exemple la figure 7.3 en page 131 de l'ouvrage « Éléments de mathématiques discrètes », de Louis Frécon, publié en janvier 2002 aux Presses polytechniques et universitaires romandes). Peut-être un consensus ou un usage privilégie-t-il l'une ou l'autre, auquel cas une mention serait probablement bienvenue dans l'article.

De plus, il manquerait une introduction sur la notation usuelle des graphes complets et des graphes bipartis (les notations sont cependant présentes dans les articles respectifs sur les graphes complets et les graphes planaires). Une mention sur ce point permettrait de rappeler l'origine de la notation « à la Kuratowski » : Kn, Kn,p. On pourrait éventuellement préciser si l'usage prête attention à l'ordre des indices dans le cas des graphes bipartis : ordre croissant, ordre décroissant, sans ordre.

Cordialement, --nha de Lyon. 28 juillet 2006 à 00:39 (CEST)

[modifier] A propos des algorithmes

Est-ce qu'il vous paraît utile de mettre une présentation unifiée des algorithmes relatifs aux graphes ? je pense aux Q-semi anneaux et aux matrices associées qui donnent un algorithme unique pour les problèmes de chemin minimal ou de flot ? (2 pages A4 manuscriptes) Claudeh5 28 août 2006 à 19:29 (CEST)

Bonjour,
Je suis favorable à cet ajout (d'autant que cela attise ma curiosité — en qualité d'informaticien, je n'ai pas eu connaissance de telle unification et, pourtant, j'imagine combien cela serait pratique à utiliser en programmation... ;-) ). Cette présentation concernerait-elle tout ou partie précisément de la liste des algorithmes cités dans l'article (sans que tous les items se réfèrent à des articles actuellement existants) ? Peut-être serait-il meilleur (en terme de clarté ?) de créer un article à cet effet... Autrement, je ne verrais pas d'inconvénient à ce que, dans un premier temps, vous (Claude) concrétisiez votre proposition au sein de cet article, quitte à ce que des ajustements postérieurs soient opérés en fonction d'éventuelles remarques.
Si besoin est, je serais partiellement disponible pour vous assister dans la transcription de vos pages manuscrites (moyennant une copie électronique par numérisation par exemple).
Cordialement --nha de Lyon 29 août 2006 à 23:33 (CEST)
Bonjour,
J'ai implanté la présentation qu en fin de compte est assez courte... Vous avez tout à fait le droit de la supprimer ou d ela modifier...Claudeh5 2 septembre 2006 à 20:27 (CEST)


[modifier] En plusieurs articles ?

Bonsoir,

Je serais pour séparer l'article en :

Le paragraphes sur les problèmes doit être mieux rédigé,

Ektoplastor. 01:07

D'accord ! Il a été proposé plusieurs fois ci-dessus de scinder l'article. Maintennat il faut le faire... À vous de jouer !!! Tchai 3 septembre 2006 à 10:34 (CEST)
C'est fait. Il reste à repenser le présent article, si besoin, Utilisateur:Ektoplastor, même jour, 10:45
À première vue, c'est réussi. Bravo ! Il reste quelques répétitions dans 'Exemples de représentation par des graphes' et 'Présentation informelle'. Sinon, le titre 'Liste des algorithmes de la théorie des graphes' me paraît un peu ambitieux, je vais l'écrire dans la page de discussion. Tchai 3 septembre 2006 à 19:04 (CEST)
Bonjour,
La séparation me semble également judicieuse et plutôt réussie. J'émettrais deux suggestions :
  1. De manière à favoriser la visibilité des "nouveaux" articles et des liens de cet article qui y pointent, on pourrait ajouter un lien vers Lexique de la théorie des graphes dans la section « Définitions élémentaires » et un lien vers Liste des algorithmes de la théorie des graphes dans la section « Quelques problèmes algorithmiques... » (au début ou en fin de section dans les deux cas). Il s'agirait soit d'une répétition (car des liens ont été ajoutés dans la section « Liens internes » ; mais à mon avis ils sont peu remarquables) soit d'un repositionnement (dans ce cas, les entrées correspondantes de la section « Liens internes » seraient retirées ; cependant je pencherais pour un maintien de celles-ci pour conforter l'objectif de visibilité).
  2. Dans le même sens que Tchai, je proposerais que le titre du second nouvel article soit "remanié" ("simplifié" ?) en « Algorithmes en théorie des graphes ».
Cordialement --nha de Lyon 3 septembre 2006 à 19:25 (CEST)

Je trouve étrange d'avoir une page "algorithmes en théorie des graphes" et pas plutôt "problèmes de théorie des graphes", avec des liens sur les problèmes, qui eux peuvent référencer les algos. Par exemple, où peut-on caser des explications sur les problèmes de cheminement, ceux qui sont NP, etc. ? François Clautiaux 25 octobre 2006 à 10:16 (CEST)

[modifier] relation binaire et "opération d'application"

Bonjour, Je ne comprends pas la signification de "opération d'application", ce terme n'est explicité nul part et il apparait dès la première ligne ! De plus il y a une page wiki qui renvoie à "graphe d'une fonction" ce qui est plus pertinent que le renvoie à la page fonction. De plus définir un graphe comme une relation binaire n'est pas heureux, en effet, tout d'abord on peut avoir des arêtes multiples, de plus les graphes non-orienté seraient des relations symétriques (et non pas non-orienté). J'avais pris la peine de rectifier tout ça mais apparamment en pure perte...

[modifier] sources?

je trouve que cet article est trop peu "sourcé", à part la référence au livre de Berge qui date de plus de 30 ans,,Michelbailly 16 septembre 2007 à 23:53 (CEST)