Leçons de niveau 16

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

Une page de Wikiversité.
Sauter à la navigation Sauter à 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é 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]