Théorie des graphes/Propriétés

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Arêtes et arcs

Propriété

• Une arête/un arc a deux extrémités. On dit qu’il est incident à ces extrémités
• Un arc a un nœud d’origine (ou départ) et un nœud d'arrivée. On dit qu’il est issu de son origine et qu’il aboutit à son arrivée
  • Vis-à-vis du nœud d’origine, un arc est sortant
  • Vis-à-vis du nœud d’arrivée, un arc est entrant
• On parle d'arêtes/arcs multiples lorsque plusieurs arêtes/arcs portent entre les mêmes sommets/nœuds
• Une boucle est une arête/un arc dont les deux extrémités sont identiques
• Une séquence d’arêtes/arcs consécutifs est appelée une chaîne / un chemin ; on note $<u,u_{1},...,u_{n},v>$ le chemin/chaîne de u à v passant par $u_{1},...,u_{n}$

On note $<a_{1},a_{2},...,a_{n}>$ le chemin/chaîne utilisant les arêtes/arcs consécutifs $<a_{1},a_{2},...,a_{n}>$

Sommets et nœuds

Propriété

• Le degré d'un sommet/nœud est le nombre d'arêtes/arcs qui lui sont incidents. Le degré entrant d'un nœud est le nombre d'arcs entrants, son degré sortant le nombre d'arcs sortants. Un sommet/nœud de degré nul est dit isolé.
• Un sommet/nœud est adjacent aux sommets/nœuds auxquels il est relié par une arête/un arc. L'ensemble des sommets/nœuds adjacents à un sommet/nœud u est appelé le voisinage de u.
• Le nœud u est un prédécesseur du nœud v s'il existe un arc (u,v). Le nœud u est un successeur du nœud v s’il existe un arc (v,u)
• Un sommet/nœud u est accessible depuis un sommet/nœud v si et seulement s'il existe un chemin de v à u. Un sommet/nœud u est coaccessible depuis un sommet/nœud v si et seulement s'il existe un chemin de u à v
• La distance δ(u,v) entre deux sommets/nœuds u et v est la longueur du plus petit chemin/chaîne depuis u à v

Note : δ(u,v)=∞ si aucun chemin/chaîne ne relie u à v.

Chaînes et chemins

Propriété

• La longueur d'un chemin/chaîne c (notée $|c|$) est le nombre d'arêtes/arcs qui le constitue
• Un chemin/chaîne $c_{1}=<a_{1},...,a_{n}>$ est un sous-chemin/chaîne du chemin/chaîne $c_{2}$ si et seulement si $c_{2}=<a_{1'},...,a_{1},...,a_{n},...,a_{n'}>$
• Un circuit/cycle est un chemin/chaîne $<u_{1},...,u_{n}>$ tel que $u_{1}=u_{n}$
• Un chemin/chaîne $<a_{1},...,a_{n}>$ est simple si et seulement si $a_{i}$ ≠ $a_{j}$ ∀ i ≠ j
• Un chemin/chaîne $<u_{1},...,u_{n}>$ est élémentaire si et seulement si $u_{i}$ ≠ $u_{j}$ ∀ i ≠ j
• Un chemin/chaîne eulérien est un chemin/chaîne simple passant par toutes les arcs/arêtes
• Un chemin/chaîne hamiltonien est un chemin/chaîne élémentaire passant par tous les nœuds/sommets

Graphes

Généralités

Propriété

• Un graphe G=(S,A) est complet si et seulement si ∀u≠v∈S (u,v)∈A (ou u→v ∈A)

Note : on note $K_{i}$ le graphe complet à i sommets

• Un graphe est simple s'il ne contient ni boucles ni arêtes/arcs multiples
• Un graphe est eulérien/hamiltonien s’il contient un circuit/chaîne eulérien/hamiltonien
• Un graphe est pondéré si on lui associe une fonction w qui à chaque sommet/nœud et/ou arête/arc associe un réel
• G=(S,A) est biparti si et seulement s'il existe une partition S1∪S2 de S tel que ∀(u,v)∈A, u∈S1⇔v∈S2

Propriété

Un graphe G=(S,A) est un sous-graphe du graphe G'=(S', A') si et seulement si S⊆S’ et A⊆A’

Note : G est le sous-graphe de G’ engendré par S si et seulement si ∀(u,v)∈A’\A, u∈S⇒v∉S

Propriété

La densité d'un graphe G=(S, A) est le rapport $|A|/|S|^{2}$

• Un graphe peu dense contient peu d’arêtes/arcs
• Un graphe dense contient beaucoup d’arêtes/arcs

Connexité

Propriété

Un graphe non orienté G=(S, A) est connexe si et seulement si ∀u,v∈S il existe une chaîne reliant u à v

• Les composantes connexes d’un graphe G sont les sous-graphes maximaux connexes de G
• Un graphe est k-connexe (1 ≤ k ≤ $|S|-1$) si le retrait de k-1 sommets quelconques préserve sa connexité

Propriété

Un graphe orienté G=(N,A) est fortement connexe si et seulement si ∀u,v∈S il existe un chemin de u à v

• Les composantes fortement connexes d'un graphe G sont les sous-graphes maximaux fortement connexes de G
• Le graphe réduit de G est le graphe G où chaque composantes fortement connexes a été condensée en un seul sommet