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 5q/(û+0=._a1ki o4m2^:fedw,y]crCvps3[*nPg)ul;jSétx9EàçRbh867 050y0x0W0l0o0R0I0p0D0R0l0I0I0i010W0o0H010406050I0Q0s0s0l0E0B040U0q0R0Q0 0q0M0p020l0s0H0S0p0$0x190E0c0Q0x0I050d16181a1c140H04051H1A1K0d1H140y0o0G0@0_0{0}0(0o0O0(0R1Y0(0W12050/0%0R0x1T0`0|011X1Z1#1Z0W1+1-1)0W0E1I0W0(0@1f0I0H0l0M0}0t011/1V010w0;0x0M1n0x1)25272c1;2f1-2i0s2k040a0p0N0E0q0H0q0I0o1i1k0-230E0E0x0D2F1A2m0M1I0d212R1~201 1*0y2o0}1#0M2h2C1)1Q1S0^1:2#0o2%0M0q2+1)0H2K1I2P2R2|15261k2-2d2=0E190R120p0m2O30132 2n321;3436380t3b273d2P2!013i0l37040p0J3m2Q143p3g0}3s3u0p0r3y3o303q3E380b3I3A3K3C3r0q353t380*3P3e311U3h3U3j3v0+3Z3B3$3D3(3W3v0)3,3R3.3T3V3F0Y3@3f3_3M040m0h3I1L2`1A2+2U0y202Z3S0D2?2u0,1R1I2_0x2{3c454f0-4n3 2.010n120-0w453-4u0z384A3^4u0M0w122_2?0Q2E4F4t2d11040e4P3#4H120l4V3q4S0A3I0p3!3L120%4!3S4S0P0v3P0p4@4)4B33120M4(4*3S0q120i4~4`3h0%122r4.3_4S4U1B4o553D4Y5a4u4:4?4^4 404K544G2d5104535e3n4_5s1;4S0K0K5j2d0s0o12445x2Q5o5k120C5r4Q1;5u0L5R4W4{044}5L3v5N2d4w040w3U5W4+040o5-504D5/5!2|5z5S3D57040E270O0x5F5B125d2~5g3r4|630}4:5Q5#064^5`5X1;5)5+0E5;5p5/6o4u0q5?2:6r335}5 0M616b015c6C0M6a5#5%64044;5m6h4@6J0}6l5,5#6i5.0T6w5T6u5^3c6V3S0M6y60626I686E6-5A5h5Z6C4:4=6f6O6{6%6p0H0k0o0k6X6U6Q015u5w5_755H5J6N6|6P686S6n74686G040n6Y0}6t126v7j6;3r6*6A6,677u6/7z5{696?6:7D6^7d7e6h757l6 71737968777o7E7O727U5u0g7U7l4Z7G6j6c125E7(5.5:7-4/5P7,7C7)7E7n7:5b5P7Y125V7t7D7l4-7{5O047?5f7u7l7`7@4#7=6F127Q897H7}6`7K7f8a5q854R7+8g6q8r6K0C883n7M8h6@8l7R7u7T817^7N707X8m8o7D5)2K0W0Q0E6#5y8B040H3Z0d4q4m468%0d491A0W4b8,2X2S0l1,8)491G4s7^2K0s0k0w0l0n0x0k0(0J121s1u1w1y0p6_2~1N3d1H0F0.0W1.8 0#1j0p2H4L0D0V0-0E2I2K251j2Z0!0p0_9o0V2f0M2E0o9n19210V9K0o990p4L2B0I0V0x0j0p0Z0R1-0p1y0W0p0W0q1h0x5+0o0?4f0f9j0Q0I1.2h0p2A0V5 2F0?0v0p0s0Q0R0 0H1#0x9u0-0Q0Xa10l1~0o0D9a0D1a0E9U0?2H1Q2t0M2D9n751a2E0(9K0x0X12090e0M090P4(0M0Vah0{2E1.0:ar0o0p990R990?au0EawayaA04aC0M0u0JaF4(9{9}9Iar0j1L3d8*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 5q/(û0{L=._a1ki o4m2^:}fedw,y]-crCvpTsO3[DnPg)ulF;jSétxàRbèAh867 050A0z0$0m0p0W0M0q0G0W0m0M0M0j010$0p0K010406050M0V0t0t0m0H0D040!0r0W0V140r0R0q020m0t0K0Y0q0)0z1e0H0c0V0z0M050d1b1d1f1h190K04051M1F1P0d1M190A0p0J0|0~10120-0p0T0-0W1%0-0$17050@0*0W0z1Y0 11011$1(1*1(0$1:1=1.0$0H1N0$0-0|1k0M0K0m0R120u011@1!010y0_0z0R1s0z1.2a2c2h1_2k1=2n0t2p040a0q0S0H0r0K0r0M0p1n1p0=280H0H0z0G2K1F2r0R1N0d262W2325241/0A2t121*0R2m2H1.1V1X0}1^2*0p2,0R0r2:1.0K2P1N2U2W311a2b1p2=2i2`0H1e0W170n2T3518342s371_393b170u3f2c3h2U2)013m0m3c040O3q2V193t3k123w3y0s3B3s353u3H170b3K3D3M3F3v0r3a3x170/3R3i361Z3l3W3n040:3#3E3(3G3*3Y040.3K1Q2 1F2:2Z0A252(3U0G2{2z0;1W1N2~0z303g3_430=4b3j3:010o170=0y3_3/2?010B170q4o3T4i0R0y17230p2c0T1=4v4h4q16040e4G3%4q0R170m4M3u4J0U0w3R0q4Y4u4p38170R3K4!4w4q0r170j4)3$3N0*172w4S3U4J4L1G4c4#3l4Q4_4i4U4X4Z4;3U4P040m0l0G1f2P4:4 124-044/4}3r4*4H4$042~2{0V2J524I174|335h3v515m2V5753170C5g4+5q4R5E4g4N2i545O064Z5o5Q1_4k040y3W5K5p50040p5%5X5i4s5*4(5O5W4=170H4D0z5w5R5y5|5)5;5A5L1_4U4W5T5V5V5G4q5Z5#0H5,3N170Z6f3U0r5/2^6j4x4?045_0R0T5{5O6a5}4K5 3G4%6A01655568686x5Y170p4n5=6J6B5a6D4J0P6D595+6w5B4J0E6U6Y636Q6i6%5(126!6o4,17020T0$0Y6/2i0t0p170g6_1_6l4Q0R0A6 6Q5b5d2O6v626,6E176$7b5-5C5*6S176#6V6h7k040E75015j6=6@7s6{6}7p66315U6H7E4Y6P4j5^0?0V0H613g5?3U0o0G170L0H1C6G7P4i5Z2P0$7L7N5n7H7R170X3x0M7a3g190d4e4a3`7^0d3}1F0$3 7}2$2X0m1;7`3}1L5P3u2P0t0l0y0m0o0z0l0-0O171x1z1B1D0q7B4c1S3h1M0N1p0t1o231?8n0q0A2c0{0G1?5d0{2M2k0T7L0z0C0q1=280z0y2k0G0p2m0$7Y4q1f2J0-1e0$0z0%17090e5b0h0p0C0Z0x090U4)2M0~8!2i8$268)8+8-0e0o8_3K0F0p0+2y0q0K5u102c8G8C1?8}8)0H0p9i0A000m0A0Z0m8G0R9i1D8Z0#0T3x0q0m0V0q2`0t0*2P9j0|0-1y2^8J9k1o8M0z7L8~1_908(0m8*8,048.968`5=2P1*2c8Z1=0{0M0r1d0?9R9H1c0#2E0{7H9Z929%8.0p975=0?9X12a19#939(0e0Za6310k1Q8t040i8o0=0V0%9d2E2~0p0#0$0#0{0#1B1W3x8Y8o8Waxao8E8Q000#2`9x0#0q9?0R8Z0A1o0G9E0V100p0qaA5u0JaDaS8o0(8Q0mas2F9nawaP1baCa*8pak870_0q8+0p0M8*0q0V1p2^1V9ia09n91aca30ea59+310q8*0W0q8B8R438T8V8XaS8C4C0T1o9Db98%a2940,0v0O0l8;8P0p8^bg7O0R009z9d0 9{0W8Pbybb9$bBbDah7O0Aay1%2nbs9l9#9nb85BabbWae0,0q09142y0{b=b@0pb_0q0,bZ3raj8s870I0?b25saua=9HbNb1bP0{1m0_b00#1?9oa!78a~0W8R0R0#8GaZb2bn3x0G0Vbk2Mapar5s0A5u0$9`9m9oao8y8Q8H0r0f8ZbOb}2G0H0@aSc31T1O040Q1?1e0R9a9L0TaM9}aD8P0M00a}a b11?b40qb6cLa901b/ada4c12Vbi0zbkbmcPbpcm8Ybt0mbv2nbkbU9!b:8.bC0RbF8=c|bJ4)bMbO2b0{0RcA8P1o9d9V8Z0m8U0p3a0z0Hbl0Vc?bkc^b2c{0G0D0}1?8|9T1C9WdjbAae0Rd404cZ3h7{0?0^0`04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)