{"id":98,"date":"2009-07-07T09:38:52","date_gmt":"2009-07-07T07:38:52","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/07\/calcul-matriciel\/"},"modified":"2009-07-07T09:38:52","modified_gmt":"2009-07-07T07:38:52","slug":"calcul-matriciel","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=98","title":{"rendered":"Calcul matriciel"},"content":{"rendered":"

Rappels sur le calcul matriciel et bool\u00e9en<\/h2>\n

Addition de matrices<\/strong><\/p>\n

[0150]+ [1203]\t= [1353]
\n
[1210] [0024]\t [1234]<\/p>\n

Multiplication de matrices<\/p>\n

\"calcul_math.jpg\"<\/p>\n

Calcul bool\u00e9en<\/strong>
\n
le + correspond au \u00ab\u00a0OU\u00a0\u00bb
\n
0 + 0 = 0
\n
1 + 0 = 1
\n
0 + 1 = 1
\n
1 + 1 = 1 <\/p>\n

pour les produits : le * correspond au \u00ab\u00a0ET\u00a0\u00bb
\n
0 * 0 = 0
\n
0 * 1 = 0
\n
1 * 0 = 0
\n
1 * 1 = 1
\n
le 0 = Faux
\n
le 1 = Vrai<\/p>\n

Th\u00e9orie des graphes : matrice d\u2019un graphe<\/p>\n

\"matrice_graph.png\"<\/p>\n

Matrice d\u2019incidence ou matrice d\u2019incidence sommet-arc ou sommet-ar\u00eate<\/strong>
\n
Si on a un graphe orient\u00e9 G=(X, U) comportant n sommets et m arcs, on appelle matrice d\u2019incidence sommet-arc la matrice M de dimension n x m avec :
\n
Mij = 1 si xi est l\u2019extr\u00e9mit\u00e9 initiale de l\u2019arc j
\n
Mij = -1 si xi est l\u2019extr\u00e9mit\u00e9 terminale de l\u2019arc j
\n
Mij = 0 si xi n\u2019est pas une extr\u00e9mit\u00e9 de l\u2019arc j
\n
Pour un graphe non orient\u00e9, il n\u2019y a pas de \u20131, juste des 1.<\/p>\n

\"matrice_incidence.png\"<\/p>\n

On num\u00e9rote les arcs comme on veut. La matrice fait 8 sur 5 avec en abscisse les arcs et en ordonn\u00e9e les sommets. C\u2019est aussi une matrice binaire. <\/p>\n

Connexit\u00e9<\/strong>
\n
Un graphe G=(X,U) est connexe si pour tout couple de sommets (x,y) il existe une cha\u00eene joignant x \u00e0 y. Trivialement, \u00e7a signifie qu\u2019il tient en un seul morceau. Si G est divis\u00e9 en trois morceaux, ces morceaux sont des sous-graphes connexes de G, qu\u2019on appelle les composantes connexes du graphe. Le nombre de connexit\u00e9s est not\u00e9 p.<\/p>\n

\"conexite.png\"<\/p>\n

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

Soit un graphe G=(X,U),
\n
M la matrice d\u2019incidence sommets-sommets,
\n
Mk : le produit matriciel bool\u00e9en de M par elle m\u00eame k fois.<\/p>\n

\"chemin_de_longueur_k.png\"<\/p>\n

La pr\u00e9sence d’un 1 sur Mk repr\u00e9sente au moins un chemin entre i et j. Sur la matrice \u00e0 la puissance p, un 1 sur xij indique l\u2019existence d\u2019un chemin de longueur p entre i et j. Si on calculait de fa\u00e7on non bool\u00e9enne, on aurait aussi le nombre de chemins.
\n
Ex : sur M2 bool\u00e9enne, un 1 entre A et B indique l\u2019existence d\u2019un ou plusieurs chemins de longueur 2 entre A et B, comme par exemple le chemin AD DB.<\/p>\n

\"chemin_longueur_k_2.png\"<\/p>\n

On s\u2019arr\u00eate \u00e0 la matrice \u00e0 la puissance trois car on a quatre sommets. On a alors la pr\u00e9sence de chemins entre deux sommets, quels que soient leur longueur.<\/p>\n

Fermeture transitive d\u2019un graphe<\/strong>
\n
Un graphe est transitif<\/em> si, quels que soient deux arcs adjacents, a1 (x, y) et a2 (y, z) appartenant \u00e0 A, alors l\u2019arc a3 (x, z) appartient \u00e9galement \u00e0 A.
\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<\/em> s\u2019obtient en faisant la somme bool\u00e9enne de la matrice unit\u00e9 ou identit\u00e9 ou I ou [1] (matrice carr\u00e9e avec des 1 sur la diagonale et des 0 partout ailleurs) et des puissances successives de la matrice d\u2019adjacence sommets-sommets, M. On s\u2019arr\u00eate \u00e0 la matrice de puissance k-1, nombre de sommets \u20131.
\n
Pour faire la fermeture transitive du graphe, on va ajouter tous les arcs qui n\u2019existent pas selon la r\u00e8gle de transitivit\u00e9.<\/p>\n

Exemple : on a ajout\u00e9 les arcs en rouge<\/p>\n

\"fermeture_trans_1.png\"<\/p>\n

\"fermeture_trans_2.png\"<\/p>\n

La matrice repr\u00e9sente tous les chemins existant entre toute paire de sommets xi,xj<\/em>, plus les boucles r\u00e9flexives et les chemins rajout\u00e9s pour la fermeture transitive.<\/p>\n

Algorithme de Roy-Warshall<\/strong>
\nEtant donn\u00e9 un graphe, G=(X,U) de n sommets, d\u00e9terminez la fermeture transitive de G.
\n
Appelons M la matrice binaire associ\u00e9e \u00e0 G.
\n
On rend G r\u00e9flexif par ajout d\u2019une boucle en chaque sommet n\u2019en comportant pas.
\n
On v\u00e9rifie d\u2019abord que pour tous arcs (i,r) et (r,j), on a bien un arc (i,j). Sinon, on l\u2019ajoute. <\/p>\n

\"roy_warshall.png\"<\/p>\n

On fait de m\u00eame avec les ensembles de trois arcs, quatre arcs et ainsi de suite. <\/p>\n","protected":false},"excerpt":{"rendered":"

Rappels sur le calcul matriciel et bool\u00e9en Addition de matrices [0150]+ [1203] = [1353] [1210] [0024] [1234] Multiplication de matrices Calcul bool\u00e9en le + correspond au \u00ab\u00a0OU\u00a0\u00bb 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 1 pour les produits : le * correspond au […]<\/p>\n","protected":false},"author":2,"featured_media":89,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-98","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\/98","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=98"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/98\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/89"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=98"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=98"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=98"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}