Découvrez la matrice de coupure fondamentale en théorie des graphes : définition, construction étape par étape, règles d'orientation, et exemples avec solutions.
Lorsqu'on parle de matrice des coupes dans la théorie des graphes, on parle généralement de matrice fondamentale des coupes. Un ensemble de coupes est un ensemble minimal de branches d'un graphe connexe tel que, lorsqu'on les retire du graphe, celui-ci se sépare en deux parties distinctes appelées sous-graphes et la matrice des coupes est la matrice obtenue en prenant une coupe à la fois par ligne. La matrice des coupes est notée par le symbole [Qf].

Deux sous-graphes sont obtenus à partir d'un graphe en sélectionnant des ensembles de coupes composés de branches [1, 2, 5, 6].
Ainsi, en d'autres termes, nous pouvons dire que l'ensemble de coupes fondamental d'un graphe donné par rapport à un arbre est un ensemble de coupes formé avec une branche de l'arbre et les liens restants. Les branches de l'arbre sont les twigs et les liens sont les branches du co-arbre.
Ainsi, le nombre d'ensembles de coupes est égal au nombre de twigs.
[Nombre de twigs = N – 1]
Où, N est le nombre de nœuds du graphe ou de l'arbre dessiné.
L'orientation de l'ensemble de coupes est la même que celle de la branche de l'arbre et est considérée comme positive.
Il y a quelques étapes à suivre pour tracer la matrice des coupes. Ces étapes sont les suivantes-
Tracez le graphe du réseau ou du circuit donné (si fourni).
Ensuite, tracez son arbre. Les branches de l'arbre seront les twigs.
Ensuite, tracez les branches restantes du graphe en lignes pointillées. Ces branches seront les liens.
Chaque branche ou twig de l'arbre formera un ensemble de coupes indépendant.
Écrivez la matrice avec les lignes comme ensembles de coupes et les colonnes comme branches.
| Branches ⇒ | 1 | 2 | 3 | . | . | b | |
| Ensembles de coupes | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = nombre d'ensembles de coupes.
b = nombre de branches.
Qij = 1 ; si la branche J est dans l'ensemble de coupes avec une orientation identique à celle de la branche de l'arbre.
Qij = -1 ; si la branche J est dans l'ensemble de coupes avec une orientation opposée à celle de la branche de l'arbre.
Qij = 0 ; si la branche J n'est pas dans l'ensemble de coupes.
Exemple 1
Tracez la matrice des coupes pour le graphe suivant.
Réponse :
Étape 1 : Tracez l'arbre pour le graphe suivant.
Étape 2 : Identifiez maintenant l'ensemble de coupes. L'ensemble de coupes sera le nœud qui contient une seule branche de l'arbre et un nombre quelconque de liens.
Ici, C2, C3 et C4 sont des ensembles de coupes.
Étape 3 : Tracez maintenant la matrice.
| Branches ⇒ | 1 | 2 | 3 | 4 | 5 | 6 | |
| Ensembles de coupes | |||||||
| C2 | +1 | ||||||