Théorie des graphes

Page d'aide sur l'homonymie Pour la notion mathématique utilisée en théorie des ensembles, voir Graphe d'une fonction.
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
L'introduction de cet article est soit absente, soit non conforme aux conventions de Wikipédia (30 novembre 2016).

Ces motifs sont peut-être précisés sur la page de discussion. — Découvrez comment faire pour en améliorer la rédaction.

La théorie des graphes est une théorie informatique et mathématique.

Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau ( réseau social, réseau informatique, télécommunications, etc.) et dans bien d'autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général. De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la conjecture d'Hadwiger, en font une branche vivace des mathématiques discrètes.

Définition de graphe et vocabulaire

Article détaillé : Lexique de la théorie des graphes.
Exemple de graphe orienté.
Exemple de graphe non orienté.

Un graphe est un ensemble de points nommés nœuds (parfois sommets ou cellules) reliés par des traits (segments) ou flèches nommées arêtes (ou liens ou arcs). L'ensemble des arêtes entre nœuds forme une figure similaire à un réseau. Différents types de réseaux sont étudiés suivant leur genre de forme (ou topologie) et propriétés ; les arbres sont une sous-catégorie plus simple de graphes particulièrement importante et qui est très étudiée, notamment en informatique.

Les arêtes peuvent être orientées (flèches) ou non orientées (traits). Si les arêtes sont orientées, la relation va dans un seul sens et est donc asymétrique, et le graphe lui-même est dit orienté. Sinon, si les arêtes sont non orientées, la relation va dans les deux sens et est symétrique, et le graphe est dit non orienté.

En mathématiques, l' ensemble des nœuds est le plus souvent noté (vertices en anglais), tandis que désigne l'ensemble des arêtes (edges en anglais). Dans le cas général, un graphe peut avoir des arêtes multiples  (en), c'est-à-dire que plusieurs arêtes différentes relient la même paire de points. De plus, une arête peut être une boucle, c'est-à-dire ne relier qu'un point à lui-même. Un graphe est simple s'il n'a ni arêtes multiples ni boucles, il peut alors être défini simplement par un couple , où est un ensemble de paires d'éléments de . Dans le cas d'un graphe simple orienté, est un ensemble de couples d'éléments de . Notons qu'un graphe sans arête multiple peut être représenté par une relation binaire, qui est symétrique si le graphe est non orienté.

Pour définir un graphe général, il faut une fonction (gamma) qui associe à chaque arête une paire de sommets. Ainsi, un graphe est un triplet avec . Toutefois l'usage veut que l'on note simplement , sachant que ce n'est parfaitement rigoureux que pour les graphes simples.

Typologies des graphes

On peut définir 3 grandes familles de graphes et 5 catégories au total

  • Structurés : il est alors possible de définir quatre identités topologiques remarquables :
    • Homogènes (1) : les sommets et les arrêtes reproduisent un schéma régulier. Le schéma le plus commun est une architecture de type matriciel aussi appelé "en filet de poisson" (mesh).
    • Topologie typique d'un réseau multipolaire.
      Hiérarchiques (2) : structure typique des graphes où les sommets s'arrangent en couches hiérarchisées et pyramidales
    • Cycliques (3) : on peut identifier des cycles dans le graphe. L'exemple le plus parlant est le graphe circulaire.
    • Centralisés/Polaires (4) : C'est une architecture ou tous les sommets sont rattachés à un seul sommet, le pôle.
  • Quelconques (5) : aucune propriété topologique ne semble émerger.
  • Multipolaires : C'est une architecture mixte entre les graphes centralisés et décentralisés. Les réseaux multipolaires sont très étudiés en raison de leur proximité avec de nombreux cas concrets et notamment Internet ou les réseaux de neurones. Les graphes multipolaires sont caractérisés par deux types d'arêtes, celles qui forment les liens émanant du pôle, les liens forts ; et les liens réunissant deux pôles entre eux : les liens faibles. Les pôles peuvent par ailleurs prendre une architecture structurée (souvent centralisée) ou quelconque.
Principales topologies typiques de graphes.
Other Languages
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk bokmål: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论