Graphe simple

Un graphe non orienté est un couple ${\displaystyle (V,E)}$ où :

• ${\displaystyle V}$ est appelé l'ensemble des sommets de ${\displaystyle G}$, et
• ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}$ est un ensemble de paires d'éléments de ${\displaystyle V}$ appelé l'ensemble des arêtes.

Un tel graphe est aussi appelé simple pour le distinguer des multigraphes, construction où il peut exister plusieurs arêtes pour une même paire de sommets. La notation E est fréquente par emprunt à l'anglais, où elle dénote l'ensemble des « edges ».

Le nombre d'arêtes issues d'un sommet est le degré de ce sommet.

Un graphe orienté est un couple ${\displaystyle (V,A)}$ où :

• ${\displaystyle V}$ est appelé l'ensemble des sommets, et
• ${\displaystyle A\subseteq \{(x,y)\mid x,y\in V\}}$ est un ensemble de couples d'éléments de ${\displaystyle V}$ appelé l'ensemble des arcs.

Un tel graphe est aussi appelé simple pour le distinguer des multigraphes, comme ci-dessus.

Le nombre d'arêtes entrant respectivement sortant d'un sommet est appelé le degré entrant respectivement le degré sortant de ce sommet.

• Théorie des graphes
• Graphe orienté
• Graphe non orienté
• Graphe (type abstrait)
• Lexique de la théorie des graphes