MP, PSI et la TSI

Théorie des graphes en classes prépas CPGE

Un graphe est une structure de données non linéaire constituée de nœuds et d'arêtes. Les nœuds sont parfois appelés sommets et les arêtes sont des lignes ou des arcs reliant deux nœuds quelconques du graphe. Plus formellement, un graphe peut être défini comme:

Un graphe G est représenté par un couple (S, A) S est un ensemble fini et A une relation binaire sur S. L’ensemble S est l’ensemble des sommets de G et A est l’ensemble des arcs de G.

Il existe deux types de graphes :

  • graphe orienté : les relations sont orientées et on parle d’arc. Un arc est représenté par un couple de sommets ordonnés.
  • Graphe non orienté: les relations ne sont pas orientées et on parle alors d’arêtes.Une arête est représentée par une paire de sommets non ordonnés.

Vocabulaire

  • Une boucle est un arc qui relie un sommet à lui-même. Dans un graphe non orienté les boucles sont interdites et chaque arête est donc constituée de deux sommets distincts.
  • Degré d’un sommet : Dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes.
  • Degré sortant d’un sommet : Dans un graphe orienté, le degré sortant d’un sommet est le nombre d’arcs qui en partent,
  • Degré rentrant d’un sommet : le degré entrant est le nombre d’arcs qui y arrivent et le degré est la somme du degré entrant et du degré sortant.
  • Chemin : Dans un graphe orienté G = (S,A), un chemin de longueur k d’un sommet u à un sommet v est une séquence (u0,u1,..., ukde sommets telle que u = u0, v = uk et (ui-1, uiappartient à A pour tout i. Un chemin est élémentaire si ses sommets sont tous distincts.
  • Circuit : Dans un graphe orienté G=(S,A), un chemin (u0,u1, .... ,ukforme un circuit si u0 =uk et si le chemin contient au moins un arc. Ce circuit est élémentaire si les sommets u1, ..., uk sont distincts. Une boucle est un circuit de longueur 1.
  • Cycle : Dans le cas non orienté, un chemin v0v1, v1v2, ..., vk−1vk est un cycle si v0 = vk et si une arête n'apparait pas deux fois avec une orientation différente. Par exemple v0v1, v1v0 n'est pas un cycle dans le cas non orienté. Ce cycle est élémentaire si les sommets u1, ..., uk sont distincts. Un graphe sans cycle est dit acyclique.
  • Graphe connexe : Un graphe non orienté est connexe si chaque paire de sommets est reliée par une chaîne. Les composantes connexes d’un graphe sont les classes d’équivalence de sommets induites par la relation « est accessible à partir de ».

  • Graphe fortement connexe : Un graphe orienté est fortement connexe si pour tout couple de sommets x, y il existe un chemin reliant x à y.
    Remarque : la définition implique que si x et y sont deux sommets d’un graphe fortement connexe, alors il existe un chemin de x à y et un chemin de y à x.


Les graphes sont utilisés pour résoudre de nombreux problèmes de la vie réelle. Les graphes sont utilisés pour représenter les réseaux. Les réseaux peuvent inclure des chemins dans une ville ou un réseau téléphonique ou un réseau de circuits. Les graphes sont également utilisés dans les réseaux sociaux tels que linkedIn et Facebook. Par exemple, sur Facebook, chaque personne est représentée par un sommet (ou nœud). Chaque nœud est une structure et contient des informations telles que l’identité de la personne, le nom, email, les paramètres régionaux, etc.

Sommaire

Partager cette formation avec tes amis :