Théorie des graphes/Propriétés

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
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

Sommets et nœuds modifier

Chaînes et chemins modifier

Graphes modifier

Généralités modifier



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


Connexité modifier

  • 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