Recherche Opérationnelle Introduction Recherche OpérationnelleIntroduction

Recherche Opérationnelle Introduction





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}


ALGORITHME DE MARQUAGE


• 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









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

Documents

Recherche Opérationnelle Introduction Recherche OpérationnelleIntroduction