Leçons de niveau 16

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

Une page de Wikiversité, la communauté pédagogique libre.
Aller à la navigation Aller à la recherche
Début de la boite de navigation du chapitre
Définitions
Icône de la faculté
Chapitre no 1
Leçon : Introduction à la théorie des graphes
Retour auSommaire
Chap. suiv. :Graphes et sous-graphes
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Introduction à la théorie des graphes : Définitions
Introduction à la théorie des graphes/Définitions
 », n'a pu être restituée correctement ci-dessus.

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[modifier | modifier le wikicode]

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 :

Début de l'exemple
Fin de l'exemple


Arêtes adjacentes, sommets voisins, arête incidente à un sommet[modifier | modifier le wikicode]

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




Début de l'exemple
Fin de l'exemple


Graphe simple[modifier | modifier le wikicode]




Début de l'exemple
Fin de l'exemple


Degré d'un sommet[modifier | modifier le wikicode]


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 :

Début d’un théorème
Fin du théorème


Début d'une démonstration
Fin de la démonstration

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.

Début d’un théorème
Fin du théorème


Début d'une démonstration
Fin de la démonstration

Quelques graphes particuliers[modifier | modifier le wikicode]

Graphe régulier[modifier | modifier le wikicode]


Graphe complet[modifier | modifier le wikicode]