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 :p(40^ed3; 1jEo5_n)h]6,qc[yCuvài2+xms7=ûwlSatf9Rrg.*çéPkb8/ 050i0h0T0S0G0Q0L0l0z0Q0S0L0L0N010T0G0c010406050L0D0K0K0S0X0B040R0p0Q0D0 0p0s0l020S0K0c0k0l0W0h190X0y0D0h0L050+16181a1c140c041A1H051K0+1K1M1H140i0G0E0@0_0{0}0u0G0Y0u0Q1!0u0T12050/0)0Q0h1V0`0|011Z1#1%1#0T1-1/1+0T0)0p0i1c1,0X1I0T0u0@1f0L0c0S0s0}0H011;1X010U0;0h0s1n0h1+2c2e2j1?2m1/2p0K2r040a0l0%0X0p0c0p0L0G1i1k0-2a0X0X0h0z2M1A2t0s1I0+282Y0T2625270i2v0}1%0s2o2J1+1S1U0^1=2,0G2.0s221T1+0c2R1I2W2Y33152d1k2@2k2|0X190Q120l0m2V3713362u391?3b3d3f0H3i2e3k2W2+013p0S3e040l0j3t2X143w3n0}3z3B0l0e3F3v373x3L3f0q3P3H3R3J3y0p3c3A3f0w3W3l381W3o3#3q3C0M3*3I3-3K3/3%3C0*3?3Y3^3!3$3M0V3~3m403T040m0f3P1J311A2=2#0i2)3x0z222B0,1T1I300h323j4c4l0-4t462^010(120-0U4c3@4A0P3f4G3 4A0s0U1230220D2L4L4z2k11040d4V3,4N120S4#3x4Y0x3P0l3+3S120)4*3Z4Y0t0b3W0l4}4/4H3a120s4.4:3Z0p120N54503o0)122y4@404Y4!1B4u5b3K4(5g4A4_4|4~55474Q5a4M2k5704595k3u4 5y1?4Y0A0A5p2k0K0G124b5D2X5u5q120v5x4W1?5A0!5X4$5104535R3C5T2k4C040U3#5$4;040G5?564J5^5*335F5Y3K5d040X2e0Y0h5L5H125j355m3y52690}4_5W5+064~605%1?5/5;0X5`5v5^6u4A0p5|2`6x3a63650s676h015i6I0s6g5+5-6a044`5s6n4}6P0}6r5=5+6o5@0n6C5Z6A5~3j6#3Z0s6E66686O6e6K6?5G5n5)6I4_4{6l6U716-6v0c0r0G0r6%6!6W015A5C5 7b5N5P6T726V6e6Y6t7a6e6M040(6(0}6z126B7p6`3y6:6G6=6d7A6^7F616f6|6_7J6~7j7k6n7b7r7577797f6e7d7u7K7U787!5A0I7!7r4)7M6p6i125K7.5@5_7?4^5V7=7I7/7K7t7_5h5V7(125#7z7J7r4?815U047|5l7A7r807}4+7{6L127W8f7N83707Q7l8g5w8b4X7;8m6w8x6Q0v8e3u7S8n6}8r7X7A7Z877~7T767%8s8u7J5/2R0T0D0X6+5E8H040c3*0+4w4s4d8-0+4g1A0T4i8=2%2Z21232#0S1.8/4g1G4y7~2R0K0r0U0S0(0h0r0u0j121s1u1w1y0l6 351N3k1H0C0.0T1:980#1j0l2O4R0z0$0-0X2P2R2c1j2*0F0l0_9x0$2m0s2L0G9w19280$9T0G9i0l4R2I0L0$0h0Z0l0o0Q1/0l1y0T0l0T0p1h0h5;0G0?4l0O9s0D0L1:2o0l2H0$652M0?0b0l0K0D0Q0 0c1%0h9D0-0D0Jaa0S2$0G0z9j0z1a0X9%0?2O1S2A0s2K9w7b1a2L0u9T0h0J12090d0s090t4.0s0$aq0{2L1:0:aA0G0l9i0Q9i0?aD0XaFaHaJ04aL0s0g0jaO4.a4a69RaA0Z1J3k8: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 :Lp(40^ed3; 1j}o5_An)h]6,qc[yFCuvà8i2Dxms7=ûwlSatf-O{Rrg.TéPkbè/ 050j0i0X0W0K0U0P0m0B0U0W0P0P0R010X0K0d010406050P0G0O0O0W0%0D040V0q0U0G140q0u0m020W0O0d0l0m0$0i1e0%0A0G0i0P050:1b1d1f1h190d041F1M051P0:1P1R1M190j0K0H0|0~10120w0K0(0w0U1)0w0X17050@0.0U0i1!0 11011(1*1,1*0X1=1@1:0X0.0q0j1h1;0%1N0X0w0|1k0P0d0W0u120L011_1$010Y0_0i0u1s0i1:2h2j2o1{2r1@2u0O2w040a0m0,0%0q0d0q0P0K1n1p0=2f0%0%0i0B2R1F2y0u1N0:2d2%0X2b2a2c0j2A121,0u2t2O1:1X1Z0}1`2;0K2?0u271Y1:0d2W1N2#2%381a2i1p2|2p310%1e0U170n2!3c183b2z3e1{3g3i170L3m2j3o2#2:013t0W3j040k3x2$193A3r123D3F0f3I3z3c3B3O170r3R3K3T3M3C0q3h3E170y3Y3p3d1#3s3%3u040Q3,3L3/3N3;3)040J3R1O361F2`2*0j2.3B0B272G0;1Y1N350i373n40490=4h3q3`010-170=0Y403_2}010T170m4u3!4o0u0Y172+0K2j0(1@4B4n4w16040e4M3.4w0u170W4S3B4P0v0b3Y0m4(4A4v3f170u3R4*4C4w0q170R4/3-3U0.172D4Y3#4P4R1G4i4+3s4W4 4o4!4%4)4`3#4V040W0s0B1f2W4_55124?044^533y4:4N4,0435270G2Q584O17523a5n3C575s2$5d59170z5m4;5w4X5K4m4T2p5a5U064)5u5W1{4q040Y3%5Q5v56040K5-5%5o4y5:4.5U5$4{170%4J0i5C5X5E625/5`5G5R1{4!4$5Z5#5#5M4w5)5+0%5=3U170o6l3#0q5^2 6p4D4|045 0u0(615U6g634Q653N4-6G016b5b6e6e6D5(170K4t5{6P6H5g6J4P0C6J5f5;6C5H4P0x6!6(696W6o6-5.126*6u4=17020(0X0l6^2p0O0K170g6 1{6r4W0u0j756W5h5j2V6B686=6K176,7h5?5I5:6Y176+6#6n7q040x7b015p6{6}7y71737v6c385!6N7K4(6V4p5~0?0G0%673n5|3#0-0B170*0%1C6M7V4o5)2W0X7R7T5t7N7X170E3E0P7g3n190:4k4g417~0:441F0X46832,2(26282*0W1?80441L5V3B2W0O0s0Y0W0-0i0s0w0k171x1z1B1D0m7H4i1S3o1M0!1p0O1o2+1^8w0m0j2j0{0B1^5j0{2T2r0(7R0i0z0m1@2f0i0Y2r0B0K2t0X7(4w1f2Q0w1e0X0i0N17090e5h0#0K0z0o0p090v4/2T0~8-2p8/2d8=8@8_0e0-923R0Z0K0/2F0m0d5A102j8P8L1^968=0%0K9r0j000W0j0o0W8P0u9r1D8,0+0(3E0m0W0G0m310O0.2W9s0|0w1y2 8S9t1o8V0i7R971{998;0W8?8^048`9f935{2W1,2j8,1@0{0P0q1d0?9!9Q1c0+2L0{7N9,9b9:8`0K9g5{0?9*12aa9.9c9;0e0oaf380)1O8C040c8x0=0G0N9m2L350K0+0X0+0{0+1B1Y3E8+8x8)aGax8N8Z000+319G0+0m9 0u8,0j1o0B9N0G100K0maJ5A0HaMa#8x0I8Z0WaB2M9waFaY1baLa?8yat8g0_0m8@0K0P8?0m0G1p2 1X9ra99w9aalac0eae9@380m8?0U0m8K8!498$8(8*a#8L4I0(1o9Mbi8:ab9d0t0h0k0s8}8Y0K91bp7U0u009I9m0 a40U8YbHbk9/bKbMaq7U0jaH1)2ubB9u9.9wbh5Hakb)an0t0m09142F0{b~c00Kc20m0tb,3yas8B8g0F0?bb5yaDa~9QbWbabY0{1m0_b90+1^9xa-7eb70U8!0u0+8Pa,bbbw3E0B0Gbt2TayaA5y0j5A0Xa39v9xax8H8Z8Q0q0S8,bXc62N0%0@a#cc1V1Q040M1^1e0u9j9U0(aVa6aM8Y0P00b6b8ba1^bd0mbfcUai01b{amadca2$br0ibtbvcYbycv8+bC0WbE2ubtb%9-b|8`bL0ubO8~d5bS4/bVbX2i0{0ucJ8Y1o9m9(8,0W8%0K3h0i0%bu0Gc btd1bbd40B0D0}1^959$1C9)dsbJan0udd04c,3o810?0^0`04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)