{"id":108,"date":"2009-07-08T11:13:43","date_gmt":"2009-07-08T09:13:43","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/08\/generalites-sur-les-graphes\/"},"modified":"2009-07-08T11:13:43","modified_gmt":"2009-07-08T09:13:43","slug":"generalites-sur-les-graphes","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=108","title":{"rendered":"G\u00e9n\u00e9ralit\u00e9s sur les graphes"},"content":{"rendered":"

La th\u00e9orie des graphes :<\/h2>\n

Un graphe est compos\u00e9 de sommets (on parle aussi de noeuds) et d\u2019arcs qui relient les sommets entre eux. La forme n\u2019a pas d\u2019importance mais en g\u00e9n\u00e9ral on le lit de gauche \u00e0 droite, parfois de haut en bas, car ce sont des sens naturels.<\/p>\n

On appelle un graphe G(X,U) avec X= ensemble de sommets et U = ensembles d\u2019arcs.<\/p>\n

Graphe non orient\u00e9<\/strong><\/p>\n

– Orientation des arcs : pas d \u2019importance (plan de circulation sans sens interdits)
\n– Extr\u00e9mit\u00e9 initiale et terminale: aucun r\u00f4le
\n– Int\u00e9resse \u00e0 l \u2019existence ou non d \u2019un ou plusieurs arcs entre deux sommets.
\n– A tout arc (xi,xj) , \u00e0 tout couple de sommets ordonn\u00e9s (xi,xj) on associe un couple non ordonn\u00e9 (xi,xj) appel\u00e9e ar\u00eate<\/p>\n

\"graph1\"
graph1<\/strong><\/figcaption><\/figure>\n

L\u2019ordre des liaisons n\u2019a pasd\u2019importance, on regarde justel\u2019existence d\u2019un lien entre deuxsommets. Donc approche binaire : le lien existe ou pas. Mais ce lien n\u2019a pas de sens.<\/p>\n

Vocabulaire :<\/em>
\nOrdre d\u2019un graphe<\/em> : nombre de sommet de ce graphe. Un graphe avec 5 sommets est un graphe d\u2019ordre 5.
\n
X-graphe<\/em> : nombre maximal de liens entre deux sommets.<\/p>\n

On appelle multigraphe un graphe pour lequel il existe plusieurs ar\u00eates entre deux sommets xi,x<\/p>\n

    \n
  • Un multigraphe est un graphe simple si :\n
      \n
    • absence de boucle<\/li>\n
    • un arc, max, entre deux sommets<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n
      \"graph2\"
      graph2<\/strong><\/figcaption><\/figure>\n

      Entre X1 et X3 il y a 4 liens et au total il y a 5 sommets. On parle donc de 4-graphe d\u2019ordre 5.
      \n
      Attention<\/strong> : le graphe est en deux parties.
      \n
      U7 et U8 font partie du m\u00eame graphe.
      \n
      Quelques trucs importants :<\/strong>
      \n
      Successeurs et pr\u00e9d\u00e9cesseurs \u00e0 un sommet : les successeurs sont les sommets qui partent d\u2019un sommet ; les pr\u00e9d\u00e9cesseurs sont les sommets qui
      \narrivent \u00e0 un autre sommet.<\/p>\n

      Matrice associ\u00e9 \u00e0 un graph<\/h2>\n

      Un graphe peut se repr\u00e9senter sous la forme graphique (le dessin du graphe). Mais quand vous en utilisez, faites des calculs ou autre, on a besoin de la forme matricielle.
      \n
      Il y a trois fa\u00e7ons de repr\u00e9senter un graphe par une matrice<\/em> :<\/p>\n

      Matrice d \u2019incidence sommets-sommets<\/strong><\/p>\n

      \"graph3\"
      graph3<\/strong><\/figcaption><\/figure>\n

      On regarde le nombre de sommets. Si on a 4 sommets, on fait une matrice 4×4. La ligne 1 correspond au sommet 1, la ligne 2 au sommet 2, \u2026. Mais aussi, la colonne 1 correspond au sommet 1, la colonne 2 au sommet 2, \u2026 Ensuite on fait un remplissage binaire simple. Par exemple, s\u2019il existe un lien entre le sommet 3 et le sommet 4, on met 1 dans la ligne 3 et la colonne 4 de
      \nla matrice.<\/p>\n

      matrice d \u2019incidence sommets-arcs<\/strong><\/p>\n

      \"graph4\"
      graph4<\/strong><\/figcaption><\/figure>\n

      Mettre en ligne les sommets et en colonne les arcs. Exemple: il existe un arc U3 qui part de X2, on met donc 1 entre U3 et X2. Les autres valeurs possibles sont -1 qui signifie que l\u2019arc arrive et 0, pas d\u2019arc entre les deux.<\/p>\n

      Matrice d \u2019incidence sommets-ar\u00eates<\/strong><\/p>\n

      \"graph5\"
      graph5<\/strong><\/figcaption><\/figure>\n

      Mettre en ligne les sommets et en colonne les arr\u00eates. Dans cette matrice on ne prend pas en compte l\u2019orientation des arcs.<\/p>\n

      chaine et de chemin.<\/h2>\n

      – Cha\u00eene \u00e9l\u00e9mentaire<\/em> : On ne rencontre pas deux fois le m\u00eame sommet en la parcourant.
      \n– Cha\u00eene simple<\/em> : On ne rencontre pas deux fois le m\u00eame arc en la parcourant.
      \n– Chemin<\/em> : C\u2019est une s\u00e9quence de q arcs dont les arcs sont orient\u00e9s dans le m\u00eame sens.Pour tout arc ui (i < q ) l\u2019extr\u00e9mit\u00e9 terminale de ui co\u00efncide avec l\u2019extr\u00e9mit\u00e9 initiale ui+1.\n- Chemin \u00e9l\u00e9mentaire<\/em> : Les sommets de degr\u00e9 2 au plus
      \n– Chemins hamiltoniens<\/em> : Dans un graphe G=(X,U), on dit qu\u2019un chemin m=[x1,x2,\u2026,xn] est hamiltonien s \u2019il passe une fois et une seule par chaque sommet du graphe. C\u2019est un chemin \u00e9l\u00e9mentaire de longueur (N-1). C\u2019est le probl\u00e8me du voyageur de commerce : il doit relier plusieurs points en partant de chez lui.
      \n– La connexit\u00e9<\/em> : un graphe G(X,U) est connexe si pour tout couple de sommets (x,y) il existe une chaine joignant x \u00e0 y. Un graphe G(X,U) est fortement connexe si pour tout couple de sommets (x,y) il existe un chemin joignant x \u00e0 y et un chemin joignant y \u00e0 x. La connexit\u00e9 signifie qu\u2019on peut relier tous les
      \npoints deux \u00e0 deux.<\/p>\n

      Graphe d\u2019ordre 4 et matrice de ce graphe.<\/strong><\/p>\n

      Chemin de longueur k<\/em> : On appelle longueur d\u2019un chemin, entre deux sommets, i et j appartenant \u00e0 X, sur un graphe G=(X,U), le nombre d\u2019arcs existant entre ces deux sommets.
      \nUn chemin est de longueur, k, s\u2019il comprend k arcs et (k+1) sommets.
      \nUn sommet seul, d\u00e9termine un chemin de longueur 0.<\/p>\n

      \"graph6\"
      graph6<\/strong><\/figcaption><\/figure>\n

      Si on calcule M\u00b2 (MxM), on obtient la matrice de tous les chemins de longueur 2, On a 1 entre A et C car on peut aller de A \u00e0 C en faisant A-B et B-C (chemin de longueur 2 => 2 arcs). Si on fait M3, on obtient tous les chemins de longueur 3, et ainsi de suite (M4, M5,\u2026).
      \n
      Si un graphe comporte N sommets, le chemin le plus long fera N-1. Exemple : pour relier 4 sommets, la longueur maximale du chemin sera 3.<\/p>\n

      \"graph7\"
      graph7<\/strong><\/figcaption><\/figure>\n

      Graphe d\u2019ordre 4, on calcule M+M\u00b2+M3, on obtient tous les chemins possibles de toutes les longueurs entre les sommets.<\/p>\n

      Fermeture transitive<\/h2>\n

      On appelle fermeture transitive d’un graphe la liste des chemins \u00e9tablis \u00e0 partir de la propri\u00e9t\u00e9 de transitivit\u00e9.<\/p>\n

      La fermeture transitive s\u2019obtient en faisant la somme bool\u00e9enne de la matrice unit\u00e9 et des puissances successives de la matrice d\u2019adjacence sommets sommets, M.<\/p>\n

      \"graph8\"
      graph8<\/strong><\/figcaption><\/figure>
      \n
      \"graph9\"
      graph9<\/strong><\/figcaption><\/figure>
      \nLa matrice M repr\u00e9sente tous les chemins existant entre toute paire de sommets xi,xj<\/em>.<\/p>\n","protected":false},"excerpt":{"rendered":"

      La th\u00e9orie des graphes : Un graphe est compos\u00e9 de sommets (on parle aussi de noeuds) et d\u2019arcs qui relient les sommets entre eux. La forme n\u2019a pas d\u2019importance mais en g\u00e9n\u00e9ral on le lit de gauche \u00e0 droite, parfois de haut en bas, car ce sont des sens naturels. On appelle un graphe G(X,U) […]<\/p>\n","protected":false},"author":2,"featured_media":99,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-108","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-rcp101-recherche-operationnelle-et-aide-a-la-decision"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=108"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/108\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/99"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}