{"id":122,"date":"2009-07-13T15:56:01","date_gmt":"2009-07-13T13:56:01","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/13\/graph-particulier\/"},"modified":"2009-07-13T15:56:01","modified_gmt":"2009-07-13T13:56:01","slug":"graph-particulier","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=122","title":{"rendered":"Graph Particulier"},"content":{"rendered":"

\nGraph Sym\u00e9trique<\/strong>\n– Si pour toute paire de sommets (x,y) $\\in$ X il existe autant d’arcs de la forme (x,y) que de la forme (y,x)<\/p>\n

\"graph1-3.png\"<\/p>\n

– Cas du 1-Graphe G=(X,U), il est sym\u00e9trique ssi :\n (x,y) $\\in$ U (y,x) $\\in$ U<\/p>\n

\"graph2-3.png\"<\/p>\n

Graph Anti-Sym\u00e9trique<\/strong>\n– Si pour toute paire de sommets (x,y) C $\\in$ X il n’existe pas autant d’arcs de la forme (x,y) que de la forme (y,x) Le graphe G est dit anti-sym\u00e9trique\n– Cas du 1-graphe G=(X,U) il est anti-sym\u00e9trique ssi :<\/p>\n

(x,y) $\\in$ U $\\Rightarrow $ (y,x) $\\in$ U<\/p>\n

Graph complet<\/strong><\/p>\n

– Un graghe G est complet si:\n
$m_G<\/em>$ (x,y) = $m^+<\/em>_G<\/em>$(x,y)+$m^–<\/em>_G<\/em>$(x,y) $\\geq$ 1 pour tout x,y $\\in$ X avec x $\\neq$ y\n– Si G est un 1-graphe il est complet ssi : (x,y) $\\notin$ U $\\Rightarrow$ (y,x) $\\in$ U<\/p>\n

\"graph3-3.png\"<\/p>\n

Les arbres :<\/h2>\n

DEFINITION:<\/strong>\nGraphe connexe sans cycle\n
Soit n sommets(n>=2) on obtient un arbre en joignant les n sommets sans former de cycle. Cet arbre a (n-1) ar\u00eates\nPreuve :<\/p>\n

    \n
  • vrai si n=2: arbre \u00e0 une ar\u00eate<\/li>\n
  • Supposons cela vrai pour (n = k-1) ar\u00eates:\n
      \n
    • arbre obtenu en connectant (k-1) sommets sans jamais former de cycle, (k-2) ar\u00eates<\/li>\n<\/ul>\n<\/li>\n
    • Ajoutons un keme sommet pour rendre le graphe connexe il suffit de relier le nouveau sommet \u00e0 l\u2019un des (k-1) sommets par une ar\u00eate\n
        \n
      • (k-2)+1=k-1 ar\u00eates<\/li>\n
      • (k-1)+1=k sommets<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n

        Un arbre est un graphe connexe sans circuit, donc en un seul morceau et sans \u00ab\u00a0boucle\u00a0\u00bb\n
        THEOREME:\n
        Soit H =(X,U) un graphe d \u2019ordre card(X)=n>=2\n
        Les propri\u00e9t\u00e9 suivantes caract\u00e9risent un arbre :<\/p>\n

          \n
        1. H est connexe et sans cycle<\/li>\n
        2. H est sans cycle et admet (n-1) ar\u00eates<\/li>\n
        3. H est connexe et admet (n-1) ar\u00eates<\/li>\n
        4. H est sans cycle et en ajoutant une ar\u00eate on cr\u00e9e un cycle et un seul<\/li>\n
        5. H est connexe et si on supprime une ar\u00eate qcq, il n \u2019est plus connexe.<\/li>\n
        6. Tout couple de sommets est reli\u00e9 par une cha\u00eene et une seule.<\/li>\n<\/ol>\n

          Arbre recouvrant minimal<\/h2>\n

          Algorithme de Kruskal<\/strong><\/p>\n

            \n
          1. Faire le liste des ar\u00eates par valuation croissante.<\/li>\n<\/ol>\n
              \n
            • S \u2019il existe des valeurs identiques ajouter une valeur \u03b5 \u00e0 la premi\u00e8re, 2\u03b5 \u00e0 la suivante. n \u03b5 \u00e0 la $n^eme<\/em>$. \u03b5 doit satisfaire la condition suivante : $n \\epsilon + v_i<\/em> \\leq v_i<\/em> +n$<\/li>\n<\/ul>\n
                \n
              1. Choisir l\u2019ar\u00eate de valeur minimale, puis successivement, au fur et mesure de la construction de l\u2019arbre, l\u2019ar\u00eate de valeur imm\u00e9diatement sup\u00e9rieure dans la liste mais sans former de cycle avec les ar\u00eates d\u00e9j\u00e0 retenues.<\/li>\n
              2. Arr\u00eat lorsque tous les sommets sont connect\u00e9s nombre d\u2019ar\u00eates=n-1<\/li>\n<\/ol>\n

                La complexit\u00e9 est en O(m log m).<\/p>\n

                donc plus m grandit, plus les temps de r\u00e9ponse seront \u00e9normes<\/p>\n

                \"graph4-2.png\"<\/p>\n\n\n\n\n\n\n\n\n\n\n
                Liste des ar\u00eates<\/caption>\n
                ab=13 <\/td>\nfa=7<\/td>\n<\/tr>\n
                be=5 <\/td>\nfc=11<\/td>\n<\/tr>\n
                bd=4 <\/td>\nga=5<\/td>\n<\/tr>\n
                ea=19<\/td>\n gf=7<\/td>\n<\/tr>\n
                ec=10 <\/td>\nhf=2<\/td>\n<\/tr>\n
                ed=5 <\/td>\nhg=9<\/td>\n<\/tr>\n
                cd=13 <\/td>\nhc=19<\/td>\n<\/tr>\n
                ca=23<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                \"graph5-2.png\"<\/p>\n\n\n\n\n\n\n\n\n\n\n
                Arbre couvrant mini<\/caption>\n
                hf=2<\/strong> <\/td>\nec=10<\/strong><\/td>\n<\/tr>\n
                bd=4<\/strong> <\/td>\nfc=11<\/strong><\/td>\n<\/tr>\n
                be=5<\/strong> <\/td>\nab=13<\/td>\n<\/tr>\n
                ed=5,(1) <\/td>\ncd=13,(1)<\/td>\n<\/tr>\n
                ga=5<\/strong>,(2)<\/td>\n<\/td>\n<\/tr>\n
                gf=7<\/strong><\/td>\n hc=19<\/td>\n<\/tr>\n
                fa=7,(1) <\/td>\nea=19,(1)<\/td>\n<\/tr>\n
                hg=9<\/td>\n ca=23<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                Algorithme de Sollin<\/strong><\/p>\n

                je prends le premier A \n
                Quel est l’arr\u00eate qui va vers A qui coute le moins cher ?\n
                F=3\n
                mon paquet devient $\\$A, F$\\<\/em>$\n
                Le point suivant c\u2019est B, le moins cher est $\\$B,E$\\<\/em>$ un $2^eme<\/em>$ paquet\n
                Le point suivant est C, le moins cher est $\\$C,B$\\<\/em>$, le $2^eme<\/em>$ paquet devient $\\$C,B,E$\\<\/em>$\n
                Le point suivant D, le moins cher est $\\$D,G$\\<\/em>$, le $3^eme<\/em>$ paquet $\\$D,G$\\<\/em>$\n
                On recommence avec les 3 paquets $\\$A,F$\\<\/em>$, $\\$C,B,E$\\<\/em>$ et $\\$D,G$\\<\/em>$<\/p>\n

                \"graph6-2.png\"<\/p>\n

                $c_1<\/em>$=$\\$A$\\<\/em>$;$c_2<\/em>$=$\\$B$\\<\/em>$; $c_3<\/em>$=$\\$C$\\<\/em>$; $c_4<\/em>$=$\\$D$\\<\/em>$; $c_5<\/em>$=$\\$E$\\<\/em>$; $c_6<\/em>$=$\\$F$\\<\/em>$; $c_7<\/em>$=$\\$G$\\<\/em>$;<\/p>\n

                $c_1<\/em>$ non marqu\u00e9, $v_1j<\/em>$=min($c_1<\/em>$,j)=[A,F]marquer $c_1<\/em>$ et $c_6<\/em>$\n
                $c_2<\/em>$ non marqu\u00e9, $v_2j<\/em>$=min($c_2<\/em>$,j)=[B,E]marquer $c_2<\/em>$ et $c_5<\/em>$\n
                $c_3<\/em>$ non marqu\u00e9, $v_3j<\/em>$=min($c_3<\/em>$,j)=[C,B]marquer $c_3<\/em>$et $c_5<\/em>$\n
                $c_4<\/em>$ non marqu\u00e9, $v_4j<\/em>$=min($c_4<\/em>$,j)=[D,G]marquer $c_4<\/em>$et $c_7<\/em>$\n
                Tous les $c_i<\/em>$ sont marqu\u00e9s,\n
                $U_1<\/em>$= [A,F], [B,E], [C,B], [D,G]<\/em> —> \u00e9tape 2<\/p>\n

                \"graph7-2.png\"<\/p>\n

                Sous-arbres :\n
                $c_1<\/em>$=$\\$A,F$\\<\/em>$, $c_2<\/em>$=$\\$B,C,E$\\<\/em>$, $c_3<\/em>$=$\\$G,D$\\<\/em>$,\n
                $c_1<\/em>$ non marqu\u00e9, $v_1,j<\/em>$ =min ($c_3<\/em>$,j)=[B,F]marquer $c_1<\/em>$ et $c_2<\/em>$\n
                $c_3<\/em>$ non marqu\u00e9, $v_1,j<\/em>$ =min ($c_3<\/em>$,j)=[G,F]marquer $c_3<\/em>$ et $c_1<\/em>$<\/p>\n

                \"graph8-2.png\"<\/p>\n

                Sous-arbres :<\/strong>\n
                $c_1<\/em>$=$\\$A,F$\\<\/em>$, $c_2<\/em>$=$\\$B,C,E$\\<\/em>$, $c_3<\/em>$=$\\$G,D$\\<\/em>$,\n
                $c_1<\/em>$ non marqu\u00e9, $v_1,j<\/em>$ =min ($c_1<\/em>$,j)=[B,F]marquer $c_1<\/em>$ et $c_2<\/em>$\n
                $c_3<\/em>$ non marqu\u00e9, $v_1,j<\/em>$ =min ($c_3<\/em>$,j)=[G,F]marquer $c_3<\/em>$ et $c_1<\/em>$\n
                Tous les ci sont marqu\u00e9s\n
                $U_2<\/em>$=$\\$U1, [B,F] ,[G,F]$\\<\/em>$<\/p>\n

                \"graph9-2.png\"<\/p>\n

                On obtient l \u2019arbre recouvrant A qui est minimal $\\lambda$(A)=16<\/p>\n

                <\/math><\/p>\n","protected":false},"excerpt":{"rendered":"

                Graph Sym\u00e9trique – Si pour toute paire de sommets (x,y) $\\in$ X il existe autant d’arcs de la forme (x,y) que de la forme (y,x) – Cas du 1-Graphe G=(X,U), il est sym\u00e9trique ssi : (x,y) $\\in$ U (y,x) $\\in$ U Graph Anti-Sym\u00e9trique – Si pour toute paire de sommets (x,y) C $\\in$ X il […]<\/p>\n","protected":false},"author":2,"featured_media":113,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-122","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\/122","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=122"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/113"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}