Graphes et Arbres

Introduction

Un graphe se note G = (V, E) avec V le nombre de sommet (vertex) et E le nombre d’arrêtes (edges).

Graphes

Graphe orienté (GO) : G = (V, A) les éléments E ont un sens, on parlera d’arc plutôt qu’arrête, par exemple graphe avec des flèches.

Graphe Simple : pas de boucles, au plus une arrête relie deux sommets (Pour aller de A vers B, j’ai au plus un chemin (arrête) pour y aller)

Graphe Complet : tout le monde et relié à tout le monde (simple et adjacent), nombre d’arrêtes = n(n-1)/2

Graphe k-régulier : si tous les sommets ont le même nombre d’arrêtes alors le graphe est k-régulier avec k le nombre d’arrêtes (= tous les sommets sont de degré k). Régulier degré 3 = cubique

Vocabulaire

Complémentaire de G : garde les sommets, on inverse les arrêtes.

Ordre : nombre de sommet (\(\Leftrightarrow \) card(V), |v|, |G|)

Boucle : les 2 extrémités de l’arrête sont les mêmes {x,x} \(\in \) E

Adjacent : deux sommet reliés par une arrête

Voisins : N(x), ensemble des voisins (neighbors) de x, \(N^{s+/e-}\)(x) dans un GO

Degré d’un sommet : d(x), nombre de voisins de x \((d^-(x) \) arrêtes qui vont vers x et \(d^+\)(x) arrêtes qui partent de x dans un GO)

La somme des degrés soit être paire ! On a un nombre pair de sommets de degré impair (donc on les groupe ensemble).

GNO : d(x) = 2|E|

GO : \(d^-\)(x) + \(d^+\)(x) = 2|E|

Matrice adjacente

Il s’agît d’une Matrice V*V, avec la valeur 1 si le sommet de la ligne à une arrête vers le sommet de la colonne sinon 0. (Dans GO, -1 sort, 1 rentre)

Dans un GNO, M est symétrique.

Types de graphes

Voici les différents types de graphes

Sous graphes

Sous-graphe partiel : on retire des arrêtes

Sous-graphe induit : on retire des sommets (et les arrêtes liés)

Sous-graphe complet = clique

Isomorphisme

Sommet est lié à des arrêtes, alors son image en faisant tourner les sommets (uniquement) doit avoir les mêmes arrêtes.

G = G’ : automorphe

Planaire : représentation sans croisements

Connexité

Connexe : Un graphe est connexe si je prends deux sommets quelconques et suis capable de les relier.

Fortement connexe : Il existe un chemin pour relier deux sommets pour tous les sommets.

Composantes connexes (=nombre morceau du graphe):

xRy : 2 sommets sont en relation s’il existe une chaine les reliant

R est une relation d’équivalence

  • Réflexive : il existe chemin reliant x et x et y et y
  • Symétrique : chaine x vers y et y vers x
  • Transitive : chaine x vers y et y vers z alors on a x vers z

Ici on a 2 composantes connexes (2 triangles qui sont les deux morceaux de notre graphe).

Distance

Diamètre = diam(G) : plus grande des plus petites distances du graph G

Distance = d(x, y) : longueur minimale d’une chaine reliant x à y

Diamètre : chemin plus court pour aller d’un point à l’autre, on regarde pour chaque point, la distance pour tous les points. On prend ensuite la distance maximale.

Le diamètre = d(2,7) = d(7,2) = diam(G) = 4

Chemins

Chaine : suite de sommets adjacents

Longueur : nombre d’arrêtes qui la composent.

Cycle : chaine fermée

Dans un GO : Chaine = Chemin et Cycle = Circuit

Arbre

Un arbre :

  1. connexe et sans cycle
  2. Il existe un unique chaîne reliant deux sommet x,y
  3. connexe mais ne l’est plus si on retire une arrête
  4. sans cycle mais ne l’est plus si on ajoute une arrête
  5. connexe et |E| =|V| -1
  6. sans cycle et |E| =|V| -1

Ces phrases sont équivalentes, si un graphe est englobé par une phrase alors il est englobé par toutes et est forcément un arbre.

Graphe

Graphes eulériens

cycle eulérien : cycle où l’on passe une seule fois par chaque arrête

cycle semi-eulérien : si c’est une chaine, on dit que c’est un cycle

Graphe est eulérien s’il est connexe et tous ses sommets sont de degré pair.

Graphe est semi-eulérien s’il est connexe et que tous sauf 2 des sommets sont de degré pair.

Graphes hamiltonien

cycle hamiltonien : cycle où l’on passe une seule fois par chaque sommet

cycle semi-hamiltonien : si c’est une chaine, on dit que c’est un cycle

Graphe est hamiltonien (conditions suffisantes mais pas nécessaires) :

  • graphe d’ordre n>=3 et tous sommets degré >= n/2
  • graphe d’ordre n>=3 et x,y non adjacents d(x)+d(y)>=n
Parcours

On veut parcourir (ou déterminer) une composante connexe en numérotant les sommets. Deux parcours classiques :

  • parcours en largeur (BFS : breadth-first search)
  • parcours en profondeur (DFS : depth-first search)

BFS : au début rien dans la pile, puis je prends le premier élément, je le numérote, il sort de la pile et je mets ses voisins que je numérote, puis je recommence avec le plus petit numéro.

DFS :au début rien dans la pile, puis je prends le premier élément, je mets ses voisins dans la pile, je numérote le dernier et je le sort, puis je recommence avec le dernier de la pile.