Graphiques Orientés PDF Graphiques Orientés . 2. Exercice

Graphes Orientés

Un graphe orienté est un graphe dont les arêtes sont orientées (c'est à Les joueurs A et B sont donc sélectionnés. 3. Exercice 2 ( sujet bac Liban mai 2006).

GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir

Exercice n°1. Un groupe d'amis organise une randonnée dans les Alpes. On a représenté par le graphe ci-dessous les sommets B

Quelques rappels sur la théorie des graphes

Un graphe orienté est un p-graphe s'il comporte au plus p arcs entre deux sommets. Le plus souvent on étudiera des 1-graphes. 1. Page 2. IUT

Exercice sur les Graphes

Principe : Parcourir le graphe à partir du point a dans le sens direct (i.e. en suivant les flèches des arcs puisque nous sommes ici dans le cadre orienté)

Premi`eres notions sur les graphes

TD Graphes et Langages feuille n◦ 1. Premi`eres notions sur les graphes. Exercice 1 On consid`ere le graphe orienté G = (S A) tels que. S = {1

Théorie des graphes et optimisation dans les graphes Table des

pred(si)

ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES

Exercice 1. (o) Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation « être diviseur

Chapitre 4: Graphes connexes 4.1 Connexité dans un graphe non

Exercice 42 Considérons un graphe simple connexe formé de 10 sommets. Que Un graphe orienté est faiblement connexe s'il y a une chaîne entre n'importe ...

Introduction à la théorie des graphes

Exercice. Soit G un graphe simple orienté d'ordre n de matrice d'adjacence M. Mon- trer que si Mn n'est pas nulle

Les exercices marqués par (*) sont à traiter en travail personnel. d

Exercice 1. Appliquer l'algorithme du parcours en largeur PL(G s) au graphe non-orienté G1 de la feuille 1 à partir du sommet s1 et au graphe orienté G1 de

Graphiques Orientés

Graphiques Orientés . 2. Exercice 1. Un club de tennis doit sélectionner deux joueurs parmi quatre pour désigner le club à un tournoi régional.

GRAPHES - EXERCICES CORRIGÉS Compilation effectuer à partir de

Exercice n°1. Un groupe d'amis organise une randonnée dans les Alpes. On a représenté par le graphe ci-dessous les sommets B

Chapitre 4: Graphes connexes 4.1 Connexité dans un graphe non

Définition Un graphe non orienté est connexe s'il y a une chaîne entre n'importe Exercice 40 Combien y a-t-il de graphes simples connexes non isomorphes ...

Théorie des graphes et optimisation dans les graphes Table des

Exercice : Dessiner un graphe non orienté complet à 4 sommets. Quel est le degré des som- mets de ce graphe ? Combien d'arêtes possède-t-il ?

Chapitre 3: Quelques caractéristiques permettant de différencier les

Exercice 13 Pour les 2 graphes suivants déterminer le nombre de sommets

Chapitre 1: Éléments de réponses Chapitre 2: Éléments de réponses

Remarque: un graphe à n sommets est très souvent représenté à l'aide du polygone régulier à n sommets. Exercice 3. Graphe orienté. Exercice 4.

Ensimag

Exercice 1.1. —. (a) Montrer que la somme des degrés des sommets d'un graphe G = (VE) non-orienté est égale à deux fois le nombre d'arêtes

Exercices …

Contenu : graphe orienté ; matrice associée à un graphe orienté. Exemple 17 : coloration de graphes. - Montrer que le nombre chromatique du graphe (1) ci-

Baccalauréat ES spécialité Index des exercices avec des graphes

On oriente et on pondère le graphe G ci-dessus pour qu'il représente un réseau Pour la suite de l'exercice on donne les matrices suivantes :.

Graphes Orientés

1. Définitionsp2

2. Exercice 1p3

3. Exercice 2p3

Graphes Orientés

1. Définitions

. Un graphe orienté est un graphe dont les arêtes sont orientées (c'est à dire : on ne peut parcourir les arêtes

que dans un sens).

Exemple :

. Une boucle est une arête orientée dont l'origine et l'extrémité sont confondues.

Exemple

. Matrice associée à une graphe orienté On numérote les sommets suivant l'ordre alphabétique .

Pour le premier exemple :

M=(0111

0011 0000

0010)a12=1 1èreligne et 2ème colonne

car il y a une arête orientée de A vers B a21=0 2ème ligne et 1ère colonne car il n'existe pas d'arête orientée de B vers A. La matrice associée à un graphe orienté n'est pas nécessairement symétrique.

Pour le deuxième exemple

M= (110 001

Graphes Orientés

2. Exercice 1

Un club de tennis doit sélectionner deux joueurs parmi quatre pour représenter le club à un tournoi régional.

Les quatre joueurs sont notés : A ; B ; C et D.

Pour réaliser la sélection le club organise des matchs : chaque joueur rencontre les trois autres.

Tout match gagné donne un point, tout match perdu enlève un point. Les joueurs sélectionnés sont les joueurs ayant obtenus le plus grand nombre de points. On donne le résultat sous la forme d'un graphe orienté.

Remarque :

Une flèche orientée de A vers B indique que le joueur A a battu le joueur B.

Conséquence

Le joueur A a gagné 3 matchs donc 3 points.

Le joueur B a gagné 2 matchs et perdu 1 match donc 1 point.

Le joueur C a perdu 3 matchs donc -3 points.

Le joueur D a gagné 1 match et perdu 2 matchs donc -1 point.

Les joueurs A et B sont donc sélectionnés.

3. Exercice 2 ( sujet bac Liban mai 2006)

1. Dans un parc, il y a cinq bancs reliés entre eux par des allées.

On modélise les bancs par les sommets A, B, C, D,E et les allées par les arêtes du graphe G ci-dessous :

Graphe G

Graphes Orientés

a. On désire peindre les bancs de façon que deux bancs reliés par une allée soient toujours de couleurs diffé-

rentes. Donner un encadrement du nombre minimal de couleurs nécessaires et justifier.

Déterminer ce nombre.

b. Est-il possible de parcourir toutes les allées de ce parc sans passer deux fois par la même allée ?

2. Une exposition est organisée dans le parc. La fréquentation devenant trop importante, on décide d'instaurer

un plan de circulation : certaines allées deviennent à sens unique, d'autre reste à double sens. Par exemple la

circulation dans l'allée située entre les bancs B et C pourra se faire de B vers C et de C vers B, alors que la

circulation dans l'allée située entre les bancs A et B ne porra se faire que de A vers B. le graphe G' ci-dessous

modélise cette nouvelle situation :

Graphe G'

a. Donner la matrice M associée au graphe G'. (On ordonnera les sommets par ordre alphabétique).

b. On donne M5=(169610

457115

466115

1510610

655142)Combien ya-t-il de chemins de longuer 5 permettant de se rendre du sommet D au sommet B ?

Les donner tous.

c. Montrer qu'il existe un seul cycle de longueur 5 passant par A.

Quel est ce cycle ?

En est-il de même pour le sommet B ?

CORRECTION

1. Les sommets B et D sont de degré 3 et les sommets A, C et E sont de degré 2.

Δ=3

Le nombre chromatique est inférieur ou égal à Δ+1=4.

Si on considère le sous graphe B ; C ; D, ce sous graphe est complet, donc le nombre chromatique est supé-

rieur ou égal à 3.

Conclusion

Graphes Orientés

Le nombre chromatique est compris entre 3 et 4.

Pour le déterminer, on colorie le graphe G en utilisant l'algorithme de coloration. Liste ordonnée des sommets : B ; D ; A ; C ; E Liste ordonnée des couleurs : Rouge ; Vert ; Jaune . . .

On a déterminé une coloration du graphe contenant 3 couleurs, donc le nombre chromatique est égal à 3.

b. Il y a deux et seulement 2 sommets de degré impair, le théorème d'Euler permet d'affirmer qu'il existe au

moins une chaîne eulérienne c'est à dire on peut parcourir toutes les allées de ce parc sans passer deux fois

par la même allée.

Exemple de chaîne eulérienne : BDEABCD.

2.a. M=

(01001 00110
01010
00101

10010)b. Le cefficient

a42=5 dans M5 donc il y a 5 chemins de longueur 5 reliant D en B. DEDEAB DEAEAB DCDEAB DCBDCB DEABCB

c. Le coefficient a11=1 dans M5 donc il y a une seule chaîne fermée de longueur 5 d'origine et d'extrémité A.

On détermine cette chaîne ABCDEA et cette chaîne est un cycle de longueur 5.

Remarque

Tout cycle de longueur 5 passant par A est une chaîne fermée de longueur 5 d'origine et d'extrémité A.

Conclusion

Il existe un seul cycle de longueue 5 passant par A.

Le coefficient a22=5 dans M5 donc il existe 5 chaînes fermées de longueur 5 d'origine et d'extrémité B.

On détermine ces 5 chaînes.

BCDEAB cette chaîne est un cycle.

BCBDCB cette chaîne n'est pas un cycle, elle contient deux fois l'arête CB.

BDEDCB cette chaîne est un cycle .

Graphes Orientés

BDCDCB cette chaîne n'est pas un cycle, elle contient deux fois l'arête DC. BDCBCB cette chaîne n'est pas un cycle, elle contient deux fois l'arêteCB.

Conclusion

Il existe deux cycles de longueur 5 passant par B.quotesdbs_dbs12.pdfusesText_18

[PDF] Graphiques Orientés Graphiques Orientés . 2. Exercice

Graphes Orientés

1. Définitionsp2

2. Exercice 1p3

3. Exercice 2p3

Graphes Orientés

1. Définitions

Exemple :

Exemple

Pour le premier exemple :

M=(0111

0010)a12=1 1èreligne et 2ème colonne

Pour le deuxième exemple

Graphes Orientés

2. Exercice 1

Remarque :

Conséquence

Le joueur A a gagné 3 matchs donc 3 points.

Le joueur C a perdu 3 matchs donc -3 points.

Les joueurs A et B sont donc sélectionnés.

3. Exercice 2 ( sujet bac Liban mai 2006)

1. Dans un parc, il y a cinq bancs reliés entre eux par des allées.

Graphe G

Graphes Orientés

Déterminer ce nombre.

2. Une exposition est organisée dans le parc. La fréquentation devenant trop importante, on décide d'instaurer

Graphe G'

457115

466115

1510610

655142)Combien ya-t-il de chemins de longuer 5 permettant de se rendre du sommet D au sommet B ?

Les donner tous.

Quel est ce cycle ?

En est-il de même pour le sommet B ?

CORRECTION

1. Les sommets B et D sont de degré 3 et les sommets A, C et E sont de degré 2.

Δ=3

Conclusion

Graphes Orientés

Le nombre chromatique est compris entre 3 et 4.

Exemple de chaîne eulérienne : BDEABCD.

2.a. M=

10010)b. Le cefficient

Remarque

Conclusion

On détermine ces 5 chaînes.

BCDEAB cette chaîne est un cycle.

BDEDCB cette chaîne est un cycle .

Graphes Orientés

Conclusion