Histoire des mathématiques Discipline

théorie des graphes

Discipline

branche des mathématiques et de l'informatique étudiant les graphes

domaine
Combinatoire · informatique · mathématiques discrètes · Mathématiques

Pour comprendre

rédaction

La théorie des graphes est une branche des mathématiques et de l'informatique qui étudie les graphes. Un graphe organise des sommets et des arêtes : les sommets représentent les éléments considérés, et les arêtes les liens entre eux. Cette discipline étudie donc la structure créée par ces liens, ainsi que les propriétés qui en découlent.

Ce qu'elle étudie

Elle examine les graphes à partir de leurs sommets, de leurs arêtes et de la façon dont ces éléments sont reliés. Le degré d'un sommet compte les arêtes qui y aboutissent. En additionnant les degrés de tous les sommets, chaque arête intervient à ses deux extrémités. La théorie des graphes permet ainsi de décrire et d'analyser des relations discrètes sans les confondre avec les objets eux-mêmes.

$$\sum_{v} \deg(v) = 2\,|E|$$

Cette égalité indique que la somme des degrés des sommets vaut deux fois le nombre d'arêtes, car chaque arête est comptée à ses deux bouts.

À quoi elle sert

Elle sert à représenter et étudier des relations entre éléments, notamment pour :

  • distinguer les éléments des liens qui les relient ;
  • observer comment les arêtes se répartissent entre les sommets ;
  • raisonner sur la structure d'un graphe ;
  • étudier les graphes extrémaux, qui forment une de ses branches.

Où elle se place

Elle appartient aux mathématiques, à la combinatoire, aux mathématiques discrètes et à l'informatique. La théorie des graphes extrémaux est l'une de ses branches.

flowchart TD
  P0[Mathématiques] --> D([théorie des graphes])
  D --> E0[Théorie des graphes extrémaux]

Les ponts de Königsberg

Cette figure schématise les sept ponts de Königsberg reliant quatre rives. Euler montre en 1736 qu'aucune promenade ne peut les traverser tous une seule fois : chaque rive touche un nombre impair de ponts. En réduisant la ville à des points et des liaisons, il fonde la théorie des graphes.

{ "boundingBox": [ 0, 4.2, 4.4, -0.2 ], "axis": false, "segments": [ { "from": [ 1.92, 3.48 ], "to": [ 1.12, 2.08 ], "color": "#dc2626", "width": 2 }, { "from": [ 2.08, 3.32 ], "to": [ 1.28, 1.92 ], "color": "#dc2626", "width": 2 }, { "from": [ 1.92, 0.52 ], "to": [ 1.12, 1.92 ], "color": "#dc2626", "width": 2 }, { "from": [ 2.08, 0.68 ], "to": [ 1.28, 2.08 ], "color": "#dc2626", "width": 2 }, { "from": [ 2, 3.4 ], "to": [ 3.2, 2 ], "color": "#dc2626", "width": 2 }, { "from": [ 2, 0.6 ], "to": [ 3.2, 2 ], "color": "#dc2626", "width": 2 }, { "from": [ 1.2, 2 ], "to": [ 3.2, 2 ], "color": "#dc2626", "width": 2 } ], "points": [ { "x": 2, "y": 3.4, "name": "N", "color": "#1e3a8a", "size": 3, "fixed": true }, { "x": 2, "y": 0.6, "name": "S", "color": "#1e3a8a", "size": 3, "fixed": true }, { "x": 1.2, "y": 2, "name": "I", "color": "#1e3a8a", "size": 3, "fixed": true }, { "x": 3.2, "y": 2, "name": "E", "color": "#1e3a8a", "size": 3, "fixed": true } ], "labels": [ { "x": 0.4, "y": 3.8, "text": "7 ponts, 4 rives", "color": "#1e3a8a" } ] }

Liens

a compté parmi ses contributeurs
a été découvert par
comprend
a pour branche

Sources