Recherche Opérationnelle Introduction Recherche OpérationnelleIntroduction

Recherche Opérationnelle Introduction

Recherche Opérationnelle Introduction

Recherche Opérationnelle Introduction

Recherche Opérationnelle Introduction

Recherche Opérationnelle Introduction

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

1 3

2 4

5

6

8

7

+-

+ +

+

+

++

+

- -

- -

Première Composante: C1={1,2,3,4,5}

6

8

7+

+

-

-

-

Deuxième Composante: C2={6,7}

8

+-

Troisième Composante: C3={8}

Recherche Opérationnelle Graphes

ALGORITHME DE MARQUAGE

Recherche Opérationnelle Graphes

• Arbre : Exemples (Graphe connexe et sans cycle)

Arbre m= n-1

• Feuille d’un arbre : sommet de degré 1

Proposition : Tout arbre admet au moins deux feuilles

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Recherche Opérationnelle Graphes

Exercice 1a) Donner la matrice d'incidence sommets-arcs, la matrice d'adjacence sommets-sommets et la fonction d'incidence des graphes suivants :i) ii)

Recherche Opérationnelle TD Graphes

b) Représenter graphiquement les graphes orientes associes aux matrices d'incidence sommets-arcs suivantes :

c) Representer graphiquement le graphe oriente donne par la fonction d'incidence suivante :

Exercice 2Déterminer les composantes fortement connexes des digraphes suivants en utilisant un algorithme de marquage.

Recherche Opérationnelle TD Graphes