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 s3_8uf^vy n7aSû1me(P24C:jtwi][çhE*)6o;bcdg/0làqp.r,=+k95Rxé 050P0s0A0n0C0T0b0k0O0T0n0b0b0!010A0C0W010406050b0f0r0r0n0Y0j040o0L0T0f0 0L0l0k020n0r0W0M0k0)0s190Y0V0f0s0b050R16181a1c140W041A1H051K0R1K1M1H140P0C0i0@0_0{0}0G0C0Q0G0T1!0G0A12050/0N0T0s1V0`0|011Z1#1%1#0A1-1/1+0A0N0L0P1c1,0Y1I0A0G0@1f0b0W0n0l0}0v011;1X010g0;0s0l1n0s1+2c2e2j1?2m1/2p0r2r040a0k0u0Y0L0W0L0b0C1i1k0-2a0Y0Y0s0O2M1A2t0l1I0R282Y0A2625270P2v0}1%0l2o2J1+1S1U0^1=2,0C2.0l221T1+0W2R1I2W2Y33152d1k2@2k2|0Y190T120k0q2V3713362u391?3b3d3f0v3i2e3k2W2+013p0n3e040k0c3t2X143w3n0}3z3B0k0w3F3v373x3L3f0(3P3H3R3J3y0L3c3A3f0K3W3l381W3o3#3q3C0m3*3I3-3K3/3%3C0e3?3Y3^3!3$3M0%3~3m403T040q0S3P1J311A2=2#0P2)3x0O222B0,1T1I300s323j4c4l0-4t462^010$120-0g4c3@4A0B3f4G3 4A0l0g1230220f2L4L4z2k11040t4V3,4N120n4#3x4Y0Z3P0k3+3S120N4*3Z4Y0J0y3W0k4}4/4H3a120l4.4:3Z0L120!54503o0N122y4@404Y4!1B4u5b3K4(5g4A4_4|4~55474Q5a4M2k5704595k3u4 5y1?4Y0E0E5p2k0r0C124b5D2X5u5q120D5x4W1?5A0I5X4$5104535R3C5T2k4C040g3#5$4;040C5?564J5^5*335F5Y3K5d040Y2e0Q0s5L5H125j355m3y52690}4_5W5+064~605%1?5/5;0Y5`5v5^6u4A0L5|2`6x3a63650l676h015i6I0l6g5+5-6a044`5s6n4}6P0}6r5=5+6o5@0z6C5Z6A5~3j6#3Z0l6E66686O6e6K6?5G5n5)6I4_4{6l6U716-6v0W0d0C0d6%6!6W015A5C5 7b5N5P6T726V6e6Y6t7a6e6M040$6(0}6z126B7p6`3y6:6G6=6d7A6^7F616f6|6_7J6~7j7k6n7b7r7577797f6e7d7u7K7U787!5A0#7!7r4)7M6p6i125K7.5@5_7?4^5V7=7I7/7K7t7_5h5V7(125#7z7J7r4?815U047|5l7A7r807}4+7{6L127W8f7N83707Q7l8g5w8b4X7;8m6w8x6Q0D8e3u7S8n6}8r7X7A7Z877~7T767%8s8u7J5/2R0A0f0Y6+5E8H040W3*0R4w4s4d8-0R4g1A0A4i8=2%2Z21232#0n1.8/4g1G4y7~2R0r0d0g0n0$0s0d0G0c121s1u1w1y0k6 351N3k1H0x0.0A1:980F1j0k2O4R0O0+0-0Y2P2R2c1j2*0U0k0_9x0+2m0l2L0C9w19280+9T0C9i0k4R2I0b0+0s0X0k0H0T1/0k1y0A0k0A0L1h0s5;0C0?4l0p9s0f0b1:2o0k2H0+652M0?0y0k0r0f0T0 0W1%0s9D0-0f0*aa0n2$0C0O9j0O1a0Y9%0?2O1S2A0l2K9w7b1a2L0G9T0s0*12090t0l090J4.0l0+aq0{2L1:0:aA0C0k9i0T9i0?aD0YaFaHaJ04aL0l0h0caO4.a4a69RaA0X1J3k8: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 s3_8èuf^vy n7aSû1me(P24C:jtwi]D[h)6Oo;bcdgx/T0làqAp.rFL-,}=k5R{é 050P0t0B0o0D0V0b0l0O0V0o0b0b0+010B0D0Z010406050b0g0s0s0o0#0k040p0L0V0g140L0m0l020o0s0Z0M0l0.0t1e0#0X0g0t0b050S1b1d1f1h190Z041F1M051P0S1P1R1M190P0D0j0|0~10120H0D0Q0H0V1)0H0B17050@0N0V0t1!0 11011(1*1,1*0B1=1@1:0B0N0L0P1h1;0#1N0B0H0|1k0b0Z0o0m120w011_1$010h0_0t0m1s0t1:2h2j2o1{2r1@2u0s2w040a0l0v0#0L0Z0L0b0D1n1p0=2f0#0#0t0O2R1F2y0m1N0S2d2%0B2b2a2c0P2A121,0m2t2O1:1X1Z0}1`2;0D2?0m271Y1:0Z2W1N2#2%381a2i1p2|2p310#1e0V170r2!3c183b2z3e1{3g3i170w3m2j3o2#2:013t0o3j040c3x2$193A3r123D3F0x3I3z3c3B3O170-3R3K3T3M3C0L3h3E170J3Y3p3d1#3s3%3u040n3,3L3/3N3;3)040e3R1O361F2`2*0P2.3B0O272G0;1Y1N350t373n40490=4h3q3`010,170=0h403_2}010C170l4u3!4o0m0h172+0D2j0Q1@4B4n4w16040u4M3.4w0m170o4S3B4P0I0z3Y0l4(4A4v3f170m3R4*4C4w0L170+4/3-3U0N172D4Y3#4P4R1G4i4+3s4W4 4o4!4%4)4`3#4V040o0d0O1f2W4_55124?044^533y4:4N4,0435270g2Q584O17523a5n3C575s2$5d59170)5m4;5w4X5K4m4T2p5a5U064)5u5W1{4q040h3%5Q5v56040D5-5%5o4y5:4.5U5$4{170#4J0t5C5X5E625/5`5G5R1{4!4$5Z5#5#5M4w5)5+0#5=3U170A6l3#0L5^2 6p4D4|045 0m0Q615U6g634Q653N4-6G016b5b6e6e6D5(170D4t5{6P6H5g6J4P0G6J5f5;6C5H4P0E6!6(696W6o6-5.126*6u4=17020Q0B0M6^2p0s0D170U6 1{6r4W0m0P756W5h5j2V6B686=6K176,7h5?5I5:6Y176+6#6n7q040E7b015p6{6}7y71737v6c385!6N7K4(6V4p5~0?0g0#673n5|3#0,0O170T0#1C6M7V4o5)2W0B7R7T5t7N7X170$3E0b7g3n190S4k4g417~0S441F0B46832,2(26282*0o1?80441L5V3B2W0s0d0h0o0,0t0d0H0c171x1z1B1D0l7H4i1S3o1M0K1p0s1o2+1^8w0l0P2j0{0O1^5j0{2T2r0Q7R0t0)0l1@2f0t0h2r0O0D2t0B7(4w1f2Q0H1e0B0t0R17090u5h0/0D0)0A0*090I4/2T0~8-2p8/2d8=8@8_0u0,923R0(0D0f2F0l0Z5A102j8P8L1^968=0#0D9r0P000o0P0A0o8P0m9r1D8,0:0Q3E0l0o0g0l310s0N2W9s0|0H1y2 8S9t1o8V0t7R971{998;0o8?8^048`9f935{2W1,2j8,1@0{0b0L1d0?9!9Q1c0:2L0{7N9,9b9:8`0D9g5{0?9*12aa9.9c9;0u0Aaf380!1O8C040%8x0=0g0R9m2L350D0:0B0:0{0:1B1Y3E8+8x8)aGax8N8Z000:319G0:0l9 0m8,0P1o0O9N0g100D0laJ5A0jaMa#8x0W8Z0oaB2M9waFaY1baLa?8yat8g0_0l8@0D0b8?0l0g1p2 1X9ra99w9aalac0uae9@380l8?0V0l8K8!498$8(8*a#8L4I0Q1o9Mbi8:ab9d0Y0i0c0d8}8Y0D91bp7U0m009I9m0 a40V8YbHbk9/bKbMaq7U0PaH1)2ubB9u9.9wbh5Hakb)an0Y0l09142F0{b~c00Dc20l0Yb,3yas8B8g0y0?bb5yaDa~9QbWbabY0{1m0_b90:1^9xa-7eb70V8!0m0:8Pa,bbbw3E0O0gbt2TayaA5y0P5A0Ba39v9xax8H8Z8Q0L0q8,bXc62N0#0@a#cc1V1Q040F1^1e0m9j9U0QaVa6aM8Y0b00b6b8ba1^bd0lbfcUai01b{amadca2$br0tbtbvcYbycv8+bC0obE2ubtb%9-b|8`bL0mbO8~d5bS4/bVbX2i0{0mcJ8Y1o9m9(8,0o8%0D3h0t0#bu0gc btd1bbd40O0k0}1^959$1C9)dsbJan0mdd04c,3o810?0^0`04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)