Secondaire 5 • 3m
Bonjour alloprof
Ramzi a dit:<<Pour le a), il semble qu'une ligne suffit pour que le graphe devienne connexe. En effet, tu peux lier tous les points avec une arête ou une suite d'arêtes. Il en va de même pour le b). Pour le c), il semble en effet qu'il te faut ajouter deux arêtes pour que cela fonctionne.>>
vous avez dit quil faut une ligne pour que le graphe soit connexe. Je ne comprends pas ce que vous voulez dire pourquoi il faut une ligne pour que ça soit connexe alors que je vois deux lignes
vous avez dit pour le b) la même chose pour le a) Donc pouvez le dessiner dans un tableau pour que je puisse comprendre.
Pour le c) vous avez dit quil faut deux arretes pour que ça soit connexe. Dessinez ça dans un tableau merci.
Explication d'Alloprof
Cette explication a été donnée par un membre de l'équipe d'Alloprof.
Salut!
Comme expliqué par mon collègue Ramzi, un graphe connexe est un graphe en un seul morceau. En d'autres mots, si tu es sur un certain sommet, tu dois pouvoir trouver un chemin qui te mènera à tous les autres sommets!
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Par exemple, si tu es au point de départ D, et que tu veux te rendre au point d'arrivée F :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Tu ne peux pas aller de D à F directement, mais tu peux prendre ce chemin :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
ou encore celui-ci :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
En d'autres mots, il y a toujours un chemin possible dans un graphe connexe!
Cependant, dans un graphe non connexe, il n'est pas possible de se rendre à n'importe quel point à partir d'un point donné. Par exemple, il est impossible de se rendre de A à D ici :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Donc, au numéro a) de ton exercice, si tu dessines une seule arête de plus :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Le graphe devient connexe! Par exemple, si tu veux te rendre de B à C, tu peux prendre le chemin B-D-A-C.
En d'autres mots, peu importe le sommet de départ, on est en mesure d'arriver à n'importe quel autre sommet du graphe en prenant différents chemins!
Si tu ajoutes 2 arêtes :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Le graphe est aussi connexe, tu as simplement ajouté un chemin possible de plus!
Cependant, bien que ce ne soit pas explicitement formulé par l'énoncé, je pense qu'on veut que tu ajoutes le nombre d'arêtes minimal pour que le graphe devienne connexe.
Pour t'aider à mieux comprendre, imaginons que les arêtes soient des ponts, et que la construction de chaque nouveau pont (les arêtes à ajouter) nous coûtait de l'argent. On cherche toujours à économiser de l'argent, donc, on veut le moins de ponts possibles qui fera en sorte que le graphe soit connexe, c'est-à-dire qui fera en sorte qu'on puisse se déplacer partout sur le réseau à partir de n'importe quel point!
Au numéro a), avec une seule arête de plus, le graphe devient connexe! Tu peux donc ajouter l'une de ces quatre arêtes :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
ou
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
ou
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
ou
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Cela dit, si tu veux les ajouter les 4, tu peux aussi! Le graphe sera connexe, c'est juste que ce n'est pas nécessaire de toutes les ajouter, le minimum à ajouter est 1 arête. En les ajoutant les 4, cela sera plus cher!
Pour le b), c'est la même chose! Tu as un graphe contenant ces deux parties qui ne sont pas liées :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
En reliant un des sommets de la partie en rose à l'un des sommets de la partie en vert, peu importe lequel, le graphe deviendra connexe, puisque le réseau sera uni et il sera possible de trouver un chemin pour se rendre à n'importe quel sommet du graphe!
Pour le c), ton graphe est composé de trois parties :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
Il faut simplement les relier pour former un graphe connexe! Il y a plusieurs réponses possibles. Par exemple :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
ou
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
ou encore :
Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.
etc.
L'important est que si on se trouve sur la partie verte par exemple, il doit être possible de se rendre à la partie rose et la partie bleue en prenant un certain chemin.
J'espère que c'est plus clair pour toi! :)
Suggestions en lien avec la question
Suggestion en lien avec la question
Voici ce qui a été trouvé automatiquement sur le site, en espérant que ça t’aide!