Discussion:Théorie des graphes

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)

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

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

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)

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)

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)

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)

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)

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)

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)

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)

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 » : K_n, K_n,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)

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)

En plusieurs articles ?

Bonsoir,

Je serais pour séparer l'article en :

• Théorie des graphes
• Lexique de la théorie des graphes (contenant le paragraphe définitions et classes de graphes)
• Liste des algorithmes de la théorie des graphes

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)

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...

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)

Déménageur

Contenu ancien de l'article et non encore traité

définition formelle

De nos jours on donne une définition intuitive des graphes (donnée plus bas) qui diffère en apparence de la définition donnée par Berge, mais en fait bien sûr elles sont équivalentes : Berge définit un graphe comme un triplet $(V,E,\phi )$ où $\phi$ est une fonction $\phi :E\rightarrow V\times V$.

Le vocabulaire de la théorie des graphes est ensuite emprunté à la géométrie des polyèdres. Un cas particulier de graphe est un triplet $(V,E,\phi )$ où $V$ est l'ensemble des sommets d'un polyèdre, $E$ celui des arêtes du polyèdre et où $\phi (e)=(u,v)$ si l'arête $e$ relie les deux sommets $u$ et $v$. Ce vocabulaire est conservé et d'une manière générale on dit pour tout graphe que $V$ est son ensemble de sommets, $E$ celui de ses arêtes (ou des arcs si le graphe est orienté) et $\phi$ est sa fonction d'incidence (qui à chaque arête (arc) associe un couple de sommets). Aussi on dira, quand $\phi (e)=(u,v)$, que $e$ et $u$ sont incidents (idem pour $e$ et $v$), que $u$ et $v$ sont adjacents et que ces deux sommets sont les extrémités de $e$. De deux arêtes on dit qu'elles sont adjacentes si elles sont incidentes à un même sommet. De nos jours, l'habitude est prise d'écrire explicitement qu'une arête est incidente à un sommet, donc de n'utiliser aucune notation pour la fonction d'incidence et en fait de supposer son existence. On écrit ainsi : soit $G=(V,E)$ un graphe... Cette notation n'est en fait strictement rigoureuse que pour les graphes simples.

Si le graphe est orienté, $u$ est l'extrémité initiale de $e$ et $v$ est son extrémité terminale (dans le cas non orienté ces sommets sont des extrémités tout simplement, sans autre précision). Dans les graphes orientés, deux arêtes sont consécutives si elles sont adjacentes et si leur extrémité commune est initiale pour un des deux arcs et terminale pour l'autre.

Une arête (arc) est appelée une boucle si ses deux extrémités sont identiques. Deux arêtes (arcs) sont parallèles si elles ont les mêmes extrémités (même extrémité initiale et même extrémité terminale pour les arcs). La multiplicité d'une arête (arc) est 1 si elle n'est parallèle avec aucune autre et sinon, on dit qu'elle est multiple et sa multiplicité est le nombre total (y compris elle même) de ses arêtes parallèles. Le concept de graphe orienté sans arc multiple correspond précisément à celui de relation binaire tandis que le concept de graphe non-orienté sans arête multiple correspond à celui de relation binaire symétrique.

Un graphe est dit simple s'il n'a ni boucle ni arête multiple. Le nombre maximum d'arêtes d'un graphe simple est donc $n(n-1)/2$ s'il est non-orienté et $n(n-1)$ s'il est orienté, où n est le nombre de sommets (voir graphe complet). Ces graphes correspondent aux relations binaires non-réflexives. Les graphes simples orientés sans paire d'arcs de la forme $(u,v)$ et $(v,u)$ correspondent aux relations binaires non-réflexives et antisymétriques.

théorèmes de la théorie des graphes et conséquences en algo, théorie de la complexité et optimisation combinatoire

En 1935, Théorème de Hall (généralisé par Tutte, puis Tutte-Berge) sur les couplages parfaits dans les graphes bipartis. Ce résultat allait être à l'origine de la classe co-NP, puis associé à l'algorithme du couplage parfait d'Edmonds, à l'origine de la conjecture ${\textrm {P}}={\textrm {NP}}\cap {\textrm {co-NP}}$ en Théorie de la complexité.

La seconde moitié du XX^e siècle, aura vu la théorie des graphes interagir avec de nombreux autres domaines. Au sortir de la guerre, les problèmes de flots dans les graphes ont été à l'origine de la programmation linéaire et de l'algorithme du simplexe. Les problèmes d'arbres couvrants allaient être à l'origine de la généralisation du concept de graphe par celui de matroïde et des parallèles entre les deux théories, en particulier au niveau algorithmique (ce qui influencera le vocabulaire des deux théories). Les problèmes de couplage allaient être à l'origine à la fois de la Théorie de la complexité (incluant les algorithmes d'approximation) et de l'approche polyédrique. Pour analyser l'efficacité de son algorithme de couplage, Jack Edmonds a défini le concept d'algorithme polynomial, poussant ainsi Cook à montrer l'existence du premier problème NP-complet. La facilité du problème de couplage contrastait avec la difficulté du transversal mais l'optimum difficile à obtenir est toujours borné par l'optimum facile multiplié par 2, ainsi l'algorithme de couplage max est le premier algorithme approché. Edmonds a ensuite montré que l'enveloppe convexe des couplages de tout graphe peut être décrit par un certain type d'inégalités linéaires, c'est le premier résultat polyèdral. Cette approche allait connaitre un grand succès lorsque son efficacité en pratique allait être révélée par les travaux sur le voyageur de commerce (qui est par-ailleurs le premier problème non-approximable), et son efficacité théorique par le théorème Optimisation/Séparation et les caractérisations polyédriques des graphes bipartis et des graphes parfaits.

La théorie des graphes contient de nombreux objets (chemins, arbres, couplages, cliques, colorations…) dont on peut donner une représentation simple (par le dessin). Du point de vue algorithmique, les problèmes (généralement d'optimisation) liés à ces objets peuvent être très difficiles (de par la nature "explosive" ou "exponentielle" des objets combinatoires) ou être de la plus grande simplicité (lorsque les objets ont de très fortes propriétés). Ainsi le problème de l'arbre couvrant est des plus simples (la simplicité de cette structure est captée par le concept plus général de matroïde) tandis que le problème de la coloration fait partie des plus durs à résoudre. C'est dans ce contexte, même si ses fondements appartiennent sans conteste à la logique, que la théorie de la complexité s'est développée, jusqu'à s'appliquer de nos jours à bien des domaines.

Parmi les problèmes classiques dont on connait la complexité algorithmique citons:

• La recherche de parcours Eulérien (comme dans le problème des sept ponts de Königsberg): facile (c'est-à-dire que l'on connait un algorithme polynomial de résolution)
• La connexité : existe-t-il un chemin reliant deux sommets ? : facile
• L'arbre couvrant de poids minimal : facile
• Le plus court chemin entre deux sommets d'un graphe valué : facile
• Le plus long chemin entre deux sommets d'un graphe valué : difficile (c'est-à-dire NP-complet)
• La coloration de graphe avec un nombre fixé de couleurs : difficile à partir de trois couleurs
• Les sous-graphes denses maximaux (parfois appelés cliques) : difficile
• Les problèmes de flots maximaux ou minimaux : facile si le flot peut être fractionnaire, difficile sinon à partir de trois flots entiers
• Le problème d'affectation de tâches : facile
• Le problème du voyageur de commerce : difficile
• Le problème du postier chinois : facile
• La gestion de projet avec le réseau PERT : facile
• Les graphes hamiltoniens et hypo-hamiltoniens : difficile
• La moralisation de graphe
• La triangulation de graphe : difficile dans la recherche de la triangulation optimale

Il existe bien sûr des problèmes dont la difficulté (complexité théorique) n'est pas encore établie, c'est le cas du problème fondamental de l'isomorphisme de graphe. On dit de deux graphes $G=(S,A)$ et $G'=(S',A')$ qu'ils sont isomorphes si

il existe une bijection $f:S\leftrightarrow S'$ telle que tout couple de sommets $(u,v)\in S^{2}$ on ait $(u,v)\in A$ si et seulement si $(f(u),f(v))\in A'$ ; c'est-à-dire que si l'on renomme bien les sommets de $G'$, on obtient alors $G'=G$.

Ironiquement on ne sait pas (on ne connait pas de bon algorithme pour) reconnaitre deux graphes identiques, pire on ne sait pas si ce problème est facile ou difficile !

• Isomorphisme de graphes : difficulté inconnue (aucun algorithme polynomial connu et aucune réduction polynomiale connue d'un problème NP-complet à ce problème)

Récente modif

Bonjour, je crois vraiment qu'il faut bien retravailler cette page. Il existe beaucoup d'articles et il faudrait pointer vers eux (flots, spectral) ou faire de différentes pages. A mon avis l'objectif de cette page doit être triple:

1) Bien présenter la théorie, ses particularités. Il faut bien introduire les objets et bien poser les problématiques centrales de la théorie. Ne pas confondre théorie des graphes et applications de la théorie des graphes.

2) Bien définir l'intérêt théorique, les liens entre les objets (théorèmes min-max), voir par exemple "Beautiful conjectures in graph theory" sur la page web d'Adrian Bondy pour les questions actuelles.

3) Traiter des applications et des interactions avec les autres matières. Par exemple, l'approche probabiliste (cf Spencer Alon) fait-elle partie de la théorie des graphes ou sont-ce les graphes qui deviennent objet d'étude de la proba ?

Un dernier point fondamental est que, par nature, le théorie des graphes part dans tous les sens. Il y a donc divers chapelles, et il ne faut pas ici en privilégier une sur les autres. C'est pourquoi il me semble que les parties spécifiques (telles théorie spectrales, ou proba) doivent faire partie de pages annexes citées dans cette page. Cette page doit être axée sur les définitions (comme chemin, couplage, coloration) et les problématiques de base de la théorie, à savoir la connexité, les packing/covering (stables, couvertures, coloration), puis éventuellement les autres comme : rigidité, proba, plongements, spectrale... Tout ce qui est matrice, programmation linéaire etc et venu a posteriori donner d'autres explications (très enrichissantes) de résultats connus, on doit en parler mais pas en détail dans la page principale. Tou chti (d) 19 février 2009 à 13:15 (CET)

Bonjour. Je suis d'accord pour le travail énorme qu'il reste à faire. On a quelques divergences sur les directions. Berge a fait de grandes contributions, et j'ai fait mon possible pour le mentionner clairement, mais commencer directement avec lui et le mettre sur un piédestal est excessif. Soit on respecte un semblant d'ordre chronologique, soit on fait par thématiques, mais là c'est un peu entre les deux. Par ailleurs, il faudrait utiliser les sources. Par exemple "elle vient même de s'enrichir d'un nouveau théorème majeur, le théorème des graphes parfaits" mériterait d'avoir une référence vers l'article. Je ne pense pas qu'enlever totalement les applications de la théorie de l'introduction soit aussi une bonne idée : si on s'intéresse aux graphes, c'est aussi parce qu'ils servent à quelque chose. Je trouve aussi que l'introduction dans son ensemble a perdu en lisibilité. Les champs d'applications devraient être à la fin, et mentionnés parfois dans les développements, qui devraient suivre l'introduction. Je vais faire quelques modifications, mais tomber sur un article qui est un peu sans dessus-dessous tout d'un coup n'est pas quelque chose que j'aime, je préfère quand on prépare le terrain avant... Philippe Giabbanelli (d) 19 février 2009 à 22:23 (CET)

Modifications

La partie Définition formelle et vocabulaire standard a été reprise quasiment à l'identique, de même pour Une première description. L'introduction proposée était source de confusion et donc j'ai gardé uniquement ces deux parties. Pourquoi est-ce que je pense qu'il y a confusion :

• Je ne vois pas à quoi ça sert de mettre trois 'questions typiques' au début. Tout l'article traite de questions et de solutions. S'il y a des questions utiles, elles peuvent être développées dans la partie liée à leur théorie. S'il y a des questions qui méritent d'être mentionnées pour leurs vertus pédagogiques, d'une part il faut le démontrer, et d'autre part il serait plus indiqué de le faire dans un paragraphe dévolu à l'enseignement de la théorie des graphes.
• L'intérêt pratique devrait être souligné à chaque fois que l'on discute une théorie. Cet intérêt est bien sûr immense, et en faire une partie au début est une tentation de retourner aux listes bric à brac qu'avait l'ancienne version de l'article. On pourrait à la rigueur développer sur une étude de cas en fin d'article ? De même pour l'intérêt théorique.
• De façon générale, faire une "aperçu" de l'intérêt en théorie et en pratique est un mini-résumé de l'article et il devrait être dans les premières lignes de l'introduction. J'y ai mit deux intérêts pratiques parmi d'autres. Toute idée pour rajouter des intérêts théoriques est la bienvenue.
• Claude Berge et les graphes parfaits sont déjà introduits dans l'origine. Il n'y a aucune raison de commencer avec Berge et il est totalement abusif de dire qu'il a inventé la théorie, et sa portée à l'étranger est très limitée. C'est un peu cocorico. Quant à Dieudonné et ce qu'il pense des quatre couleurs, ça pourrait être mentionné dans l'article sur les quatre couleurs, mais au sein d'une synthèse ?...

Cordialement Philippe Giabbanelli (d) 19 février 2009 à 23:44 (CET)

Proposition de plan

Suite aux remarques, il y a bien déséquilibre entre les aspects, ce qui est normal puisque certains manquent totalement. Je propose donc de discuter sur l'idée suivante :
1) Définition de graphe et vocabulaire
2) Origines
3) Représentations et invariants
...3.1) Étiquetage et morphismes
...3.2) De la matrice d'adjacence à la théorie spectrale
...3.3) Mesures sur les graphes
4) Opérations
...4.1) Produits
...4.2) Contractions et mineurs
...4.3) Décompositions arborescentes et en branches
5) Problèmes fondamentaux
...5.1) Couplage
...5.2) Coloration
...5.3) ...
6) Aspects algorithmiques
...6.1) Structures de données
...6.2) Sous-graphes utiles : séparateurs, spanners et arbres de Steiner
...6.3) Réduction de données
7) Processus
...7.1) Graph searching
...7.2) Diffusion
...7.3) Commérage
8) Extensions
...8.1) Flots
...8.2) Probabilités
...8.3) Hypergraphe

Il me paraît important de bien définir les objets avant de commencer à les manipuler, ce qui est la raison pour laquelle les connaissances que l'on a sur les morphismes, la théorie spectrale et les différentes opérations sont introduites avant les problèmes 'fondamentaux'. Ces opérations et théories permettent de jeter de nouveaux éclairages sur ces problèmes, en apportant des parallèles intéressants. C'est anachronique, mais d'un point de vue pédagogique il me semble que seule la section historique origine devrait respecter la chronologie. Après les problèmes fondamentaux, on pourrait passer dans des problèmes plus informatiques, ce qui donne le parallèle à ceux purement des graphes : d'abord représenter les structures, puis les manipuler. Enfin, les extensions notables devraient venir en dernier. Qu'en pensez-vous ? Qui peut faire quoi ? Philippe Giabbanelli (d) 20 février 2009 à 05:58 (CET)

Si j'ai bien compris, il n'y aurait pas de partie sur l'histoire de la théorie des Graphes en dehors des "origines" ? ---- El Caro ^bla 21 février 2009 à 21:21 (CET)

C'est du moins ma proposition initiale. Pour chacun des aspects, ses principaux éléments doivent quoiqu'il en soit être introduits et constituent donc un historique. Par exemple, si quelqu'un souhaite un historique dans l'extension en probabilités, cette section fournie déjà les travaux les plus marquants ce qui revient à faire un historique. Ceci étant, on peut bien sûr structurer la section origines en sous-sections. Je n'ai pas d'idée particulière pour cela. Suggestions ? Philippe Giabbanelli (d) 21 février 2009 à 21:25 (CET)

Je crains que "mélanger" un concept avec son histoire risque de mener à une certaine confusion. N'y a-t-il pas eu, au cours de l'histoire, des polémiques, des erreurs intéressantes à mentionner... bref, des tas de trucs passionnants mais qui peuvent mener à des digressions, donc nuire à la bonne compréhension de l'article par un lecteur non averti ? Mais ce n'est qu'un principe général que j'énonce : je ne connais pas le sujet . Donc tu fais suivant ton inspiration, si tu penses que ces écueils seront évités. ---- El Caro ^bla 22 février 2009 à 15:48 (CET)

Un point bizarre dans la nouvelle version

Je relève un point bizarre:

Un sous-graphe couvrant est appelé un k-facteur si chacun de ses sommets a k arêtes et les premiers théorèmes furent donnés par Julius Petersen[A 12]; par exemple, il montra qu'un graphe peut être séparé en 2-facteurs si et seulement si tous les sommets ont un nombre pair d'arêtes (mais il fallut attendre 50 ans pour que Bäbler traite le cas impair[A 13]).

Mais un 2-facteur est un ensemble de cycles disjoints (puisque chaque sommet a degré 2). Donc un graphe est séparable 2-facteurs si et seulement si (chacune de ses composantes connexes) est Eulérienne. Mais d'après A2, à l'époque de A12 on connait déjà le théorème d'Euler. Tou chti (d) 24 février 2009 à 12:52 (CET)

Sous-graphe couvrant

De plus, "sous-graphe couvrant" ça veut dire : le graphe de départ !

Pas nécessairement. Le sous-graphe couvrant aura les mêmes sommets que le graphe de départ, mais l'ensemble des arcs peut être plus petit. Fais un exemple sur un graphe complet. Philippe Giabbanelli (d) 8 septembre 2009 à 17:59 (CEST)

« à ne pas confondre avec le graphe d'une fonction  »

Comme ensemble de couples le graphe d'une fonction est aussi un graphe orienté, non ? Je serais plutôt pour dire ".... dont le graphe d'une fonction n'est qu'un cas particulier". ---Michel421 (d) 15 mars 2009 à 10:47 (CET)

C'est vrai que pour toute fonction f de E dans F on peut construire un graphe (au sens théorie des graphes) dont l'ensemble des sommets est E est dont les arêtes sont le graphe (au sens de l'analyse fonctionnelle) de f. Mais dire ".... dont le graphe d'une fonction n'est qu'un cas particulier" ne serait tout de même pas rigoureux puisque les graphes de l'analyse fonctionnelle ne sont pas des couples du même type que les couples définissant les graphes de la théorie des graphes. Au contraire je crois qu'il faut souligner le fait que le terme graphe est ambivalent. Tou chti (d) 13 mai 2009 à 16:26 (CEST)

définition d'un arbre

Dans le lexique de la théorie des graphes associé à cet article, ainsi que dans le texte de cet article, un arbre est défini comme un graphe connexe acyclique.

Je me demande si cette définition est suffisante, car il est une propriété supplémentaire qui se retrouve dans tous les exemples d'arbres donnés dans la suite de l'article, et qui selon mon expérience est toujours implicite lorsqu'un informaticien parle d'arbre.

Il s'agit d'autoriser ou non plusieurs chemins d'un sommet à un autre : un graphe orienté connexe acyclique permet que plusieurs chemins différents mènent d'un sommet à un autre, alors que tous les exemples d'arbres donnés dans l'article aussi bien que tous les emplois du mot 'arbre' que j'ai rencontrés par ailleurs n'autorisent qu'un seul chemin. Je pense qu'il faudrait :

• soit compléter la définition d'un arbre si la définition existante ne repose pas sur un usage établi dans certains domaines
• soit mettre en garde contre la différence qu'il y a entre cette définition existante et l'usage courant (qui n'engage que moi) en informatique

Quelqu'un saurait-il si la définition d'un arbre comme étant un graphe connexe acyclique est valide et établie dans certain domaine (mathématiques ?) ? ou si cette définition est admissible dans le domaine de l'informatique (ce que je ne crois pas) ? Cjf (d) 22 septembre 2009 à 15:08 (CEST)

Le "acyclique" t'empéche d'avoir plusieurs chemins d'un sommet à un autre... Koko90 (d) 22 septembre 2009 à 15:34 (CEST)

Le "acyclique" empêche en effet d'avoir plusieurs chemins d'un sommet à un autre, mais pour un graphe non orienté. Pour un graphe orienté, "acyclique" signifie "absence de circuit dont les deux sommets extrémités sont identiques", ce qui n'interdit pas plusieurs chemins d'un sommet à un autre. C'est ce cas précis qui me semble admis selon la définition générale d'un arbre, mais qui me semble toujours écarté dans les utilisations du concept d'arbre.

J'ai recherché dans les articles anglais, et là "tree" est défini différemment en maths et en info :

• dans tree (graph theory), "tree" se limite aux graphes non orientés, et il y a une mise en garde "The various kinds of trees used as data structures in computer science are not really trees in this sense [...]"
• dans tree (data structure), "tree" exclue explicitement ce cas ("It is an acyclic connected graph where each node has [...] at most one parent node", "A node has at most one parent", etc...)

Peut-être que si on a en tête des graphes orientés, c'était mon cas, et je pense que c'est implicite pour un informaticien car les relations entre les données sont rarement symétriques, alors la définition existante peut être mal comprise dans ce contexte, c'est ce qui m'est arrivé. En maths un graphe est sans doute implicitement non orienté ce qui valide la définition dans ce contexte.Cjf (d) 22 septembre 2009 à 18:22 (CEST)

Bien entendu je pensais au cas des graphes non orientés. Il faut juste ajouter non orienté à la définition d'arbre. Koko90 (d) 23 septembre 2009 à 13:43 (CEST)

Place de la typologie

 Goel : Bonjour, il me semble que la typologie des graphes ne devrait pas être si haut dans l'article : c'est un aspect qui n'est important que si on se place selon un certain point de vue (modélisation, réseaux sociaux). Je connais plein de cours de graphes qui n'en parle pas du tout. Je propose de la déplacer ailleurs dans l'article. Et en passant, il faudrait des références . --Roll-Morton (discuter) 20 avril 2016 à 10:54 (CEST)

Pas de souci pour la déplacer. Je l'avais mis si haut car c'est un point structurant et généraliste.

Palette de navigation ?

Je me demande s'il ne faudrait pas créer une palette de navigation spécifique à la théorie des graphes, avec une partie contenant la liste des graphes ayant une page wikipedia, une liste des divers polynômes associés aux graphes, etc. Cela permettrait de naviguer plus facilement d'un article à l'autre concernant les graphes et d'avoir une vision plus globale des articles relatifs aux graphes. Theon (discuter) 13 septembre 2020 à 18:46 (CEST)

Voisins et boucles

Le mot "voisin" est utilisé maintes fois, mais défini nulle part. Aussi lit-on:

pour autoriser les boucles les définitions doivent être étendues

or, en vérité, les définitions sont simplifiées, raccourcies, et plus naturelles dans ce cas. Je ne comprends pas bien pourquoi on interdit les boucles a priori (d'autant plus que dans les graphes de relations binaires on aime avoir des boucles: réflexivité <=> ∀x: x ~ x; fonction identité <=> ∀x: f(x) = x, ...), pour les réintroduire a posteriori comme "complication" (alors que c'est le contraire). — MFH 21 avril 2021 à 23:40 (CEST)