Graphes non orientés et arbres

  Un graphe est dit non orienté si la relation binaire est symétrique (si $u\to v$ alors $v\to u$) et irréflexive (pas de boucle $u\to u$) ; on peut alors considérer ensemble les deux arcs $u\to v$ et $v\to u$ comme la paire de sommets $\{u,v\}$, appelée arête . Au lieu de dessiner les deux arcs symétriques $u\to v$ et $v\to u$, on dessine seulement une arête, sans flèche, entre u et v, ce qu'on peut noter $u\leftrightarrow v$.

Dans un graphe non orienté, une chaîne $v_0, v_1, \dots, v_k$ (avec $v_i \leftrightarrow v_{i+1}$ pour tout i) telle que v_k=v₀ et qui ne contient pas deux fois la même arête est appelée un cycle  ; sa longueur est nécessairement $\ge 3$ ; un graphe non orienté sans cycle est appelé acyclique . Les propriétés suivantes sont équivalentes, si G=(S, A) est non orienté :

1.

G est acyclique et connexe ;

2.

G est acyclique et |A| = |S|-1 ;

3.

G est connexe et |A| = |S|-1 ;

4.

G est connexe et cesse de l'être si on lui retire une arête quelconque ;

5.

G est acyclique et cesse de l'être si on lui ajoute une arête quelconque ;

6.

deux sommets quelconques sont reliés par une chaîne dont tous les sommets sont distincts.

 

Un graphe vérifiant ces propriétés est appelé un arbre  (figure 2.8); un graphe non orienté acyclique qui n'est pas connexe est appelé une forêt  ; chaque composante connexe d'une forêt est un arbre.

Un arbre est enraciné  dès qu'un sommet a été désigné comme sa racine  (n'importe quel sommet peut être désigné comme racine). Une racine r détermine alors une relation de descendance : si $r\to^{\star} u\to^{\star}v$, on dit que u est ancêtre de v et que v est descendant de u ; si $r\to^{\star} u\to v$, on dit que u est le parent de v et que v est un enfant  de u ; le nombre d'enfants d'un sommet est appelé son degré. La racine n'a pas de parent ; un sommet sans enfant est appelé une feuille .

Un arbre enraciné peut alors être considéré comme un graphe orienté, avec un arc $u\to v$ quand u est le parent de v ; l'orientation inverse peut aussi être utile pour certaines applications. On dit que ce sont des arborescences  (figure 2.9).