Théorie des Graphes - THG - Chapitre 3 : Arbres et Arborescences - PDF

# Théorie des Graphes - THG ## CHAPITRE 3 : ARBRES ET ARBORESCENCES **Plan** 1. Nombre cyclomatique et nombre cocyclomatique 2. Arbres 3. Arborescences 4. Fonction ordinale Licence M.I Les arbres et les arborescences sont des structures fondamentales utilisées dans de très nombreux domaines: info...

# Théorie des Graphes - THG ## CHAPITRE 3 : ARBRES ET ARBORESCENCES **Plan** 1. Nombre cyclomatique et nombre cocyclomatique 2. Arbres 3. Arborescences 4. Fonction ordinale Licence M.I Les arbres et les arborescences sont des structures fondamentales utilisées dans de très nombreux domaines: informatique, science sociale, statistique, intelligence artificielle,... ## 1. NOMBRE CYCLOMATIQUE ET NOMBRE COCYCLOMATIQUE Etant donné un graphe G avec n sommets, m arcs et p composantes connexes : - La dimension de la base des cycles (cycles indépendants) est a(G) = m-n+p; a(G) est appelé le "nombre cyclomatique" du graphe. - La dimension de la base des cocycles (cocycles indépendants) est β(G) = n-p; β(G) est appelé le "nombre cocyclomatique" du graphe. Du fait que le nombre de chemins, cycles et cocycles existants dans un graphe peut être très grand, les nombres cyclomatique et cocyclomatique permettent de mesurer le nombre de cycles et cocycles indépendants dans un graphe donné. **Exemple 1:**  - n = 6, m = 7, p = 2 - a(G) = m-n+p = 3, donc il existe 3 cycles élémentaires indépendants. - β(G) = n-p = 4, donc il existe 4 cocycles élémentaires indépendants. ## 2. ARBRES ### 2.1. Définitions Un arbre est un graphe connexe sans cycle et ayant au moins deux sommets (il peut avoir des arcs ou des arêtes). **Exemple 2:**  **Exemple 3:** L'arbre généalogique d'une famille est un exemple classique d'arbre où les sommets sont les membres de la famille et les arêtes sont les liens de parenté directs. - Une forêt est un graphe non connexe et sans cycle; c'est aussi un ensemble d'arbres. - Une forêt est un graphe dont chaque composante connexe est un arbre. **Exemple 4:**  ### 2.2. Propriétés Soit H un graphe ayant n sommets (n ≥ 2), l'une des propriétés suivantes est suffisante pour définir un arbre : a. H est connexe et sans cycle. b. H est sans cycle et possède (n - 1) arêtes (ou arcs). c. H est connexe et possède (n - 1) arêtes. d. H est sans cycle et en ajoutant une arête entre deux sommets non adjacents on crée un cycle et un seul. e. H est connexe et en supprimant une arête quelconque, il n'est plus connexe. f. Tout couple de sommets est relié par une chaîne et une seule. **Démonstration** On peut démontrer que: a ⇒ b ⇒ c ⇒ d ⇒ e ⇒ f ⇒ a **Exemple 5: Démonstration de a ⇒ b** Soient p le nombre de composantes connexes, m le nombre d'arêtes et a(H) le nombre cyclomatique: Ona: a(H)=m-n+p = 0 (sans cycle) et p = 1, donc m = n-p=n-1 **Propriétés** * Un graphe connexe de n sommets, possède au moins (n - 1) arêtes (ou arcs). * Un graphe sans cycle de n sommets, possède au plus (n-1) arêtes (ou arcs). * Dans un graphe sans cycle qui a n sommets, m arêtes, p composantes connexes, on a m = n - p. * Un arbre d'ordre n (n ≥ 2) possède au moins 2 sommets pendants (Un sommet pendant x₁ est un sommet qui n'est adjacent qu'a un seul sommet). **Exemple 6:**  - Un graphe G quelconque admet un graphe partiel qui est un arbre si et seulement si G est connexe. Un tel arbre est appelé "arbre partiel". ### 2.3. Algorithme de détermination d'un arbre partiel d'un graphe connexe a. Chercher une arête (ou un arc) dont la suppression "ne déconnecte pas" le graphe. b. Si une telle arête existe, la supprimer du graphe puis reprendre en a. Sinon le graphe est un arbre partiel. La procédure s'arrête une fois qu'il n'y a plus d'arêtes à supprimer. **Exemple 7:**  ### 2.4. Algorithmes de recherche d'un arbre partiel de valeur minimale Soit un graphe G(X, U), à chaque arête (ou arc) appartenant à U, on lui associe un nombre c(u) appelé "cout" ou "valeur" ou "poids" de l'arête u; on appelle valeur totale d'un arbre partiel H(X, V) la somme: $$S(H) = \sum_{u \in V}c(u)$$ Le problème est de chercher un arbre partiel H de G tel que sa valeur totale soit minimale. Le minimum est pris sur l'ensemble des arbres possibles de G. Si toutes les arêtes ont des couts différents, l'arbre partiel minimal est unique. Ce problème a plusieurs applications. Nous citons à titre d'exemple la construction de lignes électriques. On considère un ensemble de N sites devant être reliés par des lignes à haute tension. L'objectif est de construire un réseau connectant tous les sites et ayant une longueur minimale. On peut modéliser l'ensemble des réseaux possibles par un graphe complet et valué G = (X,U,C) dans lequel X est l'ensemble des sites,U l'ensemble de toutes les connections possibles et C une application qui associe à toute arête (i, j) un coût (la distance entre i et j). La résolution de ce problème (réseau optimal) revient à trouver l'arbre partiel (recouvrant) de poids minimal. ### 2.5. Recherche d'un système fondamental de cycles indépendants d'un graphe connexe Pour obtenir un système fondamental de cycles indépendants, il suffit de construire un arbre partiel du graphe et de faire passer un cycle et un seul, par chacune des arêtes n'appartenant pas à l'arbre. **Exemple 11:**  - Les arêtes en gras forment l'arbre partiel. - Le nombre cyclomatique: a(G)=m-n+p=11-6+1=6. - Soit 6 cycles indépendants. Cette notion est très importante dans la théoric des réseaux électriques. ### 2.6. Détermination du nombre d'arbres partiels d'un graphe connexe A partir de la matrice booléenne associée au graphe, construire la matrice B telle que : $$b_{ij} = \begin{cases} \text{degré du sommet i} & \text{ si } i = j\\ -1 & \text{ si l'arc (i, j) ∈ U }\\ 0 & \text{ si l'arc(i,j) ≠ U } \end{cases}$$ Le nombre d'arbres partiels et égal au mineur de n'importe quel terme de la diagonale principale de la matrice B (Mineur = déterminant de la matrice) **Exemple 12:**  - Le déterminant (mineur (B)) = - Donc il y a 8 arbres partiels. Le nombre d'arêtes de chaque arbre partiel est n - 1 (c'est-à-dire 3 arêtes), ainsi il faut enlever de chaque combinaison deux arêtes.  ## 3. ARBORESCENCE ### 3.1. Définitions **Racine** Dans un graphe G(X, U), on appelle racine un sommet x tel que tout autre sommet du graphe peut être atteint par un chemin issu de x. **Exemple 13:**  **Graphe quasi-fortement connexe** - Un graphe G est dit quasi-fortement connexe, si pour tout couple de sommets (xi, xj), il existe un sommet y d'où partent à la fois un chemin allant en x₁ et un chemin allant en xj. - Un graphe fortement connexe est donc quasi-fortement connexe, mais la réciproque est fausse - Un graphe quasi-fortement connexe est connexe. **Arborescence** Soit G (X, I) un graphe orienté : G est une arborescence de racine x ∈ X si : a. xo est unique et n'est l'extrémité finale d'aucun arc (i. e. [¯¹(x0) = Ø). b. VXi, Xi Xo, x₁ est l'extrémité finale d'un seul arc (i. e. |Г−¹(xi)| = 1). c. G ne contient pas de circuit. Toute arborescence est un arbre muni d'une racine xo et ∀x₁ ∈ X, ∃ un chemin allant de xo à xi. **Exemple 14:**  **Remarque:** La condition nécessaire et suffisante pour qu'un graphe G(X, U) admet une racine est qu'il soit quasi-fortement connexe. ### 3.2. Propriétés Soit A un graphe d'ordre n > 1, les propriétés suivantes sont équivalents pour définir une arborescence. a. A est quasi-fortement connexe et sans cycles b. A est fortement connexe et admet (n - 1) arcs c. A est un arbre admettant une racine xo d. Il existe un sommet xo qui est relié à tout autre sommet par un chemin unique issu de xo e. A est quasi-fortement connexe et cette propriété disparait par suppression d'un arc quelconque f. A est connexe et il existe un sommet xo tel que: d (x) = 0 et d₁(x) = 1 ∀x; ≠ xo g. A est sans cycle et l'on a dx(x) = 0 et d₁ (xi) = 1 ∀xi ≠ Xo **Démonstration** On peut démontrer que : a⇒b>c>d>e>f ga **Exemple 15: Démonstration de a ⇒ b** D'après a, A est connexe et sans cycle c'est un arbre, ainsi il admet (n - 1) arcs. ## 4. FONCTION ORDINALE ### 4.1. Définition Soit G (X, I) un graphe sans circuit, on définit les sous-ensembles No, N1, N2,..., N, tels que: - No = {xi / Γ-1(xi) = 0} - N₁ = {xi / Γ-1(xi)No} - N₂ = {xi / Γ-1(x)No UN₁} - N = {xi / Γ-1(xi)∪_k=0^n-1 N_k} Avec r est le plus petit entier tel que ¹(xi) = Ø (ou Γ' (N₄) = 0Ø) Les sous-ensembles Nr forment une partition de X et sont appelés "Niveaux". La fonction ordinale (x₁) du graphe sans circuit est défini par x₁ ∈ Nk0(xi) = k ### 4.2. Méthode de détermination de la fonction ordinale d'un graphe sans cycle a. Représenter la matrice booléenne du graphe; poser k = 0 b. Ajouter une ligne totale Ak en bas de la matrice et y mettre des croix dans les cases des colonnes dont les lignes correspondantes ont été supprimées. c. Faire la somme par colonne et reporter le total dans la case correspondante de Ak. d. Les sommets ayant leur total nul constituent le niveau Nk, supprimer alors les lignes portant ces sommets. e. Incrémenter k (k = k + 1) et aller à b. f. S'arrêter une fois que la ligne Ak contient seulement des croix. **Exemple 16:**  **Exemple 17: (Contre-Exemple: Graphe avec cycle)**  **Remarque:** - On peut définir la fonction ordinale inverse de la même façon qu'on a défini la fonction ordinale: seulement tout ce qui a été fait pour les lignes, sera fait pour les colonnes et inversement. - Une arborescence a toujours une fonction ordinale. **Exemple 18:** Définir une fonction ordinale (en donnant à la racine le niveau No) pour l'arborescence suivante :  - No = {2}, N₁ = {1,12}, N₂ = {3,4,5}, N₃ = {6,7,8}, N₁ = {9,10,11}