Théorie des graphes - Arbres
Les arbres sont des graphiques qui ne contiennent même pas un seul cycle. Ils représentent la structure hiérarchique sous une forme graphique. Les arbres appartiennent à la classe la plus simple de graphiques. Malgré leur simplicité, ils ont une structure riche.
Les arbres fournissent une gamme d'applications utiles aussi simples qu'un arbre généalogique à aussi complexes que des arbres dans les structures de données de l'informatique.
Arbre
UNE connected acyclic graphs'appelle un arbre. En d'autres termes, un graphe connecté sans cycle est appelé un arbre.
Les bords d'un arbre sont connus comme branches. Les éléments des arbres sont appelés leurs nœuds. Les nœuds sans nœuds enfants sont appelésleaf nodes.
Un arbre avec 'n' sommets a 'n-1' arêtes. S'il a une arête de plus que 'n-1', alors l'arête supplémentaire devrait évidemment être associée à deux sommets, ce qui conduit à former un cycle. Ensuite, il devient un graphe cyclique qui est une violation du graphe arborescent.
Example 1
Le graphe présenté ici est un arbre car il n'a pas de cycles et il est connecté. Il a quatre sommets et trois arêtes, c'est-à-dire pour 'n' sommets 'n-1' arêtes comme mentionné dans la définition.
Note - Chaque arbre a au moins deux sommets de degré un.
Example 2
Dans l'exemple ci-dessus, les sommets «a» et «d» ont le degré un. Et les deux autres sommets «b» et «c» ont le degré deux. Ceci est possible car pour ne pas former de cycle, il doit y avoir au moins deux arêtes simples n'importe où dans le graphique. Ce ne sont que deux arêtes avec un degré d'un.
Forêt
UNE disconnected acyclic graphs'appelle une forêt. En d'autres termes, une collection disjointe d'arbres s'appelle une forêt.
Example
Le graphique suivant ressemble à deux sous-graphiques; mais c'est un seul graphe déconnecté. Il n'y a pas de cycles dans ce graphique. Par conséquent, il s'agit clairement d'une forêt.
S'étendant sur les arbres
Soit G un graphe connexe, alors le sous-graphe H de G est appelé un arbre couvrant de G si -
- H est un arbre
- H contient tous les sommets de G.
Un arbre couvrant T d'un graphe non orienté G est un sous-graphe qui comprend tous les sommets de G.
Example
Dans l'exemple ci-dessus, G est un graphe connexe et H est un sous-graphe de G.
Clairement, le graphe H n'a pas de cycles, c'est un arbre à six arêtes qui est un de moins que le nombre total de sommets. Par conséquent, H est l'arbre couvrant de G.
Rang du circuit
Soit 'G' un graphe connexe avec 'n' sommets et 'm' arêtes. Un arbre couvrant 'T' de G contient (n-1) arêtes.
Par conséquent, le nombre d'arêtes que vous devez supprimer de 'G' pour obtenir un arbre couvrant = m- (n-1), qui est appelé le rang de circuit de G.
Cette formule est vraie, car dans un arbre couvrant, vous devez avoir des arêtes «n-1». Sur «m» arêtes, vous devez conserver «n – 1» arêtes dans le graphique.
Par conséquent, la suppression des arêtes «n – 1» de «m» donne les arêtes à supprimer du graphe afin d'obtenir un arbre couvrant, qui ne devrait pas former un cycle.
Example
Jetez un œil au graphique suivant -
Pour le graphe donné dans l'exemple ci-dessus, vous avez m = 7 arêtes et n = 5 sommets.
Alors le rang du circuit est -
Example
Soit «G» un graphe connexe avec six sommets et le degré de chaque sommet est de trois. Trouvez le rang de circuit «G».
Par la somme du théorème du degré des sommets,
Théorème de Kirchoff
Le théorème de Kirchoff est utile pour trouver le nombre d'arbres couvrant qui peuvent être formés à partir d'un graphe connexe.
Example
La matrice 'A' doit être remplie comme, s'il y a une arête entre deux sommets, alors elle doit être donnée comme '1', sinon '0'.
$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \ end {vmatrix} $$En utilisant le théorème de Kirchoff, il devrait être changé en remplaçant les valeurs diagonales principales par le degré des sommets et tous les autres éléments par -1.
$$ = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: factor \: \: of \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$Ainsi, le nombre d'arbres couvrant = 8.