{"id":2204,"date":"2016-02-15T17:41:01","date_gmt":"2016-02-15T16:41:01","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2204"},"modified":"2024-02-11T21:27:56","modified_gmt":"2024-02-11T20:27:56","slug":"theorie-des-graphes","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/","title":{"rendered":"Teor\u00eda de grafos 101"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"2204\" class=\"elementor elementor-2204\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f688a80 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f688a80\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-b05af82\" data-id=\"b05af82\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c53adc0 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c53adc0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/2020\/04\/03\/theories-et-algorithmes\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Th\u00e9ories<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\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<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-f76292c\" data-id=\"f76292c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b3ced38 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b3ced38\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\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<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-b708349\" data-id=\"b708349\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f27db8f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f27db8f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9orie_des_graphes\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\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<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6c61a75 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6c61a75\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1670072\" data-id=\"1670072\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f9bbc18 elementor-widget elementor-widget-toggle\" data-id=\"f9bbc18\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2611\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2611\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Th\u00e9orie des Graphes (Familles)<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2611\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2611\"><ul>\n<li><a href=\"http:\/\/www.or.uni-bonn.de\/~hougardy\/paper\/ClassesOfPerfectGraphs.pdf\" target=\"_blank\" rel=\"noopener\">Graphes parfaits<\/a><\/li>\n<li><a href=\"https:\/\/www.researchgate.net\/publication\/307630901_What_Are_Graph_Amalgamations#read\" target=\"_blank\" rel=\"noopener\">Amalgamation de graphes<\/a><\/li>\n<li><a href=\"https:\/\/mathworld.wolfram.com\/RegularGraph.html\" target=\"_blank\" rel=\"noopener\">Graphe r\u00e9gulier<\/a><\/li>\n<li><a href=\"https:\/\/mathworld.wolfram.com\/CageGraph.html\" target=\"_blank\" rel=\"noopener\">Cage<\/a><\/li>\n<li><a href=\"https:\/\/www.geeksforgeeks.org\/bipartite-graph\/\" target=\"_blank\" rel=\"noopener\">Graphe biparti<\/a><\/li>\n<li><a href=\"https:\/\/bearworks.missouristate.edu\/cgi\/viewcontent.cgi?article=4137&amp;context=theses\" target=\"_blank\" rel=\"noopener\">Graphe de Cayley<\/a><\/li>\n<li><a href=\"https:\/\/iq.opengenus.org\/clique-in-graphs\/\" target=\"_blank\" rel=\"noopener\">Clique<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Complement_graph\" target=\"_blank\" rel=\"noopener\">Graphe compl\u00e9mentaire<\/a><\/li>\n<li><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000016300502\" target=\"_blank\" rel=\"noopener\">Graphe de Bruijin<\/a><\/li>\n<li><a href=\"https:\/\/www.baeldung.com\/cs\/graphs-sparse-vs-dense\" target=\"_blank\" rel=\"noopener\">Densit\u00e9 des graphes (Graphes denses et Graphes creux)<\/a><\/li>\n<li><a href=\"https:\/\/www.polymtl.ca\/pub\/sites\/lagrapheur\/docs\/en\/documents\/NotesChap3.pdf\" target=\"_blank\" rel=\"noopener\">Graphe d&rsquo;intervalles<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Circle_graph\" target=\"_blank\" rel=\"noopener\">Graphe en cercle<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Line_graph\" target=\"_blank\" rel=\"noopener\">Graphe line<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Petersen_graph\" target=\"_blank\" rel=\"noopener\">Graphe de Petersen<\/a><\/li>\n<li><a href=\"http:\/\/monge.univ-mlv.fr\/~goaoc\/lec1.pdf\" target=\"_blank\" rel=\"noopener\">Graphe planaire<\/a><\/li>\n<li><a href=\"https:\/\/www.math.cmu.edu\/~af1p\/BOOK.pdf\" target=\"_blank\" rel=\"noopener\">Graphe al\u00e9atoire<\/a><\/li>\n<li><a href=\"https:\/\/projecteuclid.org\/x429.xml?aspxerrorpath=\/journalArticle\/Download\" target=\"_blank\" rel=\"noopener\">Graphe \u00e0 invariance d&rsquo;\u00e9chelle<\/a><\/li>\n<li><a href=\"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/EA9BC5B22B4ABD72CB6C7C797F51864B\/S1446788700023077a.pdf\/almost_all_chordal_graphs_split.pdf\" target=\"_blank\" rel=\"noopener\">Graphe cordal ou split\u00e9<\/a><\/li>\n<li><a href=\"http:\/\/www.numdam.org\/article\/AIHP_1949__11_5_227_0.pdf\" target=\"_blank\" rel=\"noopener\">Treillis<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2612\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-2612\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Arbres et arborescence<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2612\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-2612\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/theorie-des-graphes\/arbres-et-arborescences\/\">Arbre et arborescences<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/theorie-des-graphes\/arbres-couvrants\/\">Arbres couvrants<\/a><\/li>\n<li><a href=\"https:\/\/webusers.imj-prg.fr\/~paul.laurain\/Steiner.pdf\" target=\"_blank\" rel=\"noopener\">Arbres de Steiner<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2613\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-2613\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Coloration, clique et stable<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2613\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-2613\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/theorie-des-graphes\/coloration-cliques-et-stables\/\">Coloriage, cliques et stables<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/theorie-des-graphes\/theoreme-des-quatre-couleurs\/\">Th\u00e9or\u00e8me des Quatre Couleurs<\/a><\/li>\n<li><a href=\"https:\/\/web.math.princeton.edu\/~pds\/papers\/hadwiger\/paper.pdf\" target=\"_blank\" rel=\"noopener\">Conjecture de Hadwiger (en)<\/a><\/li>\n<li><a href=\"https:\/\/www.groundai.com\/project\/on-erdos-faber-lovasz-conjecture\/1\" target=\"_blank\" rel=\"noopener\">Conjecture de Erd\u00f6s &#8211; Faber &#8211; Lov\u00e1sz (en)<\/a><\/li>\n<li><a href=\"http:\/\/www.openproblemgarden.org\/op\/behzads_conjecture\" target=\"_blank\" rel=\"noopener\">Conjecture de Behzad (en)<\/a><\/li>\n<li><a href=\"https:\/\/www.math.cmu.edu\/~mradclif\/teaching\/228F16\/Kuratowski.pdf\" target=\"_blank\" rel=\"noopener\">Graphe planaire et Th\u00e9or\u00e8me de Kuratowski (en)<\/a><\/li>\n<li><a href=\"https:\/\/www.personal.kent.edu\/~rmuhamma\/GraphTheory\/MyGraphTheory\/planarity.htm\" target=\"_blank\" rel=\"noopener\">Graphe planaire et Th\u00e9or\u00e8me de Wagner (en)<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2614\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-2614\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Cheminement<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2614\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-2614\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/theorie-des-graphes\/parcours-de-graphes\/\">Parcours d&rsquo;arbres<\/a><\/li>\n<li><a href=\"http:\/\/www.cs.kent.edu\/~dragan\/ST-Spring2016\/The%20Seven%20Bridges%20of%20Konigsberg-Euler&#039;s%20solution.pdf\" target=\"_blank\" rel=\"noopener\">Les sept ponts de K\u00f6nigsburg (en)<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/theorie-des-graphes\/hamiltonien-et-eulerien\/\">Hamiltonien et Eulerien<\/a><\/li>\n<li><a href=\"http:\/\/www.suffolkmaths.co.uk\/pages\/Maths%20Projects\/Projects\/Topology%20and%20Graph%20Theory\/Chinese%20Postman%20Problem.pdf\" target=\"_blank\" rel=\"noopener\">Probl\u00e8me du postier chinois (en)<\/a><\/li>\n<li><a href=\"https:\/\/www.nctm.org\/classroomresources\/\" target=\"_blank\" rel=\"noopener\">Enigme des trois maisons (en)<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2615\" class=\"elementor-tab-title\" data-tab=\"5\" role=\"button\" aria-controls=\"elementor-tab-content-2615\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">V. Analyse des r\u00e9seaux<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2615\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"5\" role=\"region\" aria-labelledby=\"elementor-tab-title-2615\"><ul>\n<li><a title=\"Centrality\" href=\"https:\/\/en.wikipedia.org\/wiki\/Centrality\" target=\"_blank\" rel=\"noopener\">Centrality<\/a><\/li>\n<li><a title=\"Degree (graph theory)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Degree_(graph_theory)\" target=\"_blank\" rel=\"noopener\">Degree<\/a><\/li>\n<li><a title=\"Network motif\" href=\"https:\/\/en.wikipedia.org\/wiki\/Network_motif\" target=\"_blank\" rel=\"noopener\">Motif<\/a><\/li>\n<li><a title=\"Clustering coefficient\" href=\"https:\/\/en.wikipedia.org\/wiki\/Clustering_coefficient\" target=\"_blank\" rel=\"noopener\">Clustering<\/a><\/li>\n<li><a title=\"Degree distribution\" href=\"https:\/\/en.wikipedia.org\/wiki\/Degree_distribution\" target=\"_blank\" rel=\"noopener\">Degree distribution<\/a><\/li>\n<li><a title=\"Assortativity\" href=\"https:\/\/en.wikipedia.org\/wiki\/Assortativity\" target=\"_blank\" rel=\"noopener\">Assortativity<\/a><\/li>\n<li><a title=\"Distance (graph theory)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Distance_(graph_theory)\" target=\"_blank\" rel=\"noopener\">Distance<\/a><\/li>\n<li><a title=\"Modularity (networks)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Modularity_(networks)\" target=\"_blank\" rel=\"noopener\">Modularity<\/a><\/li>\n<li><a title=\"Efficiency (network science)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Efficiency_(network_science)\" target=\"_blank\" rel=\"noopener\">Efficiency<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2616\" class=\"elementor-tab-title\" data-tab=\"6\" role=\"button\" aria-controls=\"elementor-tab-content-2616\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">VI. Topologie<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2616\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"6\" role=\"region\" aria-labelledby=\"elementor-tab-title-2616\"><ul>\n<li><a title=\"Random graph\" href=\"https:\/\/en.wikipedia.org\/wiki\/Random_graph\" target=\"_blank\" rel=\"noopener\">Random graph<\/a><\/li>\n<li><a title=\"Erd\u0151s\u2013R\u00e9nyi model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Erd%C5%91s%E2%80%93R%C3%A9nyi_model\" target=\"_blank\" rel=\"noopener\">Erd\u0151s\u2013R\u00e9nyi<\/a><\/li>\n<li><a title=\"Barab\u00e1si\u2013Albert model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Barab%C3%A1si%E2%80%93Albert_model\" target=\"_blank\" rel=\"noopener\">Barab\u00e1si\u2013Albert<\/a><\/li>\n<li><a title=\"Bianconi\u2013Barab\u00e1si model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Bianconi%E2%80%93Barab%C3%A1si_model\" target=\"_blank\" rel=\"noopener\">Bianconi\u2013Barab\u00e1si<\/a><\/li>\n<li><a title=\"Fitness model (network theory)\" href=\"https:\/\/en.wikipedia.org\/wiki\/Fitness_model_(network_theory)\" target=\"_blank\" rel=\"noopener\">Fitness model<\/a><\/li>\n<li><a title=\"Watts\u2013Strogatz model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Watts%E2%80%93Strogatz_model\" target=\"_blank\" rel=\"noopener\">Watts\u2013Strogatz<\/a><\/li>\n<li><a class=\"mw-redirect\" title=\"Exponential random graph models\" href=\"https:\/\/en.wikipedia.org\/wiki\/Exponential_random_graph_models\" target=\"_blank\" rel=\"noopener\">Exponential random (ERGM)<\/a><\/li>\n<li><a title=\"Random geometric graph\" href=\"https:\/\/en.wikipedia.org\/wiki\/Random_geometric_graph\" target=\"_blank\" rel=\"noopener\">Random geometric (RGG)<\/a><\/li>\n<li><a title=\"Hyperbolic geometric graph\" href=\"https:\/\/en.wikipedia.org\/wiki\/Hyperbolic_geometric_graph\" target=\"_blank\" rel=\"noopener\">Hyperbolic (HGN)<\/a><\/li>\n<li><a title=\"Hierarchical network model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Hierarchical_network_model\" target=\"_blank\" rel=\"noopener\">Hierarchical<\/a><\/li>\n<li><a title=\"Stochastic block model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Stochastic_block_model\" target=\"_blank\" rel=\"noopener\">Stochastic block<\/a><\/li>\n<li><a title=\"Blockmodeling\" href=\"https:\/\/en.wikipedia.org\/wiki\/Blockmodeling\" target=\"_blank\" rel=\"noopener\">Blockmodeling<\/a><\/li>\n<li><a title=\"Maximum-entropy random graph model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Maximum-entropy_random_graph_model\" target=\"_blank\" rel=\"noopener\">Maximum entropy<\/a><\/li>\n<li><a title=\"Soft configuration model\" href=\"https:\/\/en.wikipedia.org\/wiki\/Soft_configuration_model\" target=\"_blank\" rel=\"noopener\">Soft configuration<\/a><\/li>\n<li><a title=\"Lancichinetti\u2013Fortunato\u2013Radicchi benchmark\" href=\"https:\/\/en.wikipedia.org\/wiki\/Lancichinetti%E2%80%93Fortunato%E2%80%93Radicchi_benchmark\" target=\"_blank\" rel=\"noopener\">LFR Benchmark<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1d099c5a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1d099c5a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2c8cffc0\" data-id=\"2c8cffc0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-99af677 elementor-widget elementor-widget-text-editor\" data-id=\"99af677\" data-element_type=\"widget\" data-e-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\t\t<p><\/p>\n<p><\/p>\n<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Alternar tabla de contenidos\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/#Theorie-des-graphes\" >Th\u00e9orie des graphes<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/#Representation-informatique\" >Repr\u00e9sentation informatique<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/#Cheminements\" >Cheminements<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Theorie-des-graphes\"><\/span>Th\u00e9orie des graphes<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p>En th\u00e9orie des graphes, un graphe <strong>G<\/strong> est d\u00e9fini par un couple (S,A) avec <strong>S<\/strong> un ensemble fini de sommets, et <strong>A<\/strong> un ensemble fini de couple de sommets (s<sub>i<\/sub>, s<sub>j<\/sub>) dans S\u00b2.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Dans un graphe orient\u00e9, les couples (s<sub>i<\/sub>,s<sub>j<\/sub>) de <strong>A<\/strong> sont orient\u00e9s, c&rsquo;est-\u00e0-dire que s<sub>i<\/sub> est le sommet initial et s<sub>j<\/sub> le sommet terminal. Graphiquement, ce couple est un <strong>arc <\/strong>du sommet s<sub>i<\/sub> vers le sommet s<sub>j<\/sub>.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph1.png\" alt=\"th\u00e9orie des graphes\" width=\"281\" height=\"152\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>Dans un graphe non orient\u00e9, les couples (s<sub>i<\/sub>,s<sub>j<\/sub>) ne sont pas orient\u00e9s. Ainsi, (s<sub>i<\/sub>,s<sub>j<\/sub>) est \u00e9quivalent \u00e0 \u00e9crire (s<sub>j<\/sub>,s<sub>i<\/sub>). Graphiquement, ce couple est une <strong>ar\u00eate<\/strong> entre les sommets s<sub>i<\/sub> et s<sub>j<\/sub>.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph2.png\" alt=\"graphe\" width=\"127\" height=\"110\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>\u00c9l\u00e9ments de terminologie :<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>L&rsquo;<strong>ordre<\/strong> d&rsquo;un graphe est le nombre de ses sommets |S|.<\/li>\n<li>Une <strong>boucle<\/strong> est un arc ou une ar\u00eate (s<sub>i<\/sub>,s<sub>i<\/sub>).<\/li>\n<li>Un graphe non orient\u00e9 est dit <strong>simple<\/strong> s&rsquo;il ne contient pas de boucle et s&rsquo;il comporte au plus une ar\u00eate entre tout couple de sommets. Sinon il s&rsquo;agit d&rsquo;un multi-graphe.<\/li>\n<li>Un graphe orient\u00e9 est dit <strong>\u00e9l\u00e9mentaire<\/strong> s&rsquo;il ne contient pas de boucle.<\/li>\n<li>Un graphe orient\u00e9 est un <strong>p-graphe<\/strong> sil comporte au plus <em>p<\/em> arcs entre tout couple de sommets.<\/li>\n<li>Un graphe<strong> partiel<\/strong> d&rsquo;un graphe est le graphe obtenu en supprimant certains arcs (ou ar\u00eates).<\/li>\n<li>Un <strong>sous-graphe<\/strong> d&rsquo;un graphe est le graphe obtenu en supprimant certains sommets et tous les arcs incidents aux sommets supprim\u00e9s.<\/li>\n<li>Un graphe est dit <strong>complet<\/strong> s&rsquo;il poss\u00e8de une ar\u00eate (s<sub>i<\/sub>,s<sub>j<\/sub>) pour tout couple de sommets (ou deux arcs (s<sub>i<\/sub>,s<sub>j<\/sub>) et (s<sub>j<\/sub>,s<sub>i<\/sub>)). Un graphe simple complet \u00e0 n sommets aura n(n-1)\/2 ar\u00eates.<\/li>\n<li>Un <strong>attribut\u00a0<\/strong>peut \u00eatre associ\u00e9 \u00e0\u00a0(s<sub>i<\/sub>,s<sub>j<\/sub>). L&rsquo;attribut peut \u00eatre une lettre, un mot ou un poids (valeur num\u00e9rique). Un graphe avec des poids est appel\u00e9 <strong>R\u00e9seau<\/strong>.<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p>Consid\u00e9rons un graphe G = (V, E,w) avec une fonction de poids :<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/weightgraph.png\" alt=\"graphe\" width=\"719\" height=\"331\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>Notions d&rsquo;adjacence :<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Dans un graphe non orient\u00e9, un sommet s<sub>i<\/sub> est dit <strong>adjacent<\/strong> \u00e0 un sommet s<sub>j<\/sub> s&rsquo;il existe une ar\u00eate entre s<sub>i<\/sub> et s<sub>j<\/sub>. L&rsquo;ensemble des sommets adjacents \u00e0 un sommet s<sub>i<\/sub> est d\u00e9finit par :<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2241\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph3.png\" alt=\"graphe adjacence\" width=\"339\" height=\"31\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph3.png 339w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph3-300x27.png 300w\" sizes=\"(max-width: 339px) 100vw, 339px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Dans un graphe orient\u00e9, on distingue les sommets <strong>successeurs<\/strong> (terminaux d&rsquo;un arc) et <strong>pr\u00e9d\u00e9cesseurs<\/strong> (initiaux d&rsquo;un arc) :<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2245\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph4.png\" alt=\"graphe successeur pr\u00e9d\u00e9cesseur\" width=\"264\" height=\"55\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<p>Notions de degr\u00e9 d&rsquo;un sommet :<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Dans un graphe non orient\u00e9, le <strong>degr\u00e9<\/strong> d&rsquo;un sommet est le nombre d&rsquo;ar\u00eates incidentes \u00e0 ce sommet. Dans le cas d&rsquo;un graphe simple nous avons :<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2250\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph5.png\" alt=\"graphe degr\u00e9\" width=\"156\" height=\"23\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph5.png 156w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph5-150x23.png 150w\" sizes=\"(max-width: 156px) 100vw, 156px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Dans un graphe orient\u00e9, le <strong>demi-degr\u00e9 ext\u00e9rieur<\/strong> d&rsquo;un sommet est le nombre d&rsquo;arcs partant de ce sommet. Dans un 1-graphe nous avons :<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2254\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph6.png\" alt=\"graphe degr\u00e9 sortant\" width=\"165\" height=\"25\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Dans un graphe orient\u00e9, le <strong>demi-degr\u00e9 int\u00e9rieur<\/strong> d&rsquo;un sommet est le nombre d&rsquo;arcs arrivant de ce sommet. Dans un 1-graphe nous avons :<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2258\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph7.png\" alt=\"graphe degr\u00e9 entrant\" width=\"165\" height=\"23\" title=\"\"><\/figure>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Le nombre de sommets de degr\u00e9 impair est pair. La somme de tous les degr\u00e9s est \u00e9gale \u00e0 deux fois le nombre d&rsquo;ar\u00eates. Puisque la somme des degr\u00e9s est paire et que la somme des degr\u00e9s des sommets \u00e0 degr\u00e9 pair est paire, la somme des degr\u00e9s des sommets \u00e0 degr\u00e9 impair doit \u00eatre paire. Si la somme des degr\u00e9s de sommets avec degr\u00e9 impair est pair, il doit y avoir un nombre pair de ces sommets.<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Representation-informatique\"><\/span>Repr\u00e9sentation informatique<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Il existe deux mani\u00e8res \u00ab\u00a0acad\u00e9miques\u00a0\u00bb de repr\u00e9senter un graphe de fa\u00e7on informatique : soit par une matrice d&rsquo;adjacence, soit par des listes d&rsquo;adjacence.<\/p>\n<p><\/p>\n<p><\/p>\n<p>On suppose que les sommets de S sont num\u00e9rot\u00e9s de 1 \u00e0 <strong>n<\/strong>. La matrice d&rsquo;adjacence est une matrice <strong>M<\/strong> de taille n*n telle que M[i,j] = <strong>value<\/strong> si (i,j) dans A, M[i,j] = <strong>no value<\/strong> sinon. Dans le cadre de la pr\u00e9sence de lien entre le sommet i et j, <strong>value<\/strong> = 1 et <strong>no value<\/strong> = 0. Dans le cadre de lien valu\u00e9 entre le sommet i et j, <strong>value<\/strong> = pond\u00e9ration et <strong>no value<\/strong> = infini. Dans un cadre non-orient\u00e9, la matrice sera sym\u00e9trique du triangle sup\u00e9rieur droit. Ce type de codage demande O(|S|\u00b2) emplacements m\u00e9moire.<\/p>\n<p><\/p>\n<p><\/p>\n<p>La repr\u00e9sentation par listes d&rsquo;adjacences consiste en un tableau <strong>T<\/strong> de <strong>n<\/strong> listes, une pour chaque sommet de <strong>S<\/strong>. Une liste chain\u00e9e T[s<sub>i<\/sub>] contient tous les \u00e9l\u00e9ments s<sub>j<\/sub> de <strong>S<\/strong> tels qu&rsquo;il existe un lien (s<sub>i<\/sub>, s<sub>j<\/sub>) dans <strong>A<\/strong>. C&rsquo;est-\u00e0-dire la liste des successeurs de s<sub>i<\/sub>. Si le graphe est valu\u00e9, chaque maillon peut contenir des informations sur la pond\u00e9ration. Ce type de codage demande O(|S|+|A|) emplacements m\u00e9moire.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Chaque m\u00e9thode a des avantages comme des inconv\u00e9nients en fonction des op\u00e9rations que l&rsquo;on souhaite effectuer sur le graphe.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2283\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph8.png\" alt=\"graphe\" width=\"233\" height=\"493\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph8.png 233w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/graph8-142x300.png 142w\" sizes=\"(max-width: 233px) 100vw, 233px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Cheminements\"><\/span>Cheminements<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Dans un graphe orient\u00e9, un chemin d&rsquo;un sommet <strong>u<\/strong> vers un sommet <strong>v<\/strong> est une s\u00e9quence &lt;s<sub>0<\/sub>, s<sub>1<\/sub>, &#8230; , s<sub>k<\/sub>&gt; de sommets telle que u = s<sub>0<\/sub> et v = s<sub>k<\/sub>, et (s<sub>i<\/sub>, s<sub>(i+1)<\/sub>) est dans <strong>A<\/strong> pour <strong>i<\/strong> de 0 \u00e0 k-1. La longueur du chemin est le nombre d&rsquo;arcs dans le chemin, c&rsquo;est-\u00e0-dire <strong>k<\/strong>. S&rsquo;il existe un chemin de <strong>u<\/strong> \u00e0 <strong>v<\/strong>, on dira que <strong>v<\/strong> est accessible \u00e0 partir de <strong>u<\/strong>. Un chemin est \u00e9l\u00e9mentaire si les sommets qu&rsquo;il contient sont tous distincts. u est appel\u00e9 Start, v est appel\u00e9 End.<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Un chemin forme un circuit si s<sub>0<\/sub> = s<sub>k<\/sub> et si le chemin comporte au moins un arc. Ce circuit est \u00e9l\u00e9mentaire si le chemin &lt;s<sub>0<\/sub>, &#8230;, s<sub>(k-1)<\/sub>&gt; (le circuit sans le dernier sommet) est \u00e9l\u00e9mentaire. Une boucle est donc un circuit de longueur 1. Le graphe est dit acyclique s&rsquo;il ne poss\u00e8de aucun circuit.<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Un graphe orient\u00e9 est dit fortement connexe si chaque sommet est accessible \u00e0 partir de n&rsquo;importe quel autre : pour tout couple de sommets distincts il existe un chemin entre eux.<\/div>\n<p><\/p>\n<p><\/p>\n<p>Cela peut se calculer par fermeture transitive. Cette derni\u00e8re est la somme des <strong>n<\/strong> premi\u00e8res puissances de la matrice d&rsquo;adjacence, n=|A|. Le graphe est fortement connexe si toute la matrice comporte <strong>value<\/strong>. Une composante fortement connexe est un sous-graphe fortement connexe.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Les m\u00eames notions existent pour les graphes non orient\u00e9s sous le nom de chaine et de cycle. Le graphe est dit connexe et l&rsquo;on parle de composante connexe.<\/p>\n<p><\/p>\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<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Teor\u00edas P\u00e1gina de inicio de Wiki I. Teor\u00eda de grafos (Familias) Grafos perfectos Fusi\u00f3n de grafos Gr\u00e1fico de jaula regular Gr\u00e1fico bipartito Gr\u00e1fico de camarilla de Cayley Gr\u00e1fico complementario \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2204","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=2204"}],"version-history":[{"count":44,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204\/revisions"}],"predecessor-version":[{"id":20485,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204\/revisions\/20485"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=2204"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}