Réalisées Par: Donia

Réalisées par : karoui hend , Ettouil Safa , Zidi Donia

• Enseignant :

Mr Hallaoui Maher 1

Plan

Exercice 2

Exercice 3

2

Représentation de graphe

Représentation graphe partiel

Représentation sous-graphe

Exercice 2

Représentation d’un sous graphe partiel 3

D A

E

B

C

ES={A,B,C,D,E} EA={AD , AB, AE,BC,CE,DE ,BD,CD}

• Graphe orientée simple de 5 sommets et 8 arcs 4

5

6

D

E

Un graphe Gp(ES,EA’) est un graphe partiel de G(ES,EA) si E A’ ⊂ E A.

A

B

C ES={A,B,C,D,E} EA={AD , AB, AE,BC,CE,DE ,BD,CD} EA’={AD , AB, BC,CE} 7

8

9

10

D ES={A,B,C,D,E} EA={AD , AB, AE,BC,CE,DE ,BD,CD} Es={A,B,C} Ea={AB,AD}

A

Un graphe Gs(ES,Ea) est un sous-graphe de G(ES,EA) si ES ⊂ ES et Ea est la restriction de la fonction caract´eristique de E A a` ES.

B

11

A

D

Un sous-graphe partiel Combine les deux points pr´ec´edents

B

12

13

Exercice 3 14

Graphe initial

. Un graphe G(ES, E A) est le graphe compl´ementaire a G(ES,E A) si pour chaque deux sommets x et y de G : – si x~y ∈ E~ A alors x~y / ∈ ¯ E~ A ; – si x~y ∈ ¯ E~ A alors x~y / ∈ E~ A;

15

Graphe complementaire

16

17

18

19

20