{"id":112,"date":"2009-07-09T12:10:06","date_gmt":"2009-07-09T10:10:06","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/09\/nombre-cyclomatique\/"},"modified":"2009-07-09T12:10:06","modified_gmt":"2009-07-09T10:10:06","slug":"nombre-cyclomatique","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=112","title":{"rendered":"Nombre cyclomatique"},"content":{"rendered":"

D\u00e9finition :<\/strong>
\n\nDans un graphe G=(X,U) un cycle est une s\u00e9quence d \u2019arcs :m=(u1,u2,u3,\u2026,uq) telle que :<\/p>\n

    \n
  1. \tTout arc uk (1\n
  2. \tLa s\u00e9quence n\u2019utilise pas deux fois le m\u00eame arc (cha\u00eene simple)<\/li>\n
  3. \tLe sommet initial et terminal de la cha\u00eene co\u00efncide Le cycle est \u00e9l\u00e9mentaire s\u2019il v\u00e9rifie de plus:<\/li>\n
  4. \tEn parcourant le cycle on ne rencontre pas deux fois le m\u00eame sommet sauf terminal et initial qui co\u00efncident.\n<\/math>
    \n\"graph1-2.png\"<\/li>\n<\/ol>\n

    Les cycles se repr\u00e9sentent aussi sous la forme de matrice.
    \n
    Ici nous avons le cycle \u00b51=1,2<\/em>=(1,-1,0,0,0,0,0)
    \n
    Dans cette matrice \u00ab 1 \u00bb repr\u00e9sente l\u2019arc 1 parcouru dans le bon sens, \u00ab -1 \u00bb repr\u00e9sente l\u2019arc 2 parcourus dans le sens inverse. Les autres arcs sont \u00e0 0 car ils ne font pas partie du cycle.<\/p>\n

    Un cycle est une s\u00e9quence d’arcs<\/em>
    \n
    Il suffit de suivre les arcs avec un stylo ou avec le doigt sans passer deux fois par le m\u00eame arc.
    \n
    Un cycle est une chaine<\/em>. le point de d\u00e9part est le point d\u2019arriv\u00e9e<\/p>\n

    Exemple :<\/p>\n

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

    Ici sont repr\u00e9sent\u00e9s 6 cycles.
    \n
    Par exemple 1,6,2 est un cycle. Cela me fait passer par les sommets a, b , c, a.
    \nOn peut partir de n’importe quel sommet du cycle<\/p>\n

    Remarque : le sens n\u2019a pas d\u2019importance : b,c,d,b est le m\u00eame cycle que d, b, c, d car on emprunte les m\u00eames arcs<\/p>\n

    Le nombre cyclomatique<\/h2>\n

    Calcul du nombre cyclomatique : v(G) :
    \n
    v(G)=m-n+p<\/p>\n

    n : nombre de sommets
    \n
    m : nombre d\u2019arcs
    \n
    p : nombre de composantes connexes<\/p>\n

    Exemple :<\/p>\n

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

    Sur le graph de droite
    \n
    m=6 car il y a 6 arcs
    \n
    n=4 car on a 4 sommets
    \n
    p=1 car on a 1 connexit\u00e9<\/p>\n

    calcule de v(G)=m-n+p
    \n
    v(G)=6-4+1=3
    \n
    donc nous avons 3 cycles sur le graphe
    \n
    Attention : a b c d a utilise deux cycles<\/p>\n","protected":false},"excerpt":{"rendered":"

    D\u00e9finition : Dans un graphe G=(X,U) un cycle est une s\u00e9quence d \u2019arcs :m=(u1,u2,u3,\u2026,uq) telle que : Tout arc uk (1<\/p>\n","protected":false},"author":2,"featured_media":109,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-112","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\/112","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=112"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/112\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/109"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}