Modélisation parle concept de

graphe

Graphe (orienté)

G (N, A)

N : Ensemble de noeuds (sommets), noté 1, ... n, Cardinal (N) = n

A : Ensemble de couples issus de N x N - arc - (i, j) : i noeud initial, j noeud final

1 2

3

45

Définitions

p-Graphe :

Un graphe est un p-graphe ssipour tout couple (i,j) il n'existe pas plus de p arcs reliant i à j

Fonction d'incidence : : A -> N x N

Etiquettage des noeuds et des arcs -> G (N, A, ,, )

Type abstrait -> fonctions de manipulation : successeurs (+), prédécesseurs ( -), ...

Exemple

1 2

3

45

boucle (arc (2, 2))

2-graphe (2 arcs (5, 4))

+ (1) = {2, 4}

- (2) = {1, 2, 4}

Définitions (2)

Demi-degré d'un noeud i : Extérieur + Intérieur

Extérieur : nombre d'arcs ayant i comme extrémité intiale (cardinal de +(i))

Intérieur : ayant i comme extrémité finale

Cocycle d'un ensemble A' d'arcs inclus dans A : + (A') + - (A')

+ : Ensemble des arcs ayant leur extrémité initiale dans A' et finale dans A \ A'

- : Ensemble des arcs ayant leur extrémité finale dans A \ A' et initiale dans A'

Chaîne / Cycle (-> non orienté)

Chaine : Sequence d'arètes telle que chaque arête de la séquence(sauf la 1ere et dernieer) ait une extrémité commune avec

l'arête précédente et l'autre extrémité commune avec l'arête suivante

Elémentaire : on ne passe pas deux fois par le même sommet

Cycle : chaine dont les extrémités coïncident

Cycle élémentaire : chaine élémentaire + minimal (pas d'autre cycle)

Chemin

(dans un contexte orienté)Chaine dont tous les arcs sont orientés dans le même sens

simple : ne comporte pas deux fois le même arc

élémentaire : ne rencontre pas deux fois le même sommet

élémentaire => simple mais pas l'inverse

Réseau de transport : opérateur de base (sous contrainte)

circuit : chemin dont les extrémités coïncident

circuit élémentaire : sommets ont un degré égal à 2

Exemple

1 2

3

45

1 2

3

45

a1

a2a3

a4a5

a6

Chaîne : (a1, a5, a6, a3, a2)(-> non élémentaire)

Cycle : (a1, a5, a6, a4)

(-> élémentaire)

Chemin : (a1, a5, a7, a3) a1

a2

a3a4

a6

a5

a7

(-> non élémentaire)

Circuit : (a5, a7, a3)

Connexité

Il existe une chaine joignanttout sommet i à tout sommet j

-> Composante connexe

-> nombre de connexité = 1 <=> graphe connexe

Application transport :

-> notion d'arbre (réseau hydrolique)-> forte connexité (réseau de transport urbain, téléphone, ...)

Fortement connexe (orienté) : il existe un chemin de i à j et de j à i

Graphe planaire

Admet une représentation sur un plan

Sommet : Point Aretes : courbes

-> Deux courbes ne se rencontrent pas en dehors de leurs extrémités

1

2 3

4 5

1

2

3

45

-> Gestion des représentations schématiques

FERMETURE TRANSITIVE

CONSTRUIRE UN NOUVEAU GRAPHE G* A PARTIR DE G :

(i, j) <=> Il existe un chemin de i à j dans G

1 2

3

45

1 2

3

45

G

G*

Représentations informatique

Matrices :

Matrice adjacence : 1-graphe, (booléenne ou valuée)

Matrice d'incidence sommets-arcs (-1 -ext-, 0, 1 -orig-) ligne sommet, colonne : arc

Listes : (matrices creuses)

Listes des sommets successeurs / prédécesseurs

Listes des arcs (cocycles)

Représentations informatique (2)

Matrice : -> Que des problèmes

- Espace mémoire important- Temps passé à faire des tests (complexité des algorithmes)- Pas de flexibilité- Pas de multi-graphe

Listes

-> Type abstrait avec primitives de manipulations

- Flexibilité (insertion / suppression)- Emplacement mémoire raisonnable

Exemples

Matrice d'adjacence non valuée / non orientée // valuée / orientée

Matrice d'incidence sommets / arcs

Liste des successeurs / prédécesseurs / voisins / sommets / arcs / arêtes

Liste des cocycles orientés / non orientés

=> Problème passage d'une représentation à une autre

Exemple (2)

1 2

3

45

1 2

3

45

5

2 7

2

32

1 2

3

45

1

2 3

4

65

Fonction de coût

Numérotation des arcs

Booléenne

• 1-graphe, Non orienté 2 arcs => Matrice symétrique

1 2 3 4 5

1 0 1 0 1 0

2 1 0 1 1 0

3 0 1 0 0 1

4 1 1 0 0 1

5 0 0 1 1 0

Valuation => Fonction de coût

• Arc inexistant : 0 ou infini => problème de représentation

1 2 3 4 5

1 0 5 0 2 0

2 0 0 2 0 0

3 0 0 0 0 0

4 0 7 0 0 0

5 0 0 2 3 0

Sommets-arcs• p-graphe, pas de boucle

• Colonne : arc, ligne : sommet, origine : + destination : -

1 2 3 4 5 6

1 +1 +1 0 0 0 0

2 -1 0 -1 +1 0 0

3 0 0 0 -1 -1 0

4 0 -1 +1 0 0 -1

5 0 0 0 0 +1 +1

Successeurs• Tableau : Nœud : tableau [1.. N+1] d’indirections sur les

successeurs ([1.. M+1])

• Principe : idem pour les voisins (non orienté) mais symétrique => 2M + 1 ou pour les prédécesseurs

754431

654321

7654321

X432342

Successeurs (version liste chaînée)

1 2 3 4 5

2

4

3 2 3

4

Orienté Valué

Idem successeurs + valuation (liste chaînée : multi-graphe)

754431

654321

7654321

327225

X432342

Cocycle

• Idem liste des successeurs mais avec les arcs => p-graphes avec boucles

754431

654321

7654321

X432342

X653421

Passages

Matrice d'incidence

Liste des arcs / arêtes

Liste des cocyclesListe des prédécesseurs

Liste des successeurs

Matrice d'adjacence

O (MN)

O(M)

O(M)O(M)

O(N )

O(MN)

2

Problèmatique Base de données

Modélisation du graphe (1 ou plusieurs niveaux d'abstraction)

Fonction d'étiquettage (noeud, arc)

-> Le graphe ne tient pas en MC-> Opérateurs de manipulation - chemin -

-> Passage des informations aux différents niveaux

Problèmes conventionnels

Chemin eulérien : chemin qui emprunteune fois et une seule chaque arc

Chemin hamiltonien : chemin qui emprunteune fois et une seule chaque sommet

Stable : Sous-ensemble, S, de sommets d'un graphetels que deux sommets de S ne sont pas adjacents ()

Clique : Sous graphe complet

Problèmes conventionnels (2)

Domaine de la recherche opérationnelle (parcours / contraintes)

Bases de données déductives / documentaires

Opérateurs de manipulation : Attention aux pb NP-Complet

Bases de données spatiales (transports)