Introduction à la théorie des graphes/Graphes et sous-graphes

Leçons de niveau 16
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Graphes et sous-graphes
Icône de la faculté
Chapitre no 2
Leçon : Introduction à la théorie des graphes
Chap. préc. :Définitions
Chap. suiv. :Quelques problèmes célèbres
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Introduction à la théorie des graphes : Graphes et sous-graphes
Introduction à la théorie des graphes/Graphes et sous-graphes
 », n'a pu être restituée correctement ci-dessus.

La majorité des problèmes de théorie des graphes consiste en l'étude, l’existence ou l'optimalité de certains sous-objets contenus dans un graphe. Nous allons définir ici ces sous-objets et nous en donnerons quelques exemples.

Sous-graphe et graphe partiel[modifier | modifier le wikicode]


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


En ce qui concerne un graphe partiel de G, c’est tout à fait l'inverse. Ici on garde tous les sommets de G et on enlève quelques arêtes. Voici la définition :


On parle aussi de graphe couvrant, particulièrement quand le graphe partiel est un arbre.

Un sous-graphe partiel sera un graphe partiel d'un sous-graphe.

Graphes et sous-graphes particuliers[modifier | modifier le wikicode]

Stable[modifier | modifier le wikicode]


Notons qu'un stable est donc 0-régulier.

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


Clique[modifier | modifier le wikicode]

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


Chaine et connexité[modifier | modifier le wikicode]


Dans un graphe simple, une chaîne pourra être simplement définie par une séquence de sommets.

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



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


Cycle[modifier | modifier le wikicode]


On dit aussi qu'un cycle est une chaîne fermée.

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


Image logo représentative de la faculté Faculté de Mathématiques Faites ces exercices : Graphes et sous-graphes.



Début d’un principe
Fin du principe


Forêt et arbre[modifier | modifier le wikicode]



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