Un sous-graphe couvrant est un sous-graphe qui contient tous les sommets du graphe d'origine. Un arbre couvrant est un sous-graphe couvrant qui est souvent intéressant. Un cycle dans un graphe qui contient tous les sommets du graphe serait appelé un cycle couvrant.
Combien y a-t-il de sous-graphes couvrant ?
Il y a 2n sous-graphes induits (tous les sous-ensembles de sommets) et 2m sous-graphes couvrant (tous les sous-ensembles d'arêtes).
Comment trouver un sous-graphe couvrant ?
Et par définition, le sous-graphe Spanning d'un graphe G est un sous-graphe obtenu par suppression d'arête uniquement. Si nous créons des sous-ensembles d'arêtes en supprimant une arête, deux arêtes, trois arêtes, etc. Comme il y a m arêtes, il y a donc 2^m sous-ensembles. Donc G a 2^m sous-graphes couvrants.
Qu'entend-on par arbre couvrant ?
L'arbre couvrant d'un graphe (G) est un sous-ensemble de G qui couvre tous ses sommets en utilisant le nombre minimum d'arêtes. Certaines propriétés d'un arbre couvrant peuvent être déduites de cette définition: Comme "un arbre couvrant couvre tous les sommets", il ne peut pas être déconnecté.
Qu'est-ce que la théorie des graphes couvrants ?
Un arbre couvrant est un sous-ensemble du graphe G, qui a tous les sommets couverts avec le nombre minimum possible d'arêtes. Par conséquent, un arbre couvrant n'a pas de cycles et il ne peut pas être déconnecté. Par cette définition, nous pouvons tirer la conclusion que chaque graphe G connecté et non orienté a au moins un arbre couvrant.
