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
É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
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
Exercice 1 Soient d = (d1
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 :.
CHAPITRE 4 GRAPHES CONNEXES 23
Option spécifique - JtJ 2016
Chapitre 4: Graphes connexes
Introduction
Représentation des liens entre
quelques sites internet créésà l'aide du logiciel
Internet Cartographer.
À quel moment un réseau informatique satisfait-il à la propriété que tous les ordinateurs du réseau, pris deux à deux, puissent partager l'information ? Des messages peuvent-ils lui être envoyés au moyen d'un ou de plusieurs ordinateurs intermédiaires ? Quand un graphe sert à représenter ce réseau informatique, où les sommets sont des ordinateurs et les arcs, les liens de communication, cette question devient: Existe-t-il toujours une chaîne entre deux sommets de ce graphe ?4.1 Connexité dans un graphe non orienté
Définition
Un graphe non orienté est connexe s'il y a une chaîne entre n'importe quelle paire de sommets distincts du graphe. Par conséquent, n'importe lequel des ordinateurs de ce réseau peut communiquer si et seulement si le graphe de ce réseau est connexe.Exemple
Le graphe G est connexe puisqu'il existe une chaîne entre n'importe quelle paire de sommets distincts. Le graphe H n'est pas connexe; par exemple, il n'y a pas de chaîne entre les sommets a et d. ab d fe gc GHab f ecdCHAPITRE 4 GRAPHES CONNEXES 24
Option spécifique - JtJ 2016
Définition
Un graphe qui n'est pas connexe est l'union de deux ou de plusieurs sous-graphes connexes, chaque paire de ceux-ci n'ayant pas de sommet en commun. Les sous-graphes connexes disjoints sont les composantes connexes du graphe.Exemple
Dans la figure précédente, le graphe H contient deux composantes connexes: H 1 formé des sommets a, b et c et H 2 formé des sommets d, e et f.Exercice 38
Dans les 3 graphes suivants, déterminer le nombre de composantes connexes :Exercice 39
Quel est le nombre minimum d'arêtes dans un graphe connexe formé de n sommets ?Démontrer votre affirmation.
Exercice 40
Combien y a-t-il de graphes simples connexes non isomorphes qui ont n sommets quand n est égal à : a) 2 ? b) 3 ? c) 4 ?Exercice 41
Soit G un graphe simple formé de n sommets. Montrer que : a) ce graphe contient au plus n(n1) 2 arêtes ; b) ce graphe, s'il est non connexe, contient au plus (n1)(n2) 2 arêtes ; c) si ce graphe contient au moins (n1)(n2) 2 + 1 arêtes, alors il est connexe.Exercice 42
Considérons un graphe simple connexe formé de 10 sommets. Que pouvez-vous affirmer au sujet du nombre d'arêtes ?CHAPITRE 4 GRAPHES CONNEXES 25
Option spécifique - JtJ 2016
En reprenant l'exemple d'introduction du réseau informatique, il peut arriver qu'un des liens ou qu'un des ordinateurs du réseau tombe en panne. Pour la bonne gestion de ce réseau, il faudrait que celui-ci reste encore connexe.Définition
Le retrait d'un sommet et de toutes les arêtes incidentes à ce sommet conduit à former un sous-graphe avec plus de composantes connexes que dans le graphe initial. Ces sommets sont appelés points de coupure. Le retrait d'un point coupure à partir d'un graphe connexe produit un sous-graphe qui n'est pas connexe. De façon similaire, une arête dont le retrait produit un graphe avec plus de composantes connexes que dans le graphe initial est appelée un séparateur.Exemple
Trouvez les points de coupure et les séparateurs dans le graphe illustréà la figure ci-contre.
Solution: • Les points de coupure sont b, c et e. Le retrait de l'un de ces sommets et de ses arêtes adjacentes sectionne le graphe. • Les séparateurs sont {a ; b} et {c ; e}. Le retrait de l'un d'eux sectionne le graphe.Exercice 43
a) Dans les 3 graphes suivants, trouver tous les points de coupure. b) Trouver tous les séparateurs des graphes précédents. a b fd che g ead cb f a b cd f e FG a eb d f c i g h HCHAPITRE 4 GRAPHES CONNEXES 26
Option spécifique - JtJ 2016
Exercice 44
Un réseau de communication informatique (Serveur - Terminaux) doit être sécurisé par un cycle de secours en cas de défaillance de liens. Déterminer le nombre minimum de liens qui faut ajouter afin de pouvoir pallier à une rupture d'un lien initial quelconque dans le réseau. Préciser le/les liens qu'il s'agit ajouter.4.2 Connexité dans les graphes orientés
Définition
Un graphe orienté est fortement connexe s'il existe un chemin du sommet a au sommet b et du sommet b au sommet a, quels que soient les sommets représentés par a et b dans le graphe. Un graphe orienté est faiblement connexe s'il y a une chaîne entre n'importe quelle paire de sommets dans le graphe si l'on ne considère plus l'orientation des arcs.Exemple
Les graphes G et H présentés ci-contre sont-ils fortement connexes ?Sont-ils faiblement connexes ?
Solution: Le graphe G est fortement connexe parce qu'il existe un chemin entre n'importe quelle paire de sommets dans ce graphe orienté (vérifiez-le !!). Par conséquent, G est également faiblement connexe. Le graphe H n'est pas fortement connexe, car par exemple, il n'existe pas de chemin orienté de ...... vers ....... Vous pouvez vérifier par contre qu'il existe une chaîne entre n'importe quelle paire de sommets du graphe si l'on ne considère pas l'orientation.H est donc faiblement connexe.
ServeurT
3 T2 T1 T4 T5 T6 T7 T8T9 T10 T11 T12 T13 a eb d c G a eb d c HCHAPITRE 4 GRAPHES CONNEXES 27
Option spécifique - JtJ 2016
Exercice 45
a) Le graphe suivant est-il fortement connexe ? b) Déterminer alors le nombre de composantes fortement connexes.4.3 Quelques applications
Exercice 46
Démontrer qu'un graphe simple à n sommets où le degré de chacun d'eux est supérieur ou égal à n1 2 est connexe.Exercice 47
Dans ce pays il y a 15 villes; chaque ville est reliée par des chemins à7 villes au moins. Démontrer qu'en partant de chaque ville on peut
atteindre toute autre ville (en passant peut-être par d'autres villes).Exercice 48
À Grapheville, on ne peut se déplacer qu'en métro. De la station "Centre" partent 7 lignes, de la station "Loin-loin" ne part qu'une seule ligne. De toutes les autres stations partent 4 lignes. Montrer qu'on peut se rendre en métro de "Centre" à "Loin-loin".Exercice 49
Montrer que, parmi 6 personnes, il y a un groupe de 3 personnes qui se connaissent mutuellement, ou bien un groupe de 3 qui ne se connaissent pas.CHAPITRE 4 GRAPHES CONNEXES 28
Option spécifique - JtJ 2016
Exercice 50
On considère l'algorithme suivant:
ALGORITHME
Donnée: Un sommet x du graphe
Résultat: L'ensemble C, composante connexe contenant x1: C = Ø ; E = {x}
2: Tant que E n'est pas vide faire
3: Choisir un élément y de E
quotesdbs_dbs12.pdfusesText_18[PDF] exercice le videoprojecteur physique corrige
[PDF] exercice lentille convergente 1ere s corrigé
[PDF] exercice ln terminale es
[PDF] exercice loi binomiale 1ere es
[PDF] exercice management de projet
[PDF] exercice masculin féminin ce1 en ligne
[PDF] exercice math 1ere s avec corrigé
[PDF] exercice math 3eme pdf
[PDF] exercice math bac maroc
[PDF] exercice mathematique niveau 3eme
[PDF] exercice maths 1ere es
[PDF] exercice maths bac pro
[PDF] exercice maths division euclidienne 3eme
[PDF] exercice maths seconde corrigé
