{"id":213,"date":"2020-08-24T22:59:02","date_gmt":"2020-08-24T20:59:02","guid":{"rendered":"http:\/\/maths-code.fr\/cours\/?p=213"},"modified":"2020-08-24T22:59:02","modified_gmt":"2020-08-24T20:59:02","slug":"graphes","status":"publish","type":"post","link":"https:\/\/maths-code.fr\/cours\/2020\/08\/24\/graphes\/","title":{"rendered":"graphes"},"content":{"rendered":"

Les graphes sont utilis\u00e9s dans de nombreux domaines: les r\u00e9seaux de t\u00e9l\u00e9communications, les bases de donn\u00e9es relationnelles, les circuits \u00e9lectriques.
\nHistoriquement, on consid\u00e8re g\u00e9n\u00e9ralement que la th\u00e9orie des graphes a eu comme point de d\u00e9part le c\u00e9l\u00e8bre probl\u00e8me des ponts de K\u00f6nigsberg, r\u00e9solu en 1736 par L\u00e9onhard EULER (1707-1783).
\nVoici un \u00e9nonc\u00e9 du probl\u00e8me des ponts de K\u00f6nigsberg, ville situ\u00e9 \u00e0 l’\u00e9poque en Russie :
\n\u00ab Est-il possible de partir d\u2019un endroit de la ville de K\u00f6nigsberg et d\u2019y revenir apr\u00e8s avoir fait une promenade empruntant une fois et une seule chacun des sept ponts de la ville ? \u00bb
\nEuler mod\u00e9lisa cette situation par un graphe.<\/p>\n

Un autre probl\u00e9me connu est celui du fermier devant faire passer une ch\u00e8vre, un loup et un chou sur l’autre rive d’un fleuve, ne pouvant charger qu’un passager \u00e0 la fois, et ne pouvant laisser sur une m\u00eame rive le loup et la ch\u00e8vre ou la ch\u00e8vre et le chou.<\/p>\n

\"\"<\/p>\n

Nous allons \u00e9crire la structure de donn\u00e9e Graphe et donner les algorithmes usuels comme les parcours en profondeur ou en largeur.<\/p>\n","protected":false},"excerpt":{"rendered":"

Les graphes sont utilis\u00e9s dans de nombreux domaines: les r\u00e9seaux de t\u00e9l\u00e9communications, les bases de donn\u00e9es relationnelles, les circuits \u00e9lectriques. Historiquement, on consid\u00e8re g\u00e9n\u00e9ralement que la th\u00e9orie des graphes a eu comme point de d\u00e9part le c\u00e9l\u00e8bre probl\u00e8me des ponts de K\u00f6nigsberg, r\u00e9solu en 1736 par L\u00e9onhard EULER (1707-1783). Voici un \u00e9nonc\u00e9 du probl\u00e8me des ponts de K\u00f6nigsberg, ville situ\u00e9 \u00e0 l’\u00e9poque en Russie : \u00ab Est-il possible de partir d\u2019un endroit de la ville de K\u00f6nigsberg et d\u2019y revenir apr\u00e8s avoir fait une promenade empruntant une fois et une seule chacun des sept ponts de la ville ? \u00bb Euler mod\u00e9lisa cette situation par un graphe. Un autre probl\u00e9me connu est celui du fermier devant faire passer une ch\u00e8vre, un loup et un chou sur l’autre rive d’un fleuve, ne pouvant charger qu’un passager \u00e0 la fois, et ne pouvant laisser sur une m\u00eame rive le loup et la ch\u00e8vre ou la ch\u00e8vre et le chou. Nous allons \u00e9crire la structure de donn\u00e9e Graphe et donner les algorithmes usuels comme les parcours en profondeur ou en largeur.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-213","post","type-post","status-publish","format-standard","hentry","category-non-classe"],"acf":[],"_links":{"self":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/posts\/213","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/comments?post=213"}],"version-history":[{"count":2,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/posts\/213\/revisions"}],"predecessor-version":[{"id":379,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/posts\/213\/revisions\/379"}],"wp:attachment":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/media?parent=213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/categories?post=213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/tags?post=213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}