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 fe)à61ipmSvk(q5rxd;Po/aR l+é[C8yç7_3:*tg.=swc,^û]h2nEb0j94u 050s0c0N0x0h0A0R0z0T0A0x0R0R0Q010N0h0i010406050R0+0j0j0x0q0G040k0v0A0+0 0v0!0z020x0j0i0t0z0y0c190q0o0+0c0R050w16181a1c140i04051H1A1K0w1H140s0h0l0@0_0{0}0Y0h0O0Y0A1Y0Y0N12050/0$0A0c1T0`0|011X1Z1#1Z0N1+1-1)0N0q1I0N0Y0@1f0R0i0x0!0}0Z011/1V010b0;0c0!1n0c1)25272c1;2f1-2i0j2k040a0z0u0q0v0i0v0R0h1i1k0-230q0q0c0T2F1A2m0!1I0w212R1~201 1*0s2o0}1#0!2h2C1)1Q1S0^1:2#0h2%0!0v2+1)0i2K1I2P2R2|15261k2-2d2=0q190A120z0g2O30132 2n321;3436380Z3b273d2P2!013i0x37040z0K3m2Q143p3g0}3s3u0z0*3y3o303q3E380p3I3A3K3C3r0v353t380f3P3e311U3h3U3j3v0I3Z3B3$3D3(3W3v0F3,3R3.3T3V3F0)3@3f3_3M040g0%3I1L2`1A2+2U0s202Z3S0T2?2u0,1R1I2_0c2{3c454f0-4n3 2.010m120-0b453-4u0S384A3^4u0!0b122_2?0+2E4F4t2d11040n4P3#4H120x4V3q4S0U3I0z3!3L120$4!3S4S0d0L3P0z4@4)4B33120!4(4*3S0v120Q4~4`3h0$122r4.3_4S4U1B4o553D4Y5a4u4:4?4^4 404K544G2d5104535e3n4_5s1;4S0D0D5j2d0j0h12445x2Q5o5k120X5r4Q1;5u0M5R4W4{044}5L3v5N2d4w040b3U5W4+040h5-504D5/5!2|5z5S3D57040q270O0c5F5B125d2~5g3r4|630}4:5Q5#064^5`5X1;5)5+0q5;5p5/6o4u0v5?2:6r335}5 0!616b015c6C0!6a5#5%64044;5m6h4@6J0}6l5,5#6i5.0(6w5T6u5^3c6V3S0!6y60626I686E6-5A5h5Z6C4:4=6f6O6{6%6p0i0J0h0J6X6U6Q015u5w5_755H5J6N6|6P686S6n74686G040m6Y0}6t126v7j6;3r6*6A6,677u6/7z5{696?6:7D6^7d7e6h757l6 71737968777o7E7O727U5u0B7U7l4Z7G6j6c125E7(5.5:7-4/5P7,7C7)7E7n7:5b5P7Y125V7t7D7l4-7{5O047?5f7u7l7`7@4#7=6F127Q897H7}6`7K7f8a5q854R7+8g6q8r6K0X883n7M8h6@8l7R7u7T817^7N707X8m8o7D5)2K0N0+0q6#5y8B040i3Z0w4q4m468%0w491A0N4b8,2X2S0x1,8)491G4s7^2K0j0J0b0x0m0c0J0Y0K121s1u1w1y0z6_2~1N3d1H0E0.0N1.8 0H1j0z2H4L0T0C0-0q2I2K251j2Z0e0z0_9o0C2f0!2E0h9n19210C9K0h990z4L2B0R0C0c0P0z0#0A1-0z1y0N0z0N0v1h0c5+0h0?4f0W9j0+0R1.2h0z2A0C5 2F0?0L0z0j0+0A0 0i1#0c9u0-0+0ra10x1~0h0T9a0T1a0q9U0?2H1Q2t0!2D9n751a2E0Y9K0c0r12090n0!090d4(0!0Cah0{2E1.0:ar0h0z990A990?au0qawayaA04aC0!0V0KaF4(9{9}9Iar0P1L3d8*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 fe})à61ipmSvk(q5rxOd;TPo/aRA lé[C8Ly7_3:{-tg.=swcF,è^û]hD2nb0j4u 050u0c0R0A0i0E0V0D0X0E0A0V0V0U010R0i0j010406050V0:0k0k0A0r0K040l0y0E0:140y0+0D020A0k0j0v0D0B0c1e0r0p0:0c0V050z1b1d1f1h190j04051M1F1P0z1M190u0i0m0|0~10120(0i0S0(0E1%0(0R17050@0,0E0c1Y0 11011$1(1*1(0R1:1=1.0R0r1N0R0(0|1k0V0j0A0+120*011@1!010b0_0c0+1s0c1.2a2c2h1_2k1=2n0k2p040a0D0x0r0y0j0y0V0i1n1p0=280r0r0c0X2K1F2r0+1N0z262W2325241/0u2t121*0+2m2H1.1V1X0}1^2*0i2,0+0y2:1.0j2P1N2U2W311a2b1p2=2i2`0r1e0E170h2T3518342s371_393b170*3f2c3h2U2)013m0A3c040N3q2V193t3k123w3y0/3B3s353u3H170q3K3D3M3F3v0y3a3x170g3R3i361Z3l3W3n040L3#3E3(3G3*3Y040I3K1Q2 1F2:2Z0u252(3U0X2{2z0;1W1N2~0c303g3_430=4b3j3:010n170=0b3_3/2?010W170D4o3T4i0+0b17230i2c0S1=4v4h4q16040o4G3%4q0+170A4M3u4J0e0O3R0D4Y4u4p38170+3K4!4w4q0y170U4)3$3N0,172w4S3U4J4L1G4c4#3l4Q4_4i4U4X4Z4;3U4P040A0M0X1f2P4:4 124-044/4}3r4*4H4$042~2{0:2J524I174|335h3v515m2V5753170Z5g4+5q4R5E4g4N2i545O064Z5o5Q1_4k040b3W5K5p50040i5%5X5i4s5*4(5O5W4=170r4D0c5w5R5y5|5)5;5A5L1_4U4W5T5V5V5G4q5Z5#0r5,3N170.6f3U0y5/2^6j4x4?045_0+0S5{5O6a5}4K5 3G4%6A01655568686x5Y170i4n5=6J6B5a6D4J0G6D595+6w5B4J0%6U6Y636Q6i6%5(126!6o4,17020S0R0v6/2i0k0i170-6_1_6l4Q0+0u6 6Q5b5d2O6v626,6E176$7b5-5C5*6S176#6V6h7k040%75015j6=6@7s6{6}7p66315U6H7E4Y6P4j5^0?0:0r613g5?3U0n0X170w0r1C6G7P4i5Z2P0R7L7N5n7H7R170Y3x0V7a3g190z4e4a3`7^0z3}1F0R3 7}2$2X0A1;7`3}1L5P3u2P0k0M0b0A0n0c0M0(0N171x1z1B1D0D7B4c1S3h1M0t1p0k1o231?8n0D0u2c0{0X1?5d0{2M2k0S7L0c0Z0D1=280c0b2k0X0i2m0R7Y4q1f2J0(1e0R0c0s17090o5b0P0i0Z0.0d090e4)2M0~8!2i8$268)8+8-0o0n8_3K0Q0i0!2y0D0j5u102c8G8C1?8}8)0r0i9i0u000A0u0.0A8G0+9i1D8Z0F0S3x0D0A0:0D2`0k0,2P9j0|0(1y2^8J9k1o8M0c7L8~1_908(0A8*8,048.968`5=2P1*2c8Z1=0{0V0y1d0?9R9H1c0F2E0{7H9Z929%8.0i975=0?9X12a19#939(0o0.a6310T1Q8t040J8o0=0:0s9d2E2~0i0F0R0F0{0F1B1W3x8Y8o8Waxao8E8Q000F2`9x0F0D9?0+8Z0u1o0X9E0:100i0DaA5u0maDaS8o0f8Q0Aas2F9nawaP1baCa*8pak870_0D8+0i0V8*0D0:1p2^1V9ia09n91aca30oa59+310D8*0E0D8B8R438T8V8XaS8C4C0S1o9Db98%a2940C0#0N0M8;8P0i8^bg7O0+009z9d0 9{0E8Pbybb9$bBbDah7O0uay1%2nbs9l9#9nb85BabbWae0C0D09142y0{b=b@0ib_0D0CbZ3raj8s870H0?b25saua=9HbNb1bP0{1m0_b00F1?9oa!78a~0E8R0+0F8GaZb2bn3x0X0:bk2Mapar5s0u5u0R9`9m9oao8y8Q8H0y0$8ZbOb}2G0r0@aSc31T1O040)1?1e0+9a9L0SaM9}aD8P0V00a}a b11?b40Db6cLa901b/ada4c12Vbi0cbkbmcPbpcm8Ybt0Abv2nbkbU9!b:8.bC0+bF8=c|bJ4)bMbO2b0{0+cA8P1o9d9V8Z0A8U0i3a0c0rbl0:c?bkc^b2c{0X0K0}1?8|9T1C9WdjbAae0+d404cZ3h7{0?0^0`04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)