Leçons de niveau 16

Théorie des graphes/Propriétés

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Propriétés
Icône de la faculté
Chapitre no 2
Leçon : Théorie des graphes
Chap. préc. :Fondements
Chap. suiv. :Parcours
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des graphes : Propriétés
Théorie des graphes/Propriétés
 », n'a pu être restituée correctement ci-dessus.

Arêtes et arcs[modifier | modifier le wikicode]

Sommets et nœuds[modifier | modifier le wikicode]

Chaînes et chemins[modifier | modifier le wikicode]

Graphes[modifier | modifier le wikicode]

Généralités[modifier | modifier le wikicode]



  • Un graphe peu dense contient peu d’arêtes/arcs
  • Un graphe dense contient beaucoup d’arêtes/arcs


Connexité[modifier | modifier le wikicode]

  • Les composantes connexes d’un graphe G sont les sous-graphes maximaux connexes de G
  • Un graphe est k-connexe (1 ≤ k ≤ ) si le retrait de k-1 sommets quelconques préserve sa connexité


  • Les composantes fortement connexes d'un graphe G sont les sous-graphes maximaux fortement connexes de G
  • Le graphe réduit de G est le graphe G où chaque composantes fortement connexes a été condensée en un seul sommet