{"id":218174,"date":"2023-10-31T05:30:00","date_gmt":"2023-10-31T05:30:00","guid":{"rendered":"https:\/\/datascientest.com\/?p=218174"},"modified":"2023-11-09T13:40:53","modified_gmt":"2023-11-09T13:40:53","slug":"theorie-des-graphes-tout-savoir","status":"publish","type":"post","link":"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir","title":{"rendered":"Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"218174\" class=\"elementor elementor-218174\" data-elementor-post-type=\"post\">\n\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8f3408e e-flex e-con-boxed e-con\" data-id=\"8f3408e\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-386a0d1 elementor-widget elementor-widget-heading\" data-id=\"386a0d1\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{color:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}<\/style><h2 class=\"elementor-heading-title elementor-size-default\">Permettant de relier plusieurs points entre eux, les graphes sont utilis\u00e9s depuis des si\u00e8cles pour simplifier la compr\u00e9hension de tous types de r\u00e9seaux. Et justement, il est possible d\u2019\u00e9tudier ces diff\u00e9rentes repr\u00e9sentations visuelles \u00e0 travers la th\u00e9orie des graphes. <\/h2>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-be2b234 e-flex e-con-boxed e-con\" data-id=\"be2b234\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-de6e5a5 elementor-widget elementor-widget-heading\" data-id=\"de6e5a5\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">La th\u00e9orie des graphes ou l\u2019\u00e9tude des graphiques<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-12d4c34 elementor-widget elementor-widget-text-editor\" data-id=\"12d4c34\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#69727d;color:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{color:#69727d;border:3px solid;background-color:transparent}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;height:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:center;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{display:inline-block}<\/style>\t\t\t\t<p><span style=\"font-weight: 400;\">La th\u00e9orie des graphes consiste \u00e0<\/span><b> \u00e9tudier les graphes<\/b><span style=\"font-weight: 400;\">. Autrement dit, des repr\u00e9sentations visuelles permettant de relier des objets entre eux.\u00a0\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">D\u2019un point de vue math\u00e9matique, le <\/span><b>graphique G correspond \u00e0 un couple de sommets V <\/b><span style=\"font-weight: 400;\">(\u00e9galement appel\u00e9 de n\u0153uds ou de points) <\/span><b>et d\u2019ar\u00eates E <\/b><span style=\"font-weight: 400;\">(\u00e9galement appel\u00e9es lignes ou liens). Ces ar\u00eates permettent alors de relier plusieurs sommets entre eux et les sommets reli\u00e9s par une ar\u00eate sont qualifi\u00e9s de voisins ou adjacents.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Voici la traduction math\u00e9matique de ces graphes : <\/span><b><i>G<\/i><\/b><b> = (<\/b><b><i>V<\/i><\/b><b>, <\/b><b><i>E<\/i><\/b><b>)\u00a0<\/b><\/p><p><span style=\"font-weight: 400;\">La th\u00e9orie des graphes \u00e9tant une sous discipline des math\u00e9matiques, elle regroupe un ensemble de th\u00e9or\u00e8mes et d\u2019<a href=\"https:\/\/datascientest.com\/algorithme-tout-savoir\">algorithmes<\/a> visant \u00e0 r\u00e9soudre divers probl\u00e8mes li\u00e9s aux r\u00e9seaux. Mais avant de voir quelques-unes de ces applications th\u00e9oriques, il convient de bien comprendre les graphes. <\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-c985b44 elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"c985b44\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formation-data-scientist\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">Se former \u00e0 la Data Science<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-e6d604b e-flex e-con-boxed e-con\" data-id=\"e6d604b\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-7e31113 elementor-widget elementor-widget-heading\" data-id=\"7e31113\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Les graphes, plusieurs mod\u00e8les pour des int\u00e9r\u00eats multiples<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-9a50a02 elementor-widget elementor-widget-heading\" data-id=\"9a50a02\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">Les diff\u00e9rents types de graphes<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-41660ba elementor-widget elementor-widget-text-editor\" data-id=\"41660ba\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<span style=\"font-weight: 400;\">Si les graphes sont tous constitu\u00e9s de plusieurs ar\u00eates et sommets, il existe en r\u00e9alit\u00e9 plusieurs types de graphes :\u00a0<\/span>\n<ul>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe non orient\u00e9 <\/b><span style=\"font-weight: 400;\">: les ar\u00eates peuvent se lire dans un sens comme dans l\u2019autre. On dit qu\u2019elles sont associ\u00e9es \u00e0 une paire {<\/span><i><span style=\"font-weight: 400;\">u<\/span><\/i><span style=\"font-weight: 400;\">, <\/span><i><span style=\"font-weight: 400;\">v<\/span><\/i><span style=\"font-weight: 400;\">} o\u00f9 \u201cu\u201d et \u201cv\u201d repr\u00e9sentent chacun un sommet.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe orient\u00e9 <\/b><span style=\"font-weight: 400;\">: les ar\u00eates vont dans un sens pr\u00e9cis (de u vers v). Dans ce cas, elles sont associ\u00e9es \u00e0 un couple {<\/span><i><span style=\"font-weight: 400;\">u<\/span><\/i><span style=\"font-weight: 400;\">, <\/span><i><span style=\"font-weight: 400;\">v<\/span><\/i><span style=\"font-weight: 400;\">} et sont qualifi\u00e9es d\u2019arcs.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe mixte :<\/b><span style=\"font-weight: 400;\"> il contient \u00e0 la fois des ar\u00eates non orient\u00e9es et des ar\u00eates orient\u00e9es (ou arc). Contrairement aux graphiques \u201ctraditionnels\u201d, sa formulation math\u00e9matique se traduit comme suit : <\/span><i><span style=\"font-weight: 400;\">G<\/span><\/i><span style=\"font-weight: 400;\"> = (<\/span><i><span style=\"font-weight: 400;\">V<\/span><\/i><span style=\"font-weight: 400;\">, <\/span><i><span style=\"font-weight: 400;\">E<\/span><\/i><span style=\"font-weight: 400;\">, <\/span><i><span style=\"font-weight: 400;\">A<\/span><\/i><span style=\"font-weight: 400;\">).<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe simple <\/b><span style=\"font-weight: 400;\">: il ne comporte aucune boucle o\u00f9 un sommet pourrait \u00eatre reli\u00e9 \u00e0 lui-m\u00eame \u00e0 travers une suite d\u2019ar\u00eates.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe pond\u00e9r\u00e9 (ou graphe valu\u00e9)<\/b><span style=\"font-weight: 400;\"> : chaque ar\u00eate est associ\u00e9e \u00e0 un poids, que ce soit une distance, un co\u00fbt, une taille, etc.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe structur\u00e9 homog\u00e8ne <\/b><span style=\"font-weight: 400;\">: l\u2019ensemble des ar\u00eates et sommets reproduit un sch\u00e9ma r\u00e9gulier. Il se pr\u00e9sente g\u00e9n\u00e9ralement comme un carr\u00e9 ou un rectangle quadrill\u00e9.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe structur\u00e9 hi\u00e9rarchique<\/b><span style=\"font-weight: 400;\"> : les sommets s&rsquo;organisent de mani\u00e8re pyramidale.<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe structur\u00e9 cyclique<\/b><span style=\"font-weight: 400;\"> : tous les points sont interconnect\u00e9s (comme un cercle)<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe structur\u00e9 centralis\u00e9<\/b><span style=\"font-weight: 400;\"> : tous les points sont connect\u00e9s \u00e0 un seul sommet (appel\u00e9 le p\u00f4le).\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe multipolaire <\/b><span style=\"font-weight: 400;\">: il est \u00e0 la fois centralis\u00e9 et d\u00e9centralis\u00e9. Dans ce cas, les ar\u00eates \u00e9manant du p\u00f4le sont appel\u00e9es les liens forts, et celles r\u00e9unissant d\u2019autres sommets sont appel\u00e9es les liens faibles. Ce mod\u00e8le est particuli\u00e8rement utilis\u00e9 pour \u00e9tudier les r\u00e9seaux de types Internet et les <a href=\"https:\/\/datascientest.com\/graph-neural-networks-tout-savoir\">r\u00e9seaux de neurones<\/a>.<span style=\"font-weight: 400;\">\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le graphe quelconque <\/b><span style=\"font-weight: 400;\">: aucune des propri\u00e9t\u00e9s susmentionn\u00e9es ne se d\u00e9gage du graphique. <\/span><\/li>\n<\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-48f3c7c elementor-widget elementor-widget-image\" data-id=\"48f3c7c\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-image{text-align:center}.elementor-widget-image a{display:inline-block}.elementor-widget-image a img[src$=\".svg\"]{width:48px}.elementor-widget-image img{vertical-align:middle;display:inline-block}<\/style>\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"885\" height=\"500\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes1.jpg\" class=\"attachment-full size-full wp-image-218190\" alt=\"\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes1.jpg 885w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes1-300x169.jpg 300w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes1-768x434.jpg 768w\" sizes=\"(max-width: 885px) 100vw, 885px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-b82b344 elementor-widget elementor-widget-text-editor\" data-id=\"b82b344\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Dans la th\u00e9orie des graphes, il est possible d\u2019associer diff\u00e9rentes familles de graphes entre eux. Par exemple, un graphe peut \u00eatre non orient\u00e9, pond\u00e9r\u00e9 et acyclique.\u00a0<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-9359aed elementor-widget elementor-widget-heading\" data-id=\"9359aed\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">L\u2019utilit\u00e9 des graphes<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-66c7f10 elementor-widget elementor-widget-text-editor\" data-id=\"66c7f10\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<span style=\"font-weight: 400;\">La th\u00e9orie des graphes a donn\u00e9 naissance \u00e0 une multitude de th\u00e9or\u00e8mes et d&rsquo;algorithmes.\u00a0 Chacun d\u2019entre eux a pour objectif de<\/span><b> r\u00e9soudre un probl\u00e8me pratique. <\/b><span style=\"font-weight: 400;\">Et pour cause, les graphes se retrouvent au sein de nombreuses applications quotidiennes. Voici les plus courantes :\u00a0<\/span>\n<ul>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Les r\u00e9seaux routiers <\/b><span style=\"font-weight: 400;\">: les villes sont alors consid\u00e9r\u00e9es comme des sommets, et les routes comme des ar\u00eates ou des arcs.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Le web :<\/b><span style=\"font-weight: 400;\"> les pages sont consid\u00e9r\u00e9es comme les sommets, et les liens hypertextes sont les ar\u00eates.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><b>Les r\u00e9seaux sociaux<\/b><span style=\"font-weight: 400;\"> : les individus sont les sommets, et leurs connexions sont les ar\u00eates.\u00a0<\/span><\/li>\n \t<li style=\"font-weight: 400;\" aria-level=\"1\"><a href=\"https:\/\/datascientest.com\/base-de-donnees-definition\">Les bases de donn\u00e9es relationnelles<\/a><span style=\"font-weight: 400;\"> : les relations correspondent aux sommets alors que les d\u00e9pendances correspondent aux ar\u00eates. Dans ce cas, il s\u2019agit d\u2019un graphe orient\u00e9.\u00a0<\/span><\/li>\n \t<li><a href=\"https:\/\/datascientest.com\/python-tout-savoir\">La programmation informatique<\/a> :<\/b><span style=\"font-weight: 400;\"> les instructions de code \u00e0 ex\u00e9cuter ou les donn\u00e9es sont les sommets. Quant aux ar\u00eates, il s\u2019agit des relations de d\u00e9pendance temporelle (l\u2019ordre dans lequel les instructions ou les donn\u00e9es s\u2019ex\u00e9cutent).<\/span><\/li>\n<\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-2b9ee1c elementor-widget elementor-widget-text-editor\" data-id=\"2b9ee1c\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Il ne s\u2019agit que de quelques exemples concrets qui ont permis le d\u00e9veloppement et l\u2019enrichissement de la th\u00e9orie des graphes. <\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-9f1a3c5 elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"9f1a3c5\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formation-data-scientist\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">Appliquer la th\u00e9orie des graphes en Data Science<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-89ae4fd e-flex e-con-boxed e-con\" data-id=\"89ae4fd\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-9bae9f6 elementor-widget elementor-widget-heading\" data-id=\"9bae9f6\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Les \u00e9l\u00e9ments de la th\u00e9orie des graphes<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-3803239 elementor-widget elementor-widget-heading\" data-id=\"3803239\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">Les graphes eul\u00e9riens<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-002a58d elementor-widget elementor-widget-text-editor\" data-id=\"002a58d\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">La th\u00e9orie des graphes a vu le jour pour la premi\u00e8re fois en 1735 gr\u00e2ce au math\u00e9maticien suisse Leonhard Euler. Celui-ci devait alors r\u00e9soudre le probl\u00e8me des sept ponts de K\u00f6nigsberg. Il s\u2019agissait d\u2019identifier une promenade permettant de partir d\u2019un point A et d\u2019y revenir en passant par les sept ponts de la ville de K\u00f6nigsberg. Et ce, tout en passant une seule fois sur chaque pont. Cette promenade donna ainsi naissance au chemin eul\u00e9rien (ou circuit eul\u00e9rien). D\u00e8s lors, <\/span><b>tout circuit permettant d\u2019arriver au point o\u00f9 il a commenc\u00e9, sans passer plusieurs fois par la m\u00eame ar\u00eate<\/b><span style=\"font-weight: 400;\"> est qualifi\u00e9 de chemin eul\u00e9rien. Et cela se transpose \u00e0 tous les graphes qui reprennent les m\u00eames propri\u00e9t\u00e9s.<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-706c36a elementor-widget elementor-widget-heading\" data-id=\"706c36a\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">La matrice d\u2019adjacence<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-797a455 elementor-widget elementor-widget-text-editor\" data-id=\"797a455\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Tr\u00e8s utilis\u00e9e en th\u00e9orie des graphes, la matrice d&rsquo;adjacence est une <\/span><b>structure de donn\u00e9es permettant de repr\u00e9senter un graphe<\/b><span style=\"font-weight: 400;\">. L\u2019id\u00e9e est alors d\u2019identifier les relations entre les sommets du graphe (qui sont repr\u00e9sent\u00e9s sur les lignes et les colonnes de la matrice). S\u2019il existe une connexion, l\u2019\u00e9l\u00e9ment correspondant est \u00e9gal \u00e0 1. \u00c0 d\u00e9faut de connexion, il est \u00e9gal \u00e0 0.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Bien souvent, elle repr\u00e9sente les graphes non orient\u00e9s. Mais elle peut aussi \u00eatre utilis\u00e9e dans les graphes orient\u00e9s. <\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-c25b24f elementor-widget elementor-widget-heading\" data-id=\"c25b24f\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h4 class=\"elementor-heading-title elementor-size-medium\">L\u2019algorithme de Kruskal<\/h4>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-c582ce2 elementor-widget elementor-widget-text-editor\" data-id=\"c582ce2\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">Il s\u2019agit alors de <\/span><b>trouver l\u2019arbre recouvrant le poids minimal <\/b><span style=\"font-weight: 400;\">dans un graphe connexe, pond\u00e9r\u00e9 et non orient\u00e9. Autrement dit, l\u2019objectif est d\u2019identifier un chemin o\u00f9 le poids des ar\u00eates connectant l\u2019ensemble des sommets est le plus l\u00e9ger possible.\u00a0<\/span><\/p><p><span style=\"font-weight: 400;\">Il ne s\u2019agit que de quelques exemples. En r\u00e9alit\u00e9, il existe en effet de nombreux autres algorithmes et th\u00e9or\u00e8mes utilisant la th\u00e9orie des graphes. Pour mieux les conna\u00eetre et les appliquer au machine learning, mieux vaut <a href=\"https:\/\/datascientest.com\/formation-data-scientist\">se former \u00e0 la science des donn\u00e9es<\/a> avec DataScientest.<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-4e62ad5 elementor-widget elementor-widget-image\" data-id=\"4e62ad5\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"843\" height=\"500\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes2.jpg\" class=\"attachment-full size-full wp-image-218194\" alt=\"\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes2.jpg 843w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes2-300x178.jpg 300w, https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes2-768x456.jpg 768w\" sizes=\"(max-width: 843px) 100vw, 843px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-bb60b09 e-flex e-con-boxed e-con\" data-id=\"bb60b09\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-ff03ba5 elementor-widget elementor-widget-heading\" data-id=\"ff03ba5\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Ce qu\u2019il faut retenir<\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-4f06841 elementor-widget elementor-widget-text-editor\" data-id=\"4f06841\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">La th\u00e9orie des graphes permet d\u2019\u00e9tudier les graphes. Autrement dit, des repr\u00e9sentations visuelles permettant de relier des points entre eux par l\u2019interm\u00e9diaire d\u2019ar\u00eates.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Il existe une multitude de graphes pour analyser tous types de r\u00e9seaux. La th\u00e9orie des graphes permet justement de tous les \u00e9tudier.\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Elle a vu le jour en 1735 \u00e0 travers les graphes eul\u00e9riens. Aujourd\u2019hui, les concepts math\u00e9matiques utilisant cette th\u00e9orie se comptent par dizaines. <\/span><\/li><\/ul>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-e036a0e elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"e036a0e\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formation-data-scientist\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">D\u00e9couvrir nos formations en Data<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-a535720 e-flex e-con-boxed e-con\" data-id=\"a535720\" data-element_type=\"container\" data-settings=\"{&quot;content_width&quot;:&quot;boxed&quot;}\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-59c68ae elementor-widget elementor-widget-html\" data-id=\"59c68ae\" data-element_type=\"widget\" data-widget_type=\"html.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<script type=\"application\/ld+json\">\r\n{\r\n  \"@context\": \"https:\/\/schema.org\",\r\n  \"@type\": \"FAQPage\",\r\n  \"mainEntity\": [{\r\n    \"@type\": \"Question\",\r\n    \"name\": \"La th\u00e9orie des graphes ou l\u2019\u00e9tude des graphiques\",\r\n    \"acceptedAnswer\": {\r\n      \"@type\": \"Answer\",\r\n      \"text\": \"La th\u00e9orie des graphes consiste \u00e0 \u00e9tudier les graphes. Autrement dit, des repr\u00e9sentations visuelles permettant de relier des objets entre eux.  D\u2019un point de vue math\u00e9matique, le graphique G correspond \u00e0 un couple de sommets V (\u00e9galement appel\u00e9 de n\u0153uds ou de points) et d\u2019ar\u00eates E (\u00e9galement appel\u00e9es lignes ou liens). Ces ar\u00eates permettent alors de relier plusieurs sommets entre eux et les sommets reli\u00e9s par une ar\u00eate sont qualifi\u00e9s de voisins ou adjacents.\"\r\n    }\r\n  },{\r\n    \"@type\": \"Question\",\r\n    \"name\": \"L\u2019utilit\u00e9 des graphes\",\r\n    \"acceptedAnswer\": {\r\n      \"@type\": \"Answer\",\r\n      \"text\": \"La th\u00e9orie des graphes a donn\u00e9 naissance \u00e0 une multitude de th\u00e9or\u00e8mes et d'algorithmes.  Chacun d\u2019entre eux a pour objectif de r\u00e9soudre un probl\u00e8me pratique. Et pour cause, les graphes se retrouvent au sein de nombreuses applications quotidiennes.\"\r\n    }\r\n  },{\r\n    \"@type\": \"Question\",\r\n    \"name\": \"Les \u00e9l\u00e9ments de la th\u00e9orie des graphes\",\r\n    \"acceptedAnswer\": {\r\n      \"@type\": \"Answer\",\r\n      \"text\": \"La th\u00e9orie des graphes a vu le jour pour la premi\u00e8re fois en 1735 gr\u00e2ce au math\u00e9maticien suisse Leonhard Euler. Celui-ci devait alors r\u00e9soudre le probl\u00e8me des sept ponts de K\u00f6nigsberg. Il s\u2019agissait d\u2019identifier une promenade permettant de partir d\u2019un point A et d\u2019y revenir en passant par les sept ponts de la ville de K\u00f6nigsberg. Et ce, tout en passant une seule fois sur chaque pont. Cette promenade donna ainsi naissance au chemin eul\u00e9rien (ou circuit eul\u00e9rien). D\u00e8s lors, tout circuit permettant d\u2019arriver au point o\u00f9 il a commenc\u00e9, sans passer plusieurs fois par la m\u00eame ar\u00eate est qualifi\u00e9 de chemin eul\u00e9rien. Et cela se transpose \u00e0 tous les graphes qui reprennent les m\u00eames propri\u00e9t\u00e9s.\"\r\n    }\r\n  }]\r\n}\r\n<\/script>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Permettant de relier plusieurs points entre eux, les graphes sont utilis\u00e9s depuis des si\u00e8cles pour simplifier la compr\u00e9hension de tous types de r\u00e9seaux. Et justement, il est possible d\u2019\u00e9tudier ces diff\u00e9rentes repr\u00e9sentations visuelles \u00e0 travers la th\u00e9orie des graphes. La th\u00e9orie des graphes ou l\u2019\u00e9tude des graphiques La th\u00e9orie des graphes consiste \u00e0 \u00e9tudier les [&hellip;]<\/p>\n","protected":false},"author":77,"featured_media":218177,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"content-type":"","inline_featured_image":false},"categories":[2497],"tags":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v21.7 (Yoast SEO v21.7) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes<\/title>\n<meta name=\"description\" content=\"Graphes pond\u00e9r\u00e9s, orient\u00e9s, hi\u00e9rarchiques, pyramidaux... Il existe une multitude de graphes. Tous sont \u00e9tudi\u00e9s par la th\u00e9orie des graphes.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes\" \/>\n<meta property=\"og:url\" content=\"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir\" \/>\n<meta property=\"og:site_name\" content=\"Formation Data Science | DataScientest.com\" \/>\n<meta property=\"article:published_time\" content=\"2023-10-31T05:30:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-09T13:40:53+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"600\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Raphael Kassel\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"Raphael Kassel\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir\",\"url\":\"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir\",\"name\":\"Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes\",\"isPartOf\":{\"@id\":\"https:\/\/datascientest.com\/#website\"},\"datePublished\":\"2023-10-31T05:30:00+00:00\",\"dateModified\":\"2023-11-09T13:40:53+00:00\",\"author\":{\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\"},\"description\":\"Graphes pond\u00e9r\u00e9s, orient\u00e9s, hi\u00e9rarchiques, pyramidaux... Il existe une multitude de graphes. Tous sont \u00e9tudi\u00e9s par la th\u00e9orie des graphes.\",\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir\"]}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/datascientest.com\/#website\",\"url\":\"https:\/\/datascientest.com\/\",\"name\":\"Formation Data Science | DataScientest.com\",\"description\":\"Leader de la formation en Data Science\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/datascientest.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\",\"name\":\"Raphael Kassel\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"contentUrl\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"caption\":\"Raphael Kassel\"},\"description\":\"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \\\"Chef de projet IA\\\" et \\\"Data Product Manager\\\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.\",\"sameAs\":[\"https:\/\/www.linkedin.com\/in\/raphaelkassel\/\",\"Data Science\"],\"url\":\"https:\/\/datascientest.com\/author\/raphaelkassel\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes","description":"Graphes pond\u00e9r\u00e9s, orient\u00e9s, hi\u00e9rarchiques, pyramidaux... Il existe une multitude de graphes. Tous sont \u00e9tudi\u00e9s par la th\u00e9orie des graphes.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir","og_locale":"fr_FR","og_type":"article","og_title":"Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes","og_url":"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir","og_site_name":"Formation Data Science | DataScientest.com","article_published_time":"2023-10-31T05:30:00+00:00","article_modified_time":"2023-11-09T13:40:53+00:00","og_image":[{"width":1200,"height":600,"url":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/10\/theorie-des-graphes.png","type":"image\/png"}],"author":"Raphael Kassel","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"Raphael Kassel","Dur\u00e9e de lecture estim\u00e9e":"6 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir","url":"https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir","name":"Th\u00e9orie des graphes\u00a0: D\u00e9finition et explications compl\u00e8tes","isPartOf":{"@id":"https:\/\/datascientest.com\/#website"},"datePublished":"2023-10-31T05:30:00+00:00","dateModified":"2023-11-09T13:40:53+00:00","author":{"@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1"},"description":"Graphes pond\u00e9r\u00e9s, orient\u00e9s, hi\u00e9rarchiques, pyramidaux... Il existe une multitude de graphes. Tous sont \u00e9tudi\u00e9s par la th\u00e9orie des graphes.","inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/datascientest.com\/theorie-des-graphes-tout-savoir"]}]},{"@type":"WebSite","@id":"https:\/\/datascientest.com\/#website","url":"https:\/\/datascientest.com\/","name":"Formation Data Science | DataScientest.com","description":"Leader de la formation en Data Science","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/datascientest.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"fr-FR"},{"@type":"Person","@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1","name":"Raphael Kassel","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/datascientest.com\/#\/schema\/person\/image\/","url":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","contentUrl":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","caption":"Raphael Kassel"},"description":"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \"Chef de projet IA\" et \"Data Product Manager\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.","sameAs":["https:\/\/www.linkedin.com\/in\/raphaelkassel\/","Data Science"],"url":"https:\/\/datascientest.com\/author\/raphaelkassel"}]}},"_links":{"self":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/218174"}],"collection":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/comments?post=218174"}],"version-history":[{"count":0,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/218174\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media\/218177"}],"wp:attachment":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media?parent=218174"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/categories?post=218174"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/tags?post=218174"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}