Introduction à la théorie des graphes/Définitions

Il est nécessaire, pour étudier la théorie des graphes, de se munir d'un crayon et d'un brouillon. En effet, pour comprendre la majorité des concepts, il sera plus qu'utile de faire un dessin.

Graphe

Un graphe est un objet mathématique particulier, nous devons donc commencer par le définir avant d’en étudier la théorie :

Pour simplifier, nous noterons V et E les ensembles V(G) et E(G).

Pour mieux comprendre cette définition, voici un exemple :

Arêtes adjacentes, sommets voisins, arête incidente à un sommet

Voilà trois termes à ne pas confondre, voici leur définition :

Degré d'un sommet

Par convention, une boucle, touchant deux fois le sommet, sera comptée comme deux arêtes incidentes.

Cette définition nous permet maintenant d'introduire notre premier théorème :

Il existe d'autres démonstrations pour ce théorème qui sont sans doute plus formelles. Cependant, nous n'avons pas encore les outils pour les étudier.

Quelques graphes particuliers

Graphe régulier

• 
  graphe 0-régulier
• 
  graphe 1-régulier
• 
  graphe 2-régulier
• 
  Modèle:W 3-régulier

Graphe complet

• 
  $K_1$
• 
  $K_2$
• 
  $K_3$
• 
  $K_4$