Voir la source de Graphe (mathématiques discrètes)

{{Voir homonymes|Graphe}}
{{Confusion|Graphe d'une fonction}}
Dans le domaine des [[mathématiques discrètes]], la [[théorie des graphes]] définit le '''graphe''', une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés ''[[Sommet (théorie des graphes)|sommets]]'' (ou ''nœuds'' ou ''points''), et les relations entre eux sont nommées ''[[Arête (théorie des graphes)|arêtes]]'' (ou ''liens'' ou ''lignes'')<ref>{{harvsp|Trudeau|1993|p=19}} : {{Citation étrangère|langue=en|A graph is an object consisting of two sets called its ''vertex set'' and its ''edge set''.}}</ref>. On distingue les [[Graphe non orienté|graphes non orientés]], où les arêtes relient deux sommets de manière [[Relation symétrique|symétrique]], et les [[Graphe orienté|graphes orientés]], où les arêtes, alors appelées ''arcs'' (ou ''flèches''), relient deux sommets de manière [[Relation asymétrique|asymétrique]].

Les graphes sont couramment [[Représentation graphique|représentés graphiquement]] à l'aide de cercles pour les sommets et de lignes (éventuellement courbées) pour les arêtes, ces dernières étant munies de flèches s'il y a une orientation. Lorsque les graphes sont très grands, la taille des sommets est souvent fonction du nombre de leurs relations (le [[Degré (théorie des graphes)|''degré'']]).
<gallery>
Fichier:6n-graf.svg|Un graphe avec six sommets et sept arêtes.
Fichier:6n-graph3.svg|Le même graphe, pivoté et avec les arêtes étiquetées.
Fichier:Dominance drawing.svg|Un graphe orienté à sept sommets.
Fichier:Social Network Analysis Visualization.png|Un graphe contenant des centaines de sommets.
</gallery>

Le mot {{Citation étrangère|langue=en|graph}} a été utilisé pour la première fois dans ce sens par [[James Joseph Sylvester]] en 1878<ref>
Dans : {{article|auteur=J. J. Sylvester|titre=Chemistry and algebra|périodique=Nature|volume=17|date=7 février 1878|doi=10.1038/017284a0|url=https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false|passage=284 : « Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph. »}}. Et : {{article|auteur=J. J. Sylvester|titre=On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, — with three appendices|périodique=American Journal of Mathematics, Pure and Applied|volume=1|numéro=1|date=1878|doi=10.2307/2369436|url=https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false|pages=64–90|passage=65 : "Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph."}}.</ref>{{,}}<ref>{{harvsp|Gross|Yellen|2004|loc =[https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35&lpg=PA35 p.35]}}.</ref>.

== Définition et vocables associés ==
{{Article connexe|Glossaire de la théorie des graphes}}
[[Fichier:Undirected.svg|vignette|Un graphe avec trois sommets et trois arêtes.|150x150px]]
[[Fichier:Directed.svg|vignette|Un graphe orienté avec trois sommets et quatre arcs.|150x150px]]
Un graphe est un [[Couple (mathématiques)|couple]] {{Math|§=''G'' = (''V'', ''E'')}} comprenant deux [[Ensemble|ensembles]] :
* {{Math|§=''V''}} : [[Sommet (théorie des graphes)|sommets]] ;
* {{Math|§=''E''}} : [[Arête (théorie des graphes)|arêtes]], chacune étant associée à un couple {{Math|§=(''u'', ''v'')}} ou une [[paire]] {{Math|§={''u'', ''v''}<nowiki/>}} de sommets ({{Math|''u'', ''v'' ∈ ''V''}}).

Des définitions plus restreintes pour {{Math|§=''E''}} sont souvent employées :

* {{Math|§=''E'' ⊆ {<nowiki/>{''u'', ''v''} {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup> ∧ ''u'' ≠ ''v''}<nowiki/>}} : chaque arête est une paire de sommets distincte des autres. {{Math|§=''G''}} est alors un ''[[graphe simple]] [[Graphe non orienté|non orienté]]<ref>{{Ouvrage|langue=en|prénom1=Edward A.|nom1=Bender|prénom2=S. Gill|nom2=Williamson|titre=Lists, Decisions and Graphs|sous-titre=With an Introduction to Probability|passage=148|éditeur=|année=2010|pages totales=251|isbn=|lire en ligne=https://books.google.fr/books?id=vaXv_yhefG8C}}</ref>{{,}}<ref>Par exemple {{harv|Iyanaga|Kawada|p=234|1977}} ou {{harv|Biggs|1993|p=4}}.</ref>''.
* {{Math|§=''ϕ'' : ''E'' → {<nowiki/>{''u'', ''v''} {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup>}<nowiki/>}} : chaque arête est associée par la fonction d'incidence {{Math|§=''ϕ''}} à une paire de sommets (ou à un [[Singleton (mathématiques)|singleton]] si {{Math|§=''u'' = ''v''}}). {{Math|§=''G''}} est alors un ''multigraphe non orienté''. Ce n'est plus un couple mais un [[Uplet|triplet]] {{Math|§=''G'' = (''V'', ''E'', ''ϕ'')}}<ref name="B&W">{{Ouvrage |langue=en |prénom1=Edward A. |nom1=Bender |prénom2=S. Gill |nom2=Williamson |titre=Lists, Decisions and Graphs |sous-titre=With an Introduction to Probability |éditeur= |année=2010 |pages totales=251 |passage=149 |isbn= |lire en ligne=https://books.google.fr/books?id=vaXv_yhefG8C}}</ref>{{,}}<ref name="GGL p5">Par exemple {{harv|Graham et. al.|1995|id=GGL|p=5}}.</ref>.
* {{Math|§=''E'' ⊆ {(''u'', ''v'') {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup> ∧ ''u'' ≠ ''v''}<nowiki/>}} : chaque arête est un couple distinct des autres, de deux sommets distincts l'un de l'autre. {{Math|§=''G''}} est alors un ''graphe simple [[Graphe orienté|orienté]]''. Les arêtes sont plus souvent appelées arcs, et leur ensemble {{Math|§=''A''}} plutôt que {{Math|§=''E''}}.
* {{Math|§=''ϕ'' : ''E'' → {(''u'', ''v'') {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup>}<nowiki/>}}, avec {{Math|§=''G'' = (''V'', ''E'', ''ϕ'')}} : chaque arc est associé par la fonction d'incidence {{Math|§=''ϕ''}} à un couple de sommets. {{Math|§=''G''}} est alors un ''multigraphe orienté'' (ou [[Carquois (théorie des catégories)|carquois]]).
* {{Math|§=''G'' = (''V'', ''E'', ''A'')}}, avec {{Math|§=''E'' ⊆ {<nowiki/>{''u'', ''v''} {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup> ∧ ''u'' ≠ ''v''}<nowiki/>}} et {{Math|§=''A'' ⊆ {(''u'', ''v'') {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup> ∧ ''u'' ≠ ''v''}<nowiki/>}} : {{Math|§=''G''}} est un ''graphe mixte simple''.
* Finalement, la définition la plus générale : {{Math|§=''G'' = (''V'', ''E'', ''A'', ''ϕ<sub>E</sub>'', ''ϕ<sub>A</sub>'')}}, avec {{Math|§=''ϕ<sub>E</sub>'' : ''E'' → {<nowiki/>{''u'', ''v''} {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup>}<nowiki/>}} et {{Math|§=''ϕ<sub>A</sub>'' : ''A'' → {(''u'', ''v'') {{!}} (''u'', ''v'') ∈ ''V''<sup>2</sup>}<nowiki/>}}. {{Math|§=''G''}} est alors un ''multigraphe mixte''.
Plus vulgairement :
* Un graphe ''simple'' ne comporte ni [[Boucle (théorie des graphes)|boucles]] (arêtes {{Math|§={''u''<nowiki>}</nowiki>}} ou arcs {{Math|§=(''u'', ''u'')}}, c.-à.-d. joignant un sommet à lui-même) ni arêtes multiples (arêtes étant associées au même duo de sommets). Pour expliciter le fait qu'un graphe peut comporter des boucles et des arêtes multiples, on peut employer le terme ''multigraphe''.
* Un graphe ''orienté'' est un graphe dans lequel toutes les arêtes possèdent une orientation et sont alors qualifiées d'arcs. Un graphe ''mixte'' comporte à la fois des arêtes non orientées et des arcs.

[[Fichier:Weighted_network.png|vignette|Un graphe pondéré avec dix sommets et douze arêtes.]]Les arêtes et arcs sont des objets abstraits reliant deux sommets. Ils peuvent comporter d'autres propriétés. Très souvent, il s'agit d'un nombre, auquel cas le graphe est dit ''pondéré'' ou ''valué''. Ce nombre, appelé poids, peut représenter par exemple des coûts, des longueurs ou des capacités. De nombreux problèmes et algorithmes sont associés aux graphes pondérés, entre autres le [[problème de plus court chemin]] et le [[problème du voyageur de commerce]].

Pour une arête {{Math|§={''u'', ''v''<nowiki>}</nowiki>}} ou un arc {{Math|§=(''u'', ''v'')}}, {{Math|§=''u''}} et {{Math|§=''v''}} sont les ''extrémités'' de l'arête. L'arête ''joint'' {{Math|§=''u''}} et {{Math|§=''v''}} et est ''incidente'' à {{Math|§=''u''}} ainsi qu'à {{Math|§=''v''}}. {{Math|§=''u''}} et {{Math|§=''v''}} sont dits ''liés'', ''connectés'', ''adjacents'' ou encore ''voisins''. L'arête est ''adjacente'' aux autres arêtes incidentes à {{Math|§=''u''}} ou à {{Math|§=''v''}}. Dans le cas d'un arc, il ''sort'' de {{Math|§=''u''}} et ''entre'' dans {{Math|§=''v''}}, et {{Math|§=''v''}} est ''consécutif'' à {{Math|§=''u''}}. L'arc est ''consécutif'' aux arcs entrant dans {{Math|§=''u''}}. Les arêtes induisent une [[relation binaire]] ([[Relation symétrique|symétrique]] pour une arête non orientée, [[Relation asymétrique|asymétrique]] pour un arc) {{Math|§=~}} sur {{Math|§=''V''}} appelée ''relation d'adjacence'' de {{Math|§=''G''}} : {{Math|§=''u'' ~ ''v''}} signifie « {{Math|§=''u''}} est adjacent à {{Math|§=''v''}} ».

L'''ordre'' d'un graphe est son nombre de sommets ({{Math|§={{!}}''V''{{!}}}}). La ''taille'' d'un graphe est son nombre d'arêtes ({{Math|§={{!}}''E''{{!}}}}). Le ''[[Degré (théorie des graphes)|degré]]'' (ou la ''valence'') d'un sommet est le nombre d'arêtes incidentes à ce sommet, où une boucle compte double. On peut distinguer le degré ''sortant'' et le degré ''entrant'', qui dénombrent seulement soit les arcs sortants soit les arcs entrants. Dans un graphe simple non orienté d'ordre {{Math|§=''n''}}, le degré maximum d'un sommet est {{Math|§=''n'' − 1}} et la taille maximale du graphe est {{Math|§=''n''(''n'' − 1)/2}}.

{{Math|§=''V''}} et {{Math|§=''E''}} sont en général supposés finis. De nombreux résultats cessent d'être vrais (ou ont des énoncés différents) pour les ''graphes infinis'' car certains [[Démonstration (logique et mathématiques)|arguments de preuve]] ne se transposent pas au cas infini. {{Math|§=''V''}} et {{Math|§=''E''}} peuvent être vides ([[Graphe nul|graphe ''nul'']], et bien entendu {{Math|§=''V'' = ∅ ⇒ ''E'' = ∅}}), bien que {{Math|§=''V''}} soit généralement conçu comme non vide. Si {{Math|§={{!}}''V''{{!}} = 1}} et {{Math|§=''E'' = ∅}}, le graphe est dit ''trivial''.

Un graphe est ''étiqueté aux sommets'' si chaque sommet porte une étiquette ; il est ''étiqueté aux arêtes'' si chaque arête porte une étiquette. On peut considérer, dans les problèmes d'[[Algorithme d'énumération|énumération]] ou de [[bijection]], des graphes étiquetés ou non étiquetés. Un graphe dont les sommets (ou parfois les arêtes) sont étiquetés par des couleurs est un graphe ''coloré'', qui peut être une réponse à un problème de [[coloration de graphe]].

== Classes ==
De nombreux types de graphes ont été définis.

=== Graphe asymétrique ===
{{Article détaillé|Graphe asymétrique|Graphe symétrique}}
Un ''graphe asymétrique'' (en anglais {{Citation étrangère|langue=en|oriented graph}}, alors qu'un graphe orienté est appelé {{Citation étrangère|langue=en|directed graph}}) est un graphe orienté où l'un au plus des couples {{Math|§=(''u'', ''v'')}} et {{Math|§=(''v'', ''u'')}} est une flèche du graphe. Un tel graphe est sans boucle. On peut le voir comme résultant du choix d'une orientation pour chaque arête d'un graphe non orienté sans boucle.

=== Graphe régulier ===
{{Article détaillé|Graphe régulier}}
Un ''graphe régulier'' est un graphe où tous les sommets ont même degré. Si ce degré est ''k'', on parle aussi de graphe ''k''-régulier.

{{Article connexe|Graphe fortement régulier|Graphe distance-régulier}}

=== Graphe complet ===
{{Article détaillé|Graphe complet}}
[[Fichier:Complete graph K7.svg|vignette|Le graphe complet à 7 sommets.]]

Un ''graphe complet'' est un graphe simple dont les sommets sont tous adjacents les uns aux autres, c'est-à-dire tel que tout couple de sommets distincts est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux flèches (une dans chaque sens).

=== Graphe fini ===
Un ''graphe fini'' est un graphe ayant un nombre fini de sommets et d'arêtes. Dans le cas contraire, c'est un ''graphe infini''. Le plus souvent, les graphes considérés sont tacitement supposés finis ; s'ils sont infinis, ceci est spécifié explicitement.

=== Graphe connexe ===
{{Article détaillé|Graphe connexe|Composante fortement connexe}}
Un ''graphe connexe'' est un graphe non orienté où toute paire de sommets est reliée par une chaîne. Un graphe orienté, est connexe si le graphe non orienté obtenu en oubliant les orientations des arêtes est connexe. Il est ''fortement connexe'' si tout couple de sommets est relié par un chemin, donc si pour tout couple {{Math|§=(''u'', ''v'')}} de sommets, il y a un chemin de {{Math|§=''u''}} à {{Math|§=''v''}} et un chemin de {{Math|§=''v''}} à {{Math|§=''u''}}. Un graphe ''[[graphe sommet-connexe|k-sommet-connexe]]'' est un graphe qui possède au moins ''k''+1 sommets et qui reste encore connexe après en avoir ôté ''k''–1 ; de même, un graphe ''[[Graphe arête-connexe|k-arête-connexe]]'' est un graphe qui reste connexe quand on lui enlève ''k''–1 arêtes.

=== Graphe biparti ===
{{Article détaillé|Graphe biparti}}
[[Fichier:Graph K3-3.svg|vignette|Un graphe biparti complet.]]

Un ''graphe biparti'' est un graphe dont l'ensemble des sommets peut être [[Partition d'un ensemble|partitionné]] en deux ensembles ''X'' et ''Y'' de telle sorte qu'il n'y a pas d'arête entre deux sommets de ''X'' ni entre deux sommets de ''Y''. De manière équivalente, un graphe biparti est un graphe dont le [[Coloration de graphe|nombre chromatique]] est 2.

Un [[graphe biparti complet]] est un graphe biparti où tous les sommets de ''X'' sont reliés à tous les sommets de ''Y'' et vice-versa.

=== Chaîne ===
{{Article détaillé|Chaîne (théorie des graphes)}}
Un graphe est une ''chaîne'' d'ordre {{Math|§=''n'' ≥ 2}} s'il est composé de sommets {{Math|§=''n''}} qu'on peut numéroter de telle sorte que les arêtes sont {{Math|§={''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>}<nowiki/>}} pour {{Math|§=''i'' = 1, 2, …, ''n'' − 1}}. Une chaîne est, de manière équivalente, un graphe connexe dont tous les sommets sont de degré 2 sauf deux qui sont de degré 1. Une chaîne dans un graphe est un [[Lexique de la théorie des graphes|sous-graphe partiel]] de ce graphe.

=== Graphe planaire ===
{{Article détaillé|Graphe planaire}}
Un ''graphe planaire'' est un graphe que l'on peut dessiner dans le plan (ou sur une sphère) sans que deux arêtes ne se croisent.

=== Graphe cycle ===
{{Article détaillé|Graphe cycle}}
Un ''graphe cycle'' d'ordre <math>n\ge3</math> ou ''n-cycle'' est un graphe dont les sommets peuvent être numérotés <math>v_1,\ldots,v_n</math> de sorte que les arêtes sont les paires <math>[v_i,v_{i+1}]</math> pour <math>i=1,\ldots,n-1</math> plus l'arête <math>[v_n,v_1]</math>. Un [[graphe cycle]] peut être caractérisé comme étant un graphe connexe dont tous les sommets ont degré 2.

=== Arbre ===
{{Article détaillé|Arbre (théorie des graphes)}}
Un ''arbre'' est un graphe connexe acyclique.

Une ''forêt'' est un graphe acyclique, c'est-à-dire une union disjointe d'un ou plusieurs arbres.

=== Autres ===
* [[Graphe orienté acyclique]]
* [[Graphe de Petersen]] et ses généralisations
* [[Graphe parfait]]
* [[Cographe]]
* [[Graphe cordal]]
* En fonction du [[Automorphisme de graphe|groupe d'automorphisme]] : [[graphe sommet-transitif]], [[graphe symétrique]], et [[graphe distance-transitif]]

== Centralité ==
{{Article détaillé|Centralité}}
Dans l'analyse de graphes, la centralité mesure la pertinence et l'importance d'un sommet. On distingue :
* la ''centralité de degré'' qui utilise le degré ;
* la ''centralité de proximité'' qui utilise l'inverse de la somme des distances à tous les autres sommets ;
* la ''centralité d'intermédiarité'' qui utilise le nombre de plus courts chemins passant par le sommet<ref>{{Article
|prénom1=Xingqin|nom1=Qi
|prénom2=Eddie|nom2=Fuller
|prénom3=Qin|nom3=Wu
|prénom4=Yezhou|nom4=Wu
|titre=Laplacian centrality: A new centrality measure for weighted networks|périodique=Information Sciences|volume=194|date=2012-07|issn=0020-0255|doi=10.1016/j.ins.2011.12.027|consulté le=2019-06-18|pages=240–253}}.</ref>.

D'autres mesures sont l'[[Lexique de la théorie des graphes#E|excentricité]] d'un sommet qui est la distance maximale à tout autre sommet, le [[Diamètre (théorie des graphes)|diamètre]] d’un graphe ainsi que le [[Rayon (théorie des graphes)|rayon]].

== Opérations sur les graphes ==
Les diverses opérations qui produisent de nouveaux graphes à partir de graphes donnés peuvent être regroupées en :
* ''opérations unaires'', qui créent un nouveau graphe à partir d'un ancien, comme :
** [[contraction d'arête]],
** [[line graph]],
** [[graphe dual]],
** [[graphe complémentaire]],
** [[Réécriture (informatique)|réécriture]] de graphes.
* ''opérations binaires'', qui créent un nouveau graphe à partir de deux anciens, comme :
** [[union disjointe]] de graphes,
** [[Produit cartésien (graphe)|produit cartésien]],
** [[Produit tensoriel (graphe)|produit tensoriel]],
** [[Produit fort (graphe)|produit fort]],
** produit lexicographique,
** [[graphe série-parallèle]].

== Applications ==
[[Fichier:Cayley graph of F2.svg|vignette|upright=1.2|Le graphe de Cayley du [[groupe libre]] sur ''a'' et ''b''.]]
[[Fichier:Saccharin-2D-skeletal.png|thumb|upright=0.8|Molécule de [[saccharine]].]]
* En [[théorie des catégories]], une catégorie peut être représentée par un multigraphe orienté dont les sommets représentent les objets et les arêtes les [[morphisme]]s. Un [[foncteur]] entre catégories induit un [[morphisme de graphes]].
* En [[informatique]], les graphes orientés sont utilisés pour représenter des notions comme les [[Graphe conceptuel|graphes conceptuels]], les [[Automate fini|automates finis]] et de nombreuses autres structures discrètes. Il est également possible de modéliser le fonctionnement d'un [[Réseau de neurones artificiels|réseau neuronal]] artificiel, ou encore le schéma décisionnel d'une [[intelligence artificielle]].
* Une [[relation binaire]] ''R'' sur un ensemble ''X'' définit un graphe orienté (et réciproquement). Il y a une flèche de ''x'' à ''y'' dans le graphe si et seulement si ''xRy''.
* Un graphe peut modéliser des informations sur des [[réseau social|réseaux sociaux]], comme la notion de « follower » dans [[X (réseau social)|Twitter]]<ref name="snatwitter">{{article | volume = 3| numéro = 1| nom = Grandjean| prénom = Martin| titre = A social network analysis of Twitter: Mapping the digital humanities community| journal =Cogent Arts & Humanities| date = 2016| pages = 1171458| url = http://cogentoa.tandfonline.com/doi/full/10.1080/23311983.2016.1171458| doi=10.1080/23311983.2016.1171458}}</ref>{{,}}<ref name="twitterwtf">Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter], ''Proceedings of the 22nd international conference on World Wide Web''. {{doi|10.1145/2488388.2488433}}.</ref>.
* Des exemples de graphes orientés réguliers sont les [[Graphe de Cayley|graphes de Cayley]] de groupes finiment engendrés, ou le {{Lien|langue=en|trad=Schreier coset graph|fr=graphe des cosets de Schreier}}.
*En [[chimie]] et notamment dans la représentation simplifiée des [[Liaison chimique|liaisons entre atomes]] formant une [[molécule]], des graphes en général non orientés mais avec des arêtes multiples sont largement utilisés.

== Extensions ==
Les graphes se généralisent dans plusieurs directions :
* Dans un [[hypergraphe]], une arête peut relier plus de deux sommets.
* Un graphe non orienté peut être vu comme un [[complexe simplicial]] dont les 1-[[Simplexe]]s sont les arêtes et les 0-simplexes les sommets. Sous cet aspect, les complexes simpliciaux sont des généralisation des graphes à des dimensions plus élevées.
* Tout graphe donne aussi un [[matroïde]].
* En [[théorie des modèles]], un graphe est juste une [[Structure (logique mathématique)|structure logique]]. Dans ce cadre, il n'y a pas de limitation aux nombre d'arêtes qui peut être tout [[nombre cardinal]].
* En [[bio-informatique]], l'[[analyse en graphe de puissance]] introduit de graphes particuliers (les {{Citation étrangère|langue=en|power graphs}}) comme une alternative pour la représentation de graphes non orientés.
* Dans les [[Système d'information géographique|systèmes d'information géographique]], les réseaux géométriques sont des modèles proches des graphes, et empruntent à la [[théorie des graphes]] de nombreux concepts pour l'analyse spatiales sur les réseaux routiers ou des repères d'utilisation.

== Notes et références ==
{{Références}}

== Annexes ==
=== Bibliographie ===

==== Ouvrages généraux ====
Tous les manuels de mathématiques discrètes contiennent un traitement des graphes :
* {{Ouvrage|prénom1=Peter|nom1=Fletcher|prénom2=Hughes|nom2=Hoyle|prénom3=C. Wayne|nom3=Patty|titre=Foundations of Discrete Mathematics|lieu=Boston|éditeur=PWS-KENT Pub. Co.|année=1991|pages totales=781|isbn=0-534-92373-9}}
* {{Ouvrage|auteur1=Ronald L. Graham|auteur2=[[Martin Grötschel]]|auteur3=László Lovász|responsabilité3=direction|titre=Handbook of Combinatorics|éditeur=MIT Press|année=1995|isbn=0-262-07169-X|id=GGL}}
* {{Ouvrage|prénom1=Shôkichi|nom1=Iyanaga|auteur2=Yukiyosi Kawada|titre=Encyclopedic Dictionary of Mathematics|éditeur=MIT Press|année=1977|isbn=0-262-09016-3}}
* {{Ouvrage | prénom1=Gilbert | nom1=Strang | titre=Linear Algebra and Its Applications | éditeur=Brooks Cole | année=2005 | numéro d'édition=4 | pages totales=487 | isbn=0-03-010567-6 | lire en ligne=https://books.google.com/books?vid=ISBN0030105676}}.
* {{Ouvrage|langue=en|prénom1=Daniel|nom1=Zwillinger|titre=CRC Standard Mathematical Tables and Formulae|lieu=Boca Raton/London/New York etc.|éditeur=Chapman & Hall/CRC|date=2002-11-27|numéro d'édition=31|pages totales=910|isbn=1-58488-291-3}}

==== Ouvrages spécifiques ====
De nombreux livres sont centrés sur la théorie des graphes :
* {{Ouvrage |auteur1=R. Balakrishnan |auteur2=K. Ranganathan |titre=A Textbook of Graph Theory |lieu=New York |éditeur=Springer-Verlag |collection=Universitext |année=2012 |pages totales=xiii+292 |isbn=978-1-4614-4528-9 |doi=10.1007/978-1-4614-4529-6 |lire en ligne=https://books.google.com/books?id=HS9iDhAuFuUC&printsec=frontcover |consulté le=24 janvier 2018}}
* {{Ouvrage|auteur1=Claude Berge|titre=Théorie des graphes et ses applications|lieu=Paris|éditeur=Collection Universitaire de Mathématiques|année=1963|numéro d'édition=2|pages totales=viii+267|sudoc=007608756}}
* {{Ouvrage|langue=en|prénom1=Norman|nom1=Biggs|titre=Algebraic Graph Theory|lieu=Cambridge|éditeur=Cambridge University Press|année=1993|numéro d'édition=2|pages totales=205|isbn=0-521-45897-8}}
* {{Ouvrage|langue=en|prénom1=Béla|nom1=Bollobás|lien auteur1=Béla Bollobás|titre=Modern Graph Theory|lieu=New York/Berlin/Paris|éditeur=Springer|date=2002-08-12|numéro d'édition=1|pages totales=394|isbn=0-387-98488-7|id=Boll}}
* {{ouvrage|nom1=Bretto |prénom1=Alain |nom2=Faisant |prénom2=Alain |nom3= Hennecart |prénom3=François     |date=2022 |titre=Elements of Graph Theory: From Basic Concepts to Modern Developments|url=https://ems.press/books/etb/243 |éditeur=European Mathematical Society Press |isbn=978-3-98547-017-4 }}
* {{Ouvrage|auteur1=Jørgen Bang-Jensen|auteur2=Gregory Z. Gutin|titre=Digraphs|sous-titre=Theory, Algorithms and Applications|éditeur=Springer-Verlag|année=2000|isbn=|lire en ligne=http://www.cs.rhul.ac.uk/books/dbook/}}
* {{Ouvrage|auteur1=Reinhard Diestel|titre=Graph Theory|éditeur=Springer|collection=Graduate Texts in Mathematics|numéro dans collection=173|année=août 2016|numéro d'édition=5|pages totales=447|isbn=978-3-662-53621-6|isbn2=978-3-96134-005-7|présentation en ligne=http://diestel-graph-theory.com/|lire en ligne=http://diestel-graph-theory.com/basic.html|réimpression=2010, 2005, 2000, 1997 }}
* {{Ouvrage|langue=en|prénom1=Jonathan L.|nom1=Gross|auteur2=Jay Yellen|titre=Graph Theory and Its Applications|lieu=Boca Raton (Fla.)/London/New York etc.|éditeur=CRC Press|date=1998-12-30|pages totales=585|isbn=0-8493-3982-0|lire en ligne=https://books.google.com/books?id=CRDMgj-DfdEC&printsec=frontcover}}
* {{Ouvrage| prénom1=Jonathan L.| nom1=Gross| prénom2=Jay| nom2=Yellen| responsabilité2=éditeurs| titre=Handbook of graph theory| éditeur=[[CRC Press]]| année=2004| pages totales=1192| isbn=978-1-58488-090-5| lire en ligne=https://books.google.com/books?id=mKkIGIea_BkC}}.
* {{Ouvrage|prénom1=Frank|nom1=Harary|titre=Graph Theory|éditeur=Addison Wesley Publishing Company|date=January 1995|isbn=0-201-41033-8}}
* {{Ouvrage|prénom1=Richard J.|nom1=Trudeau|titre=Introduction to Graph Theory|lieu=New York|éditeur=[[Dover Publications]]|année=1993|pages totales=209|isbn=978-0-486-67870-2|présentation en ligne=http://store.doverpublications.com/0486678709.html|consulté le=8 août 2012}}

=== Articles connexes ===
{{Colonnes|taille=30|
* [[Graphe conceptuel]]
* [[Graphe dual]]
* [[Lexique de la théorie des graphes]]
* [[Graphe (type abstrait)]]
* [[Base de données orientée graphe]]
* [[Tracé de graphes]]
* [[Théorie des graphes]]
* [[Hypergraphe]]
* [[Liste de publications importantes en mathématiques#Théorie des graphes|Publications importantes en théorie des graphes]]
* [[Théorie des réseaux]]
}}

=== Liens externes ===
* {{MathWorld | nom_url=Graph | titre = Graph}}
* {{dictionnaires}}

{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Théorie des graphes]]