moyen
Matrice d'adjacence
Soit \(n\) un entier strictement positif.
On rappelle que la matrice d'adjacence \(A\) associée à un graphe fini et simple dont les sommets sont numérotés de \(1\) à \(n\) est une matrice carrée à \(n\) lignes et \(n\) colonnes si \(n\) est le nombre de sommets du graphe. Pour tout couple \((i, j)\) , le coefficient \(A_{i, j}\) vaut \(1\) si les sommets numéro \(i\) et numéro \(j\) sont adjacents et \(0\) sinon.
Un graphe et sa matrice d'adjacence
\[\begin{pmatrix}0&1&1&1&0\\1&0&0&0&1\\1&0&0&1&1\\1&0&1&0&0\\0&1&1&0&0\end{pmatrix}\]
Cette matrice est représentée en Python par une liste contenant \(n\) listes de longueur \(n\) , représentant les \(n\) lignes.
Question 1 : Produit de matrices
Le produit de deux matrices carrées \(A\) et \(B\) à \(n\) lignes et \(n\) colonnes est la matrice \(P=A\times B\) telle que pour tout couple \((i, j)\) :
\[p_{i, j} = \sum_{k=1}^n a_{i, k} b_{k, j}\]
Dans la figure ci-dessus on a donc :
\[p_{2, 3} = a_{2, 1} b_{1, 3} + a_{2, 2} b_{2, 3} + a_{2, 3} b_{3, 3}\]
Si les matrices \(A\) et \(B\) sont représentées respectivement par les listes a et b, alors la matrice \(P\) est représentée par la liste p telle que pour tout couple \((i, j)\) valide :
p [ i ][ j ] = a [ i ][ 0 ] * b [ 0 ][ j ] + a [ i ][ 1 ] * b [ 1 ][ j ] + ... + a [ i ][ n - 1 ] * b [ n - 1 ][ j ]
Compléter le code de la fonction produit qui prend en paramètres deux matrices carrées et renvoie le produit de ces deux matrices.
Exemples
>>> a = [[ 0 , 1 ], [ 1 , 0 ]]
>>> b = [[ 1 , 0 ], [ 0 , 1 ]]
>>> produit ( a , b )
[[0, 1], [1, 0]]
>>> produit ( a , a ) == b
[[1, 0], [0, 1]]
.128013 4E2nyg )rPCq;joà*u5(,:éts]h^07w+8f/6û3pçv1x=a_ckmieS9l[Rb.d 050+0Z0y0T0Y0$0z0h0V0$0T0z0z0S010y0Y0N010406050z0s0X0X0T0j0f040!0p0$0s0 0p0e0h020T0X0N0n0h0(0Z190j0m0s0Z0z050J16181a1c140N041A1H051K0J1K1M1H140+0Y0P0@0_0{0}0B0Y0g0B0$1!0B0y12050/0)0$0Z1V0`0|011Z1#1%1#0y1-1/1+0y0)0p0+1c1,0j1I0y0B0@1f0z0N0T0e0}0d011;1X010I0;0Z0e1n0Z1+2c2e2j1?2m1/2p0X2r040a0h0k0j0p0N0p0z0Y1i1k0-2a0j0j0Z0V2M1A2t0e1I0J282Y0y2625270+2v0}1%0e2o2J1+1S1U0^1=2,0Y2.0e221T1+0N2R1I2W2Y33152d1k2@2k2|0j190$120h0Q2V3713362u391?3b3d3f0d3i2e3k2W2+013p0T3e040h0M3t2X143w3n0}3z3B0h0b3F3v373x3L3f0t3P3H3R3J3y0p3c3A3f0K3W3l381W3o3#3q3C0E3*3I3-3K3/3%3C0H3?3Y3^3!3$3M0#3~3m403T040Q0D3P1J311A2=2#0+2)3x0V222B0,1T1I300Z323j4c4l0-4t462^010W120-0I4c3@4A0F3f4G3 4A0e0I1230220s2L4L4z2k11040u4V3,4N120T4#3x4Y0v3P0h3+3S120)4*3Z4Y0i0w3W0h4}4/4H3a120e4.4:3Z0p120S54503o0)122y4@404Y4!1B4u5b3K4(5g4A4_4|4~55474Q5a4M2k5704595k3u4 5y1?4Y0%0%5p2k0X0Y124b5D2X5u5q120A5x4W1?5A0r5X4$5104535R3C5T2k4C040I3#5$4;040Y5?564J5^5*335F5Y3K5d040j2e0g0Z5L5H125j355m3y52690}4_5W5+064~605%1?5/5;0j5`5v5^6u4A0p5|2`6x3a63650e676h015i6I0e6g5+5-6a044`5s6n4}6P0}6r5=5+6o5@0o6C5Z6A5~3j6#3Z0e6E66686O6e6K6?5G5n5)6I4_4{6l6U716-6v0N0U0Y0U6%6!6W015A5C5 7b5N5P6T726V6e6Y6t7a6e6M040W6(0}6z126B7p6`3y6:6G6=6d7A6^7F616f6|6_7J6~7j7k6n7b7r7577797f6e7d7u7K7U787!5A0G7!7r4)7M6p6i125K7.5@5_7?4^5V7=7I7/7K7t7_5h5V7(125#7z7J7r4?815U047|5l7A7r807}4+7{6L127W8f7N83707Q7l8g5w8b4X7;8m6w8x6Q0A8e3u7S8n6}8r7X7A7Z877~7T767%8s8u7J5/2R0y0s0j6+5E8H040N3*0J4w4s4d8-0J4g1A0y4i8=2%2Z21232#0T1.8/4g1G4y7~2R0X0U0I0T0W0Z0U0B0M121s1u1w1y0h6 351N3k1H0l0.0y1:980O1j0h2O4R0V0x0-0j2P2R2c1j2*0q0h0_9x0x2m0e2L0Y9w19280x9T0Y9i0h4R2I0z0x0Z0*0h0c0$1/0h1y0y0h0y0p1h0Z5;0Y0?4l0L9s0s0z1:2o0h2H0x652M0?0w0h0X0s0$0 0N1%0Z9D0-0s0Raa0T2$0Y0V9j0V1a0j9%0?2O1S2A0e2K9w7b1a2L0B9T0Z0R12090u0e090i4.0e0xaq0{2L1:0:aA0Y0h9i0$9i0?aD0jaFaHaJ04aL0e0C0MaO4.a4a69RaA0*1J3k8:0.0:0=04.
Question 2 : Recherche d'un triangle
On considère un graphe, fini, simple et non orienté , la matrice d'adjacence associée \(A\) et la matrice \(A^2= A \times A\) . Les deux propriétés suivantes sont équivalentes :
Il existe un couple \((i, j)\) , avec \(i \neq j\) , tel que les coefficients \(A_{i, j}\) et \(A^2_{i, j}\) sont non nuls ;
Le graphe possède un cycle de longueur \(3\) , qu'on appelle un triangle .
Par exemple, les deux graphes ci-dessous possèdent un triangle .
Par contre, ce graphe ne possède pas de triangle :
Écrire une fonction triangle qui prend en paramètre une matrice d'adjacence associée à un graphe et renvoie True si le graphe possède un triangle et False sinon.
Une version valide de la fonction produit demandée à la question précédente est déjà incluse dans cet éditeur. Vous pouvez l'utiliser sans l'importer .
Exemples
>>> a = [[ 0 , 1 , 1 ], [ 1 , 0 , 1 ], [ 1 , 1 , 0 ]]
>>> triangle ( a )
True
>>> b = [
... [ 0 , 1 , 1 , 1 , 0 ],
... [ 1 , 0 , 0 , 0 , 1 ],
... [ 1 , 0 , 0 , 1 , 1 ],
... [ 1 , 0 , 1 , 0 , 0 ],
... [ 0 , 1 , 1 , 0 , 0 ],
... ]
>>> triangle ( b )
True
>>> c = [[ 0 , 1 ], [ 1 , 0 ]]
>>> triangle ( c )
False
.128013 42AnygF )TrPCq-;joàè{u5(,:éts]h0^7w8f/6û3pODv1x=a_ckm}iLeSl[Rb.d 050:0)0C0X0%0+0D0i0Z0+0X0D0D0W010C0%0Q010406050D0w0#0#0X0l0f040*0s0+0w140s0e0i020X0#0Q0q0i0-0)1e0l0o0w0)0D050M1b1d1f1h190Q041F1M051P0M1P1R1M190:0%0T0|0~10120F0%0g0F0+1)0F0C17050@0.0+0)1!0 11011(1*1,1*0C1=1@1:0C0.0s0:1h1;0l1N0C0F0|1k0D0Q0X0e120c011_1$010L0_0)0e1s0)1:2h2j2o1{2r1@2u0#2w040a0i0m0l0s0Q0s0D0%1n1p0=2f0l0l0)0Z2R1F2y0e1N0M2d2%0C2b2a2c0:2A121,0e2t2O1:1X1Z0}1`2;0%2?0e271Y1:0Q2W1N2#2%381a2i1p2|2p310l1e0+170U2!3c183b2z3e1{3g3i170c3m2j3o2#2:013t0X3j040P3x2$193A3r123D3F0b3I3z3c3B3O170x3R3K3T3M3C0s3h3E170N3Y3p3d1#3s3%3u040I3,3L3/3N3;3)040K3R1O361F2`2*0:2.3B0Z272G0;1Y1N350)373n40490=4h3q3`010!170=0L403_2}010J170i4u3!4o0e0L172+0%2j0g1@4B4n4w16040y4M3.4w0e170X4S3B4P0j0A3Y0i4(4A4v3f170e3R4*4C4w0s170W4/3-3U0.172D4Y3#4P4R1G4i4+3s4W4 4o4!4%4)4`3#4V040X0Y0Z1f2W4_55124?044^533y4:4N4,0435270w2Q584O17523a5n3C575s2$5d59170z5m4;5w4X5K4m4T2p5a5U064)5u5W1{4q040L3%5Q5v56040%5-5%5o4y5:4.5U5$4{170l4J0)5C5X5E625/5`5G5R1{4!4$5Z5#5#5M4w5)5+0l5=3U170r6l3#0s5^2 6p4D4|045 0e0g615U6g634Q653N4-6G016b5b6e6e6D5(170%4t5{6P6H5g6J4P0,6J5f5;6C5H4P0E6!6(696W6o6-5.126*6u4=17020g0C0q6^2p0#0%170G6 1{6r4W0e0:756W5h5j2V6B686=6K176,7h5?5I5:6Y176+6#6n7q040E7b015p6{6}7y71737v6c385!6N7K4(6V4p5~0?0w0l673n5|3#0!0Z170k0l1C6M7V4o5)2W0C7R7T5t7N7X170h3E0D7g3n190M4k4g417~0M441F0C46832,2(26282*0X1?80441L5V3B2W0#0Y0L0X0!0)0Y0F0P171x1z1B1D0i7H4i1S3o1M0R1p0#1o2+1^8w0i0:2j0{0Z1^5j0{2T2r0g7R0)0z0i1@2f0)0L2r0Z0%2t0C7(4w1f2Q0F1e0C0)0V17090y5h0v0%0z0r0$090j4/2T0~8-2p8/2d8=8@8_0y0!923R0p0%0u2F0i0Q5A102j8P8L1^968=0l0%9r0:000X0:0r0X8P0e9r1D8,0B0g3E0i0X0w0i310#0.2W9s0|0F1y2 8S9t1o8V0)7R971{998;0X8?8^048`9f935{2W1,2j8,1@0{0D0s1d0?9!9Q1c0B2L0{7N9,9b9:8`0%9g5{0?9*12aa9.9c9;0y0raf380/1O8C040(8x0=0w0V9m2L350%0B0C0B0{0B1B1Y3E8+8x8)aGax8N8Z000B319G0B0i9 0e8,0:1o0Z9N0w100%0iaJ5A0TaMa#8x0t8Z0XaB2M9waFaY1baLa?8yat8g0_0i8@0%0D8?0i0w1p2 1X9ra99w9aalac0yae9@380i8?0+0i8K8!498$8(8*a#8L4I0g1o9Mbi8:ab9d0d0H0P0Y8}8Y0%91bp7U0e009I9m0 a40+8YbHbk9/bKbMaq7U0:aH1)2ubB9u9.9wbh5Hakb)an0d0i09142F0{b~c00%c20i0db,3yas8B8g0n0?bb5yaDa~9QbWbabY0{1m0_b90B1^9xa-7eb70+8!0e0B8Pa,bbbw3E0Z0wbt2TayaA5y0:5A0Ca39v9xax8H8Z8Q0s0O8,bXc62N0l0@a#cc1V1Q040S1^1e0e9j9U0gaVa6aM8Y0D00b6b8ba1^bd0ibfcUai01b{amadca2$br0)btbvcYbycv8+bC0XbE2ubtb%9-b|8`bL0ebO8~d5bS4/bVbX2i0{0ecJ8Y1o9m9(8,0X8%0%3h0)0lbu0wc btd1bbd40Z0f0}1^959$1C9)dsbJan0edd04c,3o810?0^0`04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)