Scheda di revisione: Fondamentaux des graphes et connexité

📋 Plan du Cours

1. Théorie des graphes
2. Graphes orientés et non orientés
3. Représentations graphiques et matricielles
4. Propriétés des graphes
5. Connexité et composantes
6. Parcours en largeur et profondeur
7. Recherche de composantes fortement connexes
8. Plus courts chemins
9. Algorithme de Kosaraju
10. Algorithme de Bellman-Ford et Floyd-Warshall

📖 1. Théorie des graphes

🔑 Notions clés & Définitions

• Graphe : Représentation mathématique composée d’un ensemble de sommets (nœuds) et d’un ensemble d’arcs ou arêtes reliant ces sommets.
  Exemple : Un réseau de transport.

• Graphe orienté : Graphe où chaque arc possède une direction, représenté par une flèche.
  Notations : $G=(X,U)$ avec $U \subseteq X \times X$.

• Degré d’un sommet : Nombre d’arêtes ou arcs incident à ce sommet.

  • Dans un graphe orienté :
    • Degré entrant ($d^-$) : nombre d’arcs arrivant au sommet.
    • Degré sortant ($d^+$) : nombre d’arcs partant du sommet.
  • Dans un graphe non orienté :
    • Degré ($d$) : nombre d’arêtes incidentes.

• Connexité : Propriété d’un graphe non orienté où chaque paire de sommets est reliée par une chaîne.

  • Composante connexe : Sous-ensemble maximal de sommets reliés entre eux.

• Forte connexité : Propriété d’un graphe orienté où chaque sommet est accessible depuis tout autre sommet par un chemin.

  • Composante fortement connexe : Sous-ensemble maximal de sommets où chaque sommet est accessible depuis tout autre.

• Chemin / Circuit :

  • Chemin : Séquence d’arcs ou arêtes reliant une série de sommets sans répétition.
  • Circuit : Chemin dont l’extrémité initiale et finale coïncident.

📝 Points essentiels

• La représentation d’un graphe peut être graphique, matricielle (matrice d’incidence, d’adjacence) ou listée.
• La matrice d’incidence sommets-arcs ou sommets-arêtes permet de décrire la structure du graphe de façon numérique.
• La matrice d’adjacence indique le nombre d’arcs ou arêtes entre chaque paire de sommets, étant symétrique dans le cas non orienté.
• La notion de composante (connexe ou fortement connexe) permet de décomposer un graphe en sous-graphes maximaux reliés.

💡 À retenir

La théorie des graphes modélise et analyse la connectivité et la structure des réseaux, en utilisant des concepts clés comme les degrés, la connexité, et différentes représentations matricielles pour résoudre des problèmes complexes.

📖 2. Graphes orientés et non orientés

🔑 Notions clés & Définitions

• Graphe : Représentation mathématique composée de sommets (ou nœuds) et de liens (arcs ou arêtes) entre eux.
• Graphe orienté (digraphe) : Graphe où chaque lien (arc) possède une direction, représenté par une flèche. Noté G=(X,U) avec U⊆X×X.
• Graphe non orienté : Graphe où les liens (arêtes) n'ont pas de direction spécifique, symétriques. Noté G=(X,U) avec U⊆X×X, où chaque arête relie deux sommets sans orientation.
• Degré d’un sommet : Nombre d’arêtes incidentes à ce sommet.
  • Dans un graphe orienté :
    • Degré entrant (d−i) : Nombre d’arcs arrivant au sommet i.
    • Degré sortant (d+i) : Nombre d’arcs partant du sommet i.
    • Degré total (di) : somme de degré entrant et sortant.
  • Dans un graphe non orienté :
    • Degré : Nombre d’arêtes incidentes.
• Successeur / Prédécesseur :
  • Dans un graphe orienté :
    • Successeur : Sommet j tel qu’il existe un arc (i,j).
    • Prédécesseur : Sommet j tel qu’il existe un arc (j,i).
• Voisin : Sommet adjacent à un sommet donné dans un graphe non orienté ou un sommet accessible via un arc dans un graphe orienté.
• Adjacence : Deux sommets ou arêtes liés directement par un lien.
• Boucle : Arc ou arête qui relie un sommet à lui-même.
• Matrice d’incidence : Matrice représentant la relation entre sommets et arcs ou arêtes, avec coefficients +1, -1 (orienté) ou 1 (non orienté).
• Matrice d’adjacence : Matrice carrée où chaque élément indique le nombre d’arcs ou arêtes entre deux sommets.
  • Dans un graphe orienté : aij = nombre d’arcs de i vers j.
  • Dans un graphe non orienté : aij = nombre d’arêtes entre i et j.
• Graphe simple : Graphe sans boucle ni arête multiple entre deux sommets.
• Sous-graphe : Graphe formé à partir d’un sous-ensemble de sommets et des liens entre eux dans le graphe initial.
• Graphe complet : Graphe où chaque paire de sommets est reliée par au moins une arête ou un arc.
• Clique : Sous-ensemble de sommets où chaque paire est reliée par une arête.
• Stable (ou indépendant) : Sous-ensemble de sommets sans arête entre eux.
• Connexité (non orienté) : Tout sommet est accessible depuis tout autre par une chaîne.
• Forte connexité (orienté) : Tout sommet est accessible depuis tout autre par un chemin dans les deux sens.
• Chaîne / Chemin : Séquence de liens successifs reliant deux sommets.
• Cycle / Circuit : Chemin dont l’extrémité initiale et finale coïncident.
• Chemin élémentaire / simple : Chemin sans répétition de sommet ou d’arête.
• Composante connexe / fortement connexe : Sous-ensemble maximal de sommets entre lesquels il existe une chaîne ou un chemin dans le graphe.

📝 Points essentiels

• La distinction entre graphe orienté et non orienté influence la définition des notions de degré, successeur, voisin, et connexité.
• La matrice d’incidence et la matrice d’adjacence sont des outils fondamentaux pour représenter et analyser les graphes.
• La connexité (non orienté) et la forte connexité (orienté) permettent de caractériser la structure globale du graphe.
• Les parcours en largeur (BFS) et en profondeur (DFS) sont des algorithmes clés pour explorer un graphe, identifier ses composantes, chemins, cycles, etc.
• La propriété de graphe simple garantit l’absence de boucle et d’arêtes multiples, simplifiant l’analyse.

💡 À retenir

Les graphes orientés et non orientés diffèrent principalement par la direction des liens, ce qui impacte leurs propriétés de connexité, de degré et de parcours. La maîtrise des représentations matricielles et des algorithmes de parcours est essentielle pour analyser efficacement leur structure.

📖 3. Représentations graphiques et matricielles

🔑 Notions clés & Définitions

• Graphe : Représentation d’un système composé de nœuds (sommets) reliés par des liens (arcs ou arêtes). Peut être orienté (liens avec direction) ou non orienté.
• Graphe orienté (digraphe) : Graphe où chaque lien (arc) a une direction, représenté par une flèche. Défini par deux ensembles : sommets $X$ et arcs $U \subseteq X \times X$.
• Graphe non orienté : Graphe où les liens (arêtes) n’ont pas de direction. Représenté par une paire de sommets reliés par une ligne.
• Matrice d’incidence : Matrice décrivant la relation entre sommets et arcs ou arêtes. Pour un graphe orienté, coefficients +1 et -1 indiquent la direction de l’arc. Pour un graphe non orienté, coefficients 0 ou 1 indiquent la présence d’une arête.
• Matrice d’adjacence : Matrice carrée où chaque élément $a_{ij}$ indique le nombre d’arcs ou arêtes entre les sommets $i$ et $j$. Symétrique pour un graphe non orienté, et généralement asymétrique pour un orienté.
• Degré d’un sommet : Nombre d’arcs ou arêtes incident à ce sommet. Dans un graphe orienté, distingué en degré entrant $d^-_i$ et degré sortant $d^+_i$.

📝 Points essentiels

• La représentation graphique d’un graphe utilise des points pour les sommets et des flèches ou lignes pour les liens.
• La matrice d’incidence relie sommets et arcs/arêtes : colonne = arc/arête, ligne = sommet.
• La matrice d’incidence sommets-arcs est à coefficients +1 et -1 pour un graphe orienté, et à coefficients 0 ou 1 pour un non orienté.
• La matrice d’adjacence est une représentation compacte, utile pour analyser la connectivité et les chemins.
• La notion de degré permet d’évaluer la connectivité locale d’un sommet, en tenant compte des liens entrants et sortants dans le cas orienté.

💡 À retenir

Les représentations graphiques et matricielles offrent des outils complémentaires pour modéliser et analyser la structure d’un graphe, facilitant la résolution de problèmes liés à la connectivité, aux chemins ou aux cycles.

📖 4. Propriétés des graphes

🔑 Notions clés & Définitions

• Graphe : Représentation mathématique composée d’un ensemble de sommets (ou nœuds) et d’un ensemble d’arcs ou arêtes reliant ces sommets. Peut être orienté ou non orienté.

• Graphe orienté (digraphe) : Graphe où chaque arc a une direction, représenté par une paire ordonnée (i,j). Notation : $G=(X,U)$ avec $U \subseteq X \times X$.

• Degré d’un sommet : Nombre d’arêtes ou arcs incident à ce sommet.

  • Degré entrant ($d^-_i$) : Nombre d’arcs arrivant au sommet $i$.
  • Degré sortant ($d^+_i$) : Nombre d’arcs partant du sommet $i$.
  • Degré total ($d_i$) : Somme de $d^-_i$ et $d^+_i$.

• Graphe simple : Graphe sans boucle (arc ou arête reliant un sommet à lui-même) ni arêtes multiples entre deux sommets.

• Sous-graphe : Graphe constitué d’un sous-ensemble de sommets et d’arcs/arêtes du graphe initial, engendré par un sous-ensemble $A \subseteq X$.

• Graphe complet : Graphe où chaque paire de sommets est reliée par une arête ou un arc dans un sens ou dans l’autre.

• Clique : Sous-ensemble de sommets où chaque paire est reliée par une arête (sous-graphe complet).

• Stable (ou indépendant) : Sous-ensemble de sommets sans arêtes ou liens entre eux.

• Connexité (non orienté) : Deux sommets sont liés si une chaîne (séquence d’arêtes) relie ces deux sommets. Le graphe est connexe si tous les sommets sont dans la même composante.

• Forte connexité (orienté) : Deux sommets $i$ et $j$ sont fortement connexes si un chemin existe de $i$ à $j$ et vice versa. Le graphe est fortement connexe si tous les sommets forment une seule composante fortement connexe.

📝 Points essentiels

• La notion de degré permet de caractériser la connectivité locale d’un sommet, en distinguant entre entrée et sortie dans un graphe orienté.
• La connexité dans un graphe non orienté repose sur l’existence de chaînes reliant tous les sommets.
• La forte connexité dans un graphe orienté exige la réciprocité des chemins entre chaque paire de sommets.
• La représentation matricielle (incidence, adjacency) permet de décrire efficacement la structure d’un graphe et d’analyser ses propriétés.

💡 À retenir

Les propriétés d’un graphe, telles que la connexité, la forte connexité, ou la présence de cliques, sont fondamentales pour comprendre la structure et le comportement des réseaux, et elles se caractérisent à la fois par des notions locales (degré) et globales (composantes).

📖 5. Connexité et composantes

🔑 Notions clés & Définitions

• Graphe : Ensemble de sommets (ou nœuds) reliés par des arcs (ou arêtes), orientés ou non.
• Connexité (non orienté) : Propriété d’un graphe où chaque paire de sommets est reliée par une chaîne.
• Forte connexité (orienté) : Propriété d’un graphe où, pour chaque paire de sommets (i, j), il existe un chemin de i à j et de j’à i.
• Composante connexe : Sous-graphe maximal dans lequel tous les sommets sont reliés par une chaîne.
• Composante fortement connexe : Sous-graphe maximal dans un graphe orienté où chaque sommet est accessible depuis tout autre dans cette composante.
• Chaîne / Chemin : Séquence d’arêtes reliant deux sommets, sans répéter de sommet ou d’arête selon la définition.
• Cycle / Circuit : Chemin dont les extrémités coïncident, sans répéter de sommet sauf le départ/arrivée.

📝 Points essentiels

• La connexité dans un graphe non orienté se vérifie si chaque paire de sommets est reliée par une chaîne.
• La forte connexité dans un graphe orienté exige une double accessibilité : de i à j et de j à i.
• La décomposition d’un graphe en composantes permet d’étudier ses sous-ensembles maximaux connexes ou fortement connexes.
• La relation de connexité est une relation d’équivalence : réflexive, symétrique, transitive.
• La recherche de composantes (connexes ou fortement connexes) est fondamentale pour analyser la structure d’un réseau.

💡 À retenir

La connexité d’un graphe indique qu’il existe un chemin entre chaque paire de sommets, tandis que la forte connexité impose cette propriété dans les deux sens pour les graphes orientés, permettant d’identifier des sous-ensembles fortement liés.

📖 6. Parcours en largeur et profondeur

🔑 Notions clés & Définitions

• Parcours en largeur (Breadth-First Search - BFS) : méthode d'exploration d’un graphe consistant à visiter tous les sommets à une distance k du sommet initial avant de passer à la distance k+1. Il construit des couches successives de sommets.

• Parcours en profondeur (Depth-First Search - DFS) : méthode d'exploration qui consiste à explorer aussi profondément que possible un chemin avant de revenir en arrière pour explorer d’autres chemins. Il construit une arborescence ou un arbre de parcours.

• Couche (niveau) : ensemble de sommets à une distance fixe k du sommet de départ dans un parcours en largeur, notée Ck.

• Arborescence (ou arbre de parcours) : structure en forme d’arbre représentant le chemin suivi lors d’un parcours en profondeur, avec racine le sommet initial.

• Sommet traité / Visité : sommet déjà exploré lors du parcours, évitant les visites répétées.

• Chemin : suite de sommets reliés par des arêtes ou arcs, permettant de relier deux sommets dans un graphe.

📝 Points essentiels

• Le parcours en largeur utilise une file d’attente pour explorer tous les voisins d’un sommet avant de passer aux suivants, permettant de déterminer la distance minimale entre le sommet initial et tous les autres.

• Le parcours en profondeur utilise une pile ou une récursion pour explorer autant que possible un chemin avant de revenir en arrière, utile pour détecter des cycles ou composants fortement connexes.

• La construction de couches en BFS permet de déterminer la distance la plus courte dans un graphe non pondéré.

• La différence fondamentale réside dans l’ordre d’exploration : BFS explore par niveaux, DFS explore en profondeur.

• Ces parcours servent de base pour de nombreux algorithmes, comme la recherche de composants connexes, la détection de cycles, ou la topological sorting.

💡 À retenir

Les parcours en largeur et en profondeur sont deux méthodes fondamentales pour explorer un graphe, chacune adaptée à des problématiques spécifiques : BFS pour la distance minimale et DFS pour la structure et la détection de cycles ou composants.

📖 7. Recherche de composantes fortement connexes

🔑 Notions clés & Définitions

• Composante fortement connexe : Sous-ensemble maximal de sommets dans un graphe orienté tel que, pour chaque paire de sommets (i, j), il existe un chemin de i à j et un chemin de j à i.
• Chemin : Sequence d’arcs où chaque arc relie deux sommets consécutifs, dans le même sens pour un graphe orienté.
• Circuit : Chemin dont l’extrémité initiale et l’extrémité terminale sont identiques, formant une boucle.
• Forte connexité : Propriété d’un graphe orienté où tous ses sommets appartiennent à une seule composante fortement connexe.
• Algorithme de recherche : Méthode permettant d’identifier et de partitionner le graphe en ses composantes fortement connexes, souvent via parcours en profondeur ou en largeur.
• Partition : Division de l’ensemble des sommets en sous-ensembles disjoints, appelés composantes fortement connexes, couvrant tout le graphe.

📝 Points essentiels

• La forte connexité concerne la réciprocité des chemins entre tous les sommets d’un sous-ensemble dans un graphe orienté.
• La détection des composantes fortement connexes se réalise généralement par des algorithmes de parcours en profondeur (DFS), en utilisant des notions comme les temps de découverte et de fin.
• Un graphe est fortement connexe s’il n’a qu’une seule composante fortement connexe, c’est-à-dire que chaque sommet est accessible depuis n’importe quel autre.
• La partition en composantes fortement connexes est une étape clé pour analyser la structure d’un graphe orienté, notamment dans la résolution de problèmes liés à la dépendance ou à la circulation.
• La recherche de ces composantes permet d’identifier des sous-graphes indépendants ou des cycles maximaux, essentiels pour la compréhension de la dynamique du réseau.

💡 À retenir

La détection des composantes fortement connexes permet de décomposer un graphe orienté en sous-ensembles où chaque sommet est accessible dans les deux sens, facilitant ainsi l’analyse de la structure et des cycles du réseau.

📖 8. Plus courts chemins

🔑 Notions clés & Définitions

• Plus court chemin : Chemin entre deux sommets d’un graphe dont la somme des poids (ou le nombre d’arêtes dans le cas non pondéré) est minimale.
• Graphe pondéré : Graphe où chaque arc ou arête possède un poids ou une longueur associée.
• Algorithme de Dijkstra : Méthode permettant de trouver le plus court chemin à partir d’un sommet source vers tous les autres dans un graphe pondéré sans boucle de poids négatif.
• Algorithme de Bellman-Ford : Méthode permettant de déterminer le plus court chemin même avec des poids négatifs, en détectant d’éventuelles boucles de poids négatif.
• Chemin simple : Chemin sans répétition de sommet ou d’arête.
• Distance : Longueur ou coût d’un plus court chemin entre deux sommets.

📝 Points essentiels

• La recherche du plus court chemin est fondamentale en optimisation, logistique, réseau, etc.
• Les algorithmes principaux sont Dijkstra (pour poids positifs) et Bellman-Ford (pour poids négatifs).
• La complexité de Dijkstra dépend de la structure du graphe (avec ou sans priorité).
• La représentation matricielle (matrice d’adjacence ou d’incidence) facilite la mise en œuvre des algorithmes.
• La notion de distance minimale permet de modéliser des problèmes de transport, de communication ou de planification.
• La propriété clé : un plus court chemin est un chemin dont la longueur totale est inférieure ou égale à celle de tout autre chemin entre les mêmes sommets.

💡 À retenir

Les plus courts chemins permettent d’optimiser la traversée d’un graphe en minimisant la longueur ou le coût, et sont résolus efficacement par des algorithmes spécifiques comme Dijkstra ou Bellman-Ford selon la nature des poids.

📖 9. Algorithme de Kosaraju

🔑 Notions clés & Définitions

Sommets (ou nœuds)
Les éléments de l'ensemble X d'un graphe, représentés par des points ou cercles. Dans un graphe orienté, chaque sommet peut avoir des arcs entrants et sortants.

Arc (ou arête)
Lien entre deux sommets. Dans un graphe orienté, un arc u=(i,j) va du sommet i (extrémité initiale) au sommet j (extrémité terminale). Dans un graphe non orienté, l'arête relie simplement deux sommets.

Componentes fortement connexes
Sous-ensembles maximaux de sommets dans un graphe orienté où chaque sommet est accessible depuis tout autre sommet du même sous-ensemble via un chemin orienté.

Parcours en profondeur (DFS)
Méthode d'exploration d'un graphe consistant à explorer autant que possible le long de chaque branche avant de revenir en arrière, utilisée pour découvrir les composantes fortement connexes.

Transposition d'un graphe
Graphe obtenu en inversant la direction de tous les arcs d'un graphe orienté. Si u=(i,j) est un arc dans G, alors dans la transposée, u'=(j,i).

Algorithme de Kosaraju
Procédé en deux étapes pour identifier les composantes fortement connexes d’un graphe orienté :

1. Parcours en profondeur pour déterminer l’ordre de fin des sommets.
2. Parcours en profondeur sur la transposée du graphe, en suivant cet ordre, pour extraire chaque composante fortement connexe.

Point à retenir

L'algorithme de Kosaraju exploite la propriété que les composantes fortement connexes peuvent être identifiées en utilisant la transposition du graphe et un parcours en profondeur basé sur l'ordre de fin des sommets.

📖 10. Algorithme de Bellman-Ford et Floyd-Warshall

🔑 Notions clés & Définitions

• Algorithme de Bellman-Ford : Méthode permettant de calculer les chemins minimaux entre un sommet source et tous les autres sommets d’un graphe pondéré, même avec des poids négatifs. Il détecte aussi les cycles de poids négatif.

• Algorithme de Floyd-Warshall : Technique permettant de déterminer les distances minimales entre toutes les paires de sommets dans un graphe pondéré, en utilisant une programmation dynamique.

• Distance : Longueur du plus court chemin entre deux sommets dans un graphe pondéré, prenant en compte les poids des arcs.

• Cycle de poids négatif : Circuit dans un graphe dont la somme des poids des arcs est négative, rendant impossible la définition d’un chemin de coût minimal.

• Matrice de distances : Matrice où chaque élément représente la distance minimale entre deux sommets, calculée par Floyd-Warshall ou Bellman-Ford.

• Complexité : La mesure du nombre d’opérations nécessaires pour exécuter un algorithme. Bellman-Ford a une complexité en O(n·m), Floyd-Warshall en O(n³), avec n le nombre de sommets.

📝 Points essentiels

• Bellman-Ford fonctionne en relaxant toutes les arêtes du graphe à chaque itération, répétée n-1 fois, pour trouver les chemins minimaux depuis une source donnée.

• Il peut détecter l’existence de cycles de poids négatif en vérifiant si une amélioration est possible après n-1 itérations.

• Floyd-Warshall utilise une approche de programmation dynamique, en construisant progressivement la matrice des distances minimales en passant par tous les sommets intermédiaires.

• La méthode de Floyd-Warshall permet de calculer simultanément toutes les distances entre chaque paire de sommets, ce qui est efficace pour des graphes denses.

• La présence d’un cycle de poids négatif peut être détectée dans Floyd-Warshall en vérifiant si la diagonale de la matrice des distances devient négative.

• Ces algorithmes sont fondamentaux pour résoudre des problèmes de routage, de planification ou d’optimisation dans des réseaux.

💡 À retenir

Bellman-Ford est adapté pour les graphes avec poids négatifs et pour détecter les cycles négatifs, tandis que Floyd-Warshall permet de connaître toutes les distances minimales entre tous les sommets en une seule étape.

📊 Tableaux de Synthèse

Caractéristique	Graphe non orienté	Graphe orienté
Représentation	Ligne sans flèche	Flèche indiquant la direction
Matrice d’incidence	Coefficients 0 ou 1	Coefficients +1 ou -1 selon la direction
Matrice d’adjacence	Symétrique (aij = aji)	Asymétrique (aij ≠ aji possible)
Degré du sommet	Nombre d’arêtes incidentes	Degré entrant, sortant, total
Connexité	Tout sommet accessible depuis tout autre	Tout sommet accessible depuis tout autre (fortement)
Chemins / Cycles	Chemin simple, cycle sans orientation	Chemin simple, cycle dans un sens ou dans l’autre
Sous-ensemble particulier	Clique (tous reliés)	Strongly connected component (tous mutuellement accessibles)

⚠️ Pièges & Confusions Fréquentes

1. Confondre degré entrant et degré sortant dans un graphe orienté.
2. Confondre graphe simple et graphe avec arêtes multiples ou boucles.
3. Confondre la matrice d’incidence et la matrice d’adjacence.
4. Supposer que la matrice d’adjacence est toujours symétrique dans un graphe orienté.
5. Confondre connexité (non orienté) et forte connexité (orienté).
6. Oublier que dans un graphe orienté, un sommet peut avoir un degré total différent de la somme des degrés entrant et sortant.
7. Confondre parcours en largeur (BFS) et en profondeur (DFS) dans l’analyse des composantes.

✅ Checklist Examen

• Maîtriser la différence entre graphe orienté et non orienté.
• Savoir définir et calculer le degré entrant, sortant et total d’un sommet.
• Connaître la représentation matricielle (incidence et adjacency) d’un graphe.
• Être capable de distinguer une composante connexe d’une composante fortement connexe.
• Savoir utiliser l’algorithme BFS pour explorer un graphe et identifier ses composantes.
• Connaître la définition et la propriété d’un cycle ou circuit.
• Comprendre la notion de chemin simple et de parcours sans répétition.
• Savoir identifier une clique ou un sous-ensemble stable.
• Maîtriser la différence entre connexité et forte connexité.
• Savoir appliquer l’algorithme de Kosaraju pour rechercher les composantes fortement connexes.
• Connaître le principe de l’algorithme de Bellman-Ford pour les plus courts chemins avec poids négatifs.
• Maîtriser l’algorithme de Floyd-Warshall pour tous les plus courts chemins.
• Vérifier la maîtrise du vocabulaire spécifique : sommet, arc, arête, chemin, cycle, composante.
• Vérifier la compréhension des représentations graphiques et matricielles.
• S’assurer de la maîtrise des propriétés de connexité dans les graphes orientés et non orientés.