Avertissement

Ce contenu a été généré par une intelligence artificielle (LLM) et peut contenir des imprécisions ou des erreurs malgré notre relecture attentive. Il s'agit d'un outil d'apprentissage et non d'une référence académique.

Si vous constatez des erreurs, merci de nous les signaler via la page "À propos".

Chaînes, parcours, cycles et tours - fiches de révision (A)

Quelle est la différence entre un parcours et une chaîne dans un graphe ?

Solution

Dans un graphe G=(S,A)G=(S,A), la différence réside dans l'unicité des sommets visités :

  1. Un parcours est une suite de sommets (s0,s1,…,sk)(s_0, s_1, \dots, s_k) reliés par des arêtes. On a le droit de repasser plusieurs fois par le même sommet ou la même arête.
  2. Une chaîne est un parcours particulier où tous les sommets sont distincts deux à deux.

Note : Une chaîne est toujours un parcours, mais un parcours n'est pas forcément une chaîne.

Exemple :

Dans un triangle 1−2−3−11-2-3-1 :

  • (1,2,3)(1, 2, 3) est une chaîne (sommets distincts).
  • (1,2,3,1,2)(1, 2, 3, 1, 2) est un parcours (répétition de 1 et 2), mais pas une chaîne.

Qu'est-ce qu'un cycle dans un graphe et quelle est sa différence avec un tour ?

Solution

Ce sont des déplacements fermés (le point de départ est le point d'arrivée, s0=sks_0 = s_k).

  • Un tour : Un parcours fermé où toutes les arêtes empruntées sont distinctes (mais on peut repasser par un sommet).
  • Un cycle : Un tour particulier où tous les sommets intermédiaires sont distincts. Seul le sommet de départ/fin est répété.

En résumé :

  • Cycle : Sommets distincts (ordre k≥3k \geq 3).
  • Tour : Arêtes distinctes.

Hiérarchie : Tout cycle est un tour, mais tout tour n'est pas un cycle.

Comment définir la connexité d'un graphe ?

Solution

Un graphe est dit connexe si, pour n'importe quelle paire de sommets {x,y}\{x, y\}, il existe une chaîne (ou un parcours) reliant xx à yy.

Si le graphe n'est pas connexe, il est formé de plusieurs sous-ensembles disjoints appelés composantes connexes.

Propriété visuelle : Un graphe est connexe s'il est "d'un seul tenant".

Quelle est la relation entre la Matrice d'Adjacence et le nombre de parcours ?

Solution

Si AGA_G est la matrice d'adjacence d'un graphe, alors le coefficient (AGk)ij(A_G^k)_{ij} de la matrice élevée à la puissance kk donne une information précise sur les parcours.

Formule :

(AGk)ij=nombre de parcours de longueur k reliant le sommet i au sommet j(A_G^k)_{ij} = \text{nombre de parcours de longueur } k \text{ reliant le sommet } i \text{ au sommet } j

Utilisation :

Pour savoir s'il existe un chemin de longueur 3 entre le sommet 1 et le sommet 4, on calcule AG3A_G^3 et on regarde la valeur à la ligne 1, colonne 4.

Quelle est la condition nécessaire et suffisante pour qu'un graphe soit Eulérien ?

Solution

D'après le Théorème d'Euler (7.11), un graphe connexe est eulérien (possède un tour fermé passant par toutes les arêtes une seule fois) si et seulement si :

Tous ses sommets sont de degré pair.

Moyen mnémotechnique : Pour ne pas rester coincé dans un sommet ou ne pas laisser d'arête non parcourue en y entrant, il faut pouvoir en ressortir. Chaque passage consomme 2 arêtes (entrée + sortie), donc le degré doit être pair.

Quelle est la définition de la distance dG(s,t)d_G(s, t) entre deux sommets ?

Solution

La distance dG(s,t)d_G(s, t) est la longueur de la chaîne la plus courte (nombre d'arêtes minimal) reliant le sommet ss au sommet tt.

Cas particuliers :

  • Si s=ts = t, alors dG(s,t)=0d_G(s, t) = 0.
  • Si ss et tt ne sont pas reliés (pas dans la même composante connexe), alors dG(s,t)=∞d_G(s, t) = \infty.

Qu'est-ce qu'un graphe Hamiltonien ?

Solution

Un graphe est Hamiltonien s'il contient un cycle hamiltonien, c'est-à-dire un cycle qui passe par chaque sommet du graphe exactement une fois.

Différence avec Eulérien :

  • Eulérien : On veut parcourir toutes les arêtes.
  • Hamiltonien : On veut parcourir tous les sommets.

Note : Savoir si un graphe est hamiltonien est un problème algorithmique difficile (pas de condition simple "si et seulement si" comme pour les degrés pairs).

Qu'est-ce qu'un arbre en théorie des graphes ?

Solution

Un arbre est un graphe qui vérifie deux propriétés fondamentales simultanément :

  1. Il est connexe (d'un seul tenant).
  2. Il est acyclique (ne contient aucun cycle).

Vocabulaire : Une collection d'arbres disjoints (un graphe acyclique mais non connexe) est appelée une forêt.

Quelles sont les propriétés équivalentes définissant un arbre d'ordre nn ?

Solution

Pour un graphe GG à nn sommets, les propriétés suivantes sont équivalentes :

  1. GG est connexe et sans cycle.
  2. Il existe une chaîne unique entre toute paire de sommets.
  3. GG est connexe et possède exactement n−1n-1 arêtes.
  4. GG est sans cycle et possède exactement n−1n-1 arêtes.

Formule clé : Nombre d'arêtes m=n−1m = n - 1.

À quoi sert l'Algorithme de Dijkstra ?

Solution

L'algorithme de Dijkstra sert à trouver le plus court chemin entre un sommet de départ et tous les autres sommets dans un graphe valué (où les arêtes ont des poids).

Condition d'utilisation :

Les poids des arêtes doivent être positifs.

Principe :

Il explore le graphe de proche en proche ("glouton") en validant définitivement le sommet le plus proche non encore visité à chaque étape.

Quand un graphe est-il semi-eulérien ?

Solution

Un graphe est semi-eulérien s'il existe un parcours (ouvert, départ ≠\neq arrivée) qui passe par toutes les arêtes exactement une fois.

Condition :

Le graphe doit être connexe et posséder exactement 2 sommets de degré impair.

Explication :

Le parcours doit obligatoirement commencer sur l'un des sommets de degré impair et se terminer sur l'autre.