Graphes Introduction et Matrice Associée - Terminale Spé Maths - Mathrix

salut et bienvenue dans le chapitre des graphes dans cette vidéo on va voir tout ce qui est définition type de grap bref toute la base pour vraiment pouvoir aborder ce chapitre ensuite on verra un théorème fondamental que tu vas constamment utiliser et on terminera par les matrices associé au graph allez on est [Musique] parti les les graphes commençons par une brève introduction alors déjà voici à quoi peut ressembler un graphe on voit quoi là alors on voit des traits on voit des boules qui sont reliées bref ça fait penser un peu à disons des maisons c'est comme si on avait la maison A B C D E et qu'ell sot reliés par des routes on dirait que c'est un peu ça alors tu es pas très loin pourquoi parce que comment on va appeler disons ces maisons c'est ce qu'on appelle dans les graphes un sommet alors là on a les sommets entre les sommets donc des fois ces sommets sont reliés ce qui les relié c'est une arête concernant les sommets deux sommets qui se touchent sont appelés sommets adjacents encore un truc à savoir chaque sommet a un degré ça c'est important de connaître parce que ceux-là ils sont assez logiques par contre le degré d'un sommet tu as probablement jamais entendu parler c'est le nombre de route entrant ou sortante si tu veux donc là on voit bien que dans ce cas-là on a 5 parce qu'il y a 1 2 3 4 5 qui sort et finalement le dernier truc c'est un sousgphe c'est quoi un sousgphe un sousgphe je peux appeler par exemple M un sousgphe parenè un sous-gphe de G et m dans ce CASL ce sera que une partie si je prends ça voilà ça c'est bien un sous-graphe de ça donc c'est juste une partie du graphe si tous les sommets sont 2 à 2 adjacents alors on dit que le graphe est complet alors déjà ça veut dire quoi tous les sommet 2 à2 adjacent on vient de voir qu'un sommet adjacent qu'est-ce qu'on a ici comme sommet adjacent on a AB on a BC ce be BD et cetera est-ce que A D est adjacent non parce queil y a pas de trait direct qui les liit ici on a AB adjacent be adjacent bon bref si tous les sommets sont de à de adjacents alors le graphe est complet est-ce que ce graphe est complet non parce qu'on vient d'en trouver deux qui sont pas liés est-ce que celui-là l' non plus parce que A et E sont pas liés par contre si je fais ça là j'ai bien un graphe complet dans ce cas-là pour le rendre complet il faudrait faire plutôt quelque chose comme ça et après encore faire venir ici faire venir bon c'est un peu plus complexe mais tu as compris l'idée tout doit se toucher ok on est bon très bien appliquons maintenant ce vocabulaire ce qu'on vient de dire si j'ai ce graphe ici alors je vais enlever les traits verts j'enlève c très ver et j'ai ce graphe comment alors ça c'est vraiment un tableau très typique que tu vas constamment faire parce que juste en dessous il y a un petit théorème prêt pour toi alors on va passer à un théorème très important mais avant tout on va compléter ce tableau donc ça c'est le tableau où tu vois les sommets donc on a bien le sommet A B C D E et on a les degrés en dessous les degrés je t'ai bien dit c'est ce qui sort donc là pour le point A on a combien de degrés on a 1 parce qu'on a une sortie celle-là ne compte pas j'ai d donc là on aurait 1 pour le point B on a combien de sorties une 2 3 4 donc là 4 pour le point C 1 2 celui-là ne compte pas 2 pour le point d le point d B D j'ai une sortie seulement he et pour le Point E j'ai une et de VO donc j'ai de voici donc ça c'est un graphe souvent on peut demander quels sont les degrés de sommet al tu demandes et une autre question aussi qu'on peut demander c'est combien ce graphe admet-il d'arêtte alors combien il admet d'arêtte une 2 3 4 5 voilà c arêtes voyz 1 2 3 4 et 5 toujours important de les les barrer ici en a 3 et ici les degrés sont 2 2 et 2 passons au théorème que je voulais te présenter alors théorème très important et justement il fait intervenir ce petit tableau alors je te l'ai fait en préchauffement on va [Musique] dire théorème la somme des degrés des sommets d'un graphe est égal à deux fois le nombre d'arrêtes du graphe comence par la première partie jusqu'à ici la somme des degrés des sommets alors là par rapport à mon graphe G là d'avant j'ai ce tableau quelle est la somme si j'écris la somme c'est 1 + 4 5 7 8 9 10 j'ai bien 10 OK et cette somme elle est égale à deux fois donc au double du nombre d'arrêtes alors le double du nombre arête ça veut dire que là il y aurait combien d'arêtes il suffit de diviser par 2 et on sait qu'il y a 5 arêtes est-ce que c'est cohérent avec ce qu'on vient de dire ici 1 2 3 4 5 il y a 5 arêtes c'est parfait donc ce théorème est cohérent de toute façon il alla être juste que c'est un théorème alors dernière petite note sur ce théorème une boucle compte x 2 alors c'est quoi une boucle une boucle je te l'ai pas encore parlé je voulais pas donner trop d'infos d'un coup c'est là on voit que les sommets sont liés par contre ce que tu as aussi le droit de faire c'est de lier B à luiême voilà tu as le droit de le lier à lui-même tu as le droit d'avoir cette boucle et ça justement c'est une boucle tu vas la compter deux fois vois ça comme une sortie et une entrée bon alors par le théorème comme j'ai dit on va avoir quoi le nombre d'arrêts tu sommes tout et tu divises par 2 on a bien 5 on peut appliquer justement ce théorème tout types de grap par exemple ça qu'est-ce qu'il a de particulier ce graphe allez il a combien de sommet de sommet il en a alors il a a il a B il a C D E A B C D a A B C D voilà il y a 5 sommets ça c'est les sommets et les degrés il y en a combien regarde le a il a 1 2 3 4 4 le B il là 1 2 3 4 4 le C 1 2 3 tu vois tu vois je renir pourquoi ils ont tous 4 et le E 3 et 4 pourquoi ils ont tous 4 à ton avis en fait là tu vas observer que on a 5 sommets et c'est un graphe allez dis-le complet ce Graph est complet ça veut dire que a il touche tous les sommets et il y en a combien des sommets en de dehors de a c'est a 5 sommets pour a ben en dehors il va en rester 4 c'est pour ça que tout le monde a 4 oui est-ce qu'on peut appliquer le théorème bien sûr qu'on peut l'appliquer pour avoir le nombre d'arrêtes alors au lieu de s'amuser à compter on en a 4 4 4 4 4 donc ça fait 5 x 4 20 divis par 2 on sait qu'il va avoir 10 arêtes si tu veux t'amuser tu peux les compter attention à pas compter des arrêtes en double donc fais bien 1 tu les barres bien au mieux donc si je résume et si tu comprends bien dès que dans les graphes tu as une question du type déterminer le nombre d'arrêtes il faut que quoi il faut que tu ce réflexe deux étapes première étape tu fais le tableau alors le tableau c'est celui-là sommet degré et la deuxème étape tu appliques le théorème qui te dit quoi qui te dit que le nombre d'arrêtte est égale à la somme allez répète avec moi des degrés et divisé par 2 donc ça ça te permettra vraiment de répondre à cet exercice type j'aimerais te laisser sur une notion fondamentale la notion des matrices associées alors matrice graphe c'est quoi maintenant ce lien oui il y en a un et c'est assez logique donc ne t'inquiète pas regarde si j'ai ce graphe en face de moi donc j'ai combien de sommets a b c d e j'ai 5 sommets jusqu'à là tout va bien je peux compter le nombre d'arrêtes en faisant le théorème le nombre de degrés bref tout ça on peut le faire il y a pas de souci mais si maintenant je te demande quelle est la matrice associée à ce graphe voici la technique une matrice cette matrice en fait tu vas la voir comme une grille voici ta grille alors tu as cinq sommets alors tu vas avir cinq entrées là et cinq entrées là oui ok alors comment je fais un lien le lien vois ça comme des routes qui connecte qui et tu vas te demander si je pars d'ici et je vais là est-ce qu'il y a un chemin ça c'est la question d'où je pars donc là je je pars de là et je vais ici est-ce qu'il y a un chemin oui non oui non si c'est un oui c'est un 1 c'est un non c'est un zé je pars de a et je vais à a je pars de a je vais à a est-ce qu'il y a un chemin oui il y en a un donc je mets un je pars de a je vais à B est-ce qu'il y a un chemin oui 1 je pars de a je vais à C est-ce qu'il y a un chemin alors moi je vais dire chemin c'est quelque chose de direct est-ce que je peux aller direct non il y a le B entre donc il y a pas un chemin de longueur une non zéro A à D non plus a à e non plus et maintenant je fais pour B je pars de B je vais vers a est-ce qu'il y a un chemin oui il y a un chemin 1 je pars de B je vais vers B est-ce qu'il y a un chemin non parce qu'il y a pas de boucle ici de B vers C oui B vers d oui B vers eu oui donc tous les autres c'est bien oui alors non oui oui oui très bien de C vers a de C vers a non de C vers B oui de C vers lui-même non c vers d non plus c vers e oui le voilà et maintenant à D de d vers a non de d vers B oui d vers e non d vers c bon bref C et E non plus donc juste de d vers B D vers B il y en a un sinon c'est non non non et non que peut-on dire de e de e vers a non plus vers B oui et vers C seulement donc vers B et vers c tout le reste c'est non et ça ça te construit ta matrice associée donc voilà donc voilà c'était une petite introduction sur les graphes avec les mots essentiel sommet arrêt sommet adjacent graphe complet degré d'un sommet avec bien sûr ce théorême très important et les matrices associées félicitations d'être arrivé jusqu'au bout de cette vidéo cette vidéo t'a plu ça tombe bien il y en a encore sur matrix.fr tu peux non seulement télécharger le résumé de cette vidéo mais aussi retrouver tout ton programme avec plein d'exercices corrigés étape par étape tu peux aussi défier tes amis dans les jeux et te mesurer à la communauté matrix pour gagner un cadeau tous les mois on se retrouve sur matrix.fr I