Théorie des graphes/Propriétés

Graphes

Généralités

Modèle:Propriété

Modèle:Propriété

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

Connexité

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

Modèle:Propriété

• 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