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 , w*5e(8CR0pkojicE6S1vqd:xy24flnçû]93m=)rh[us;^b/.àt_géaP+7 050y0g0!0(0q0F0T0c0r0F0(0T0T0N010!0q0m010406050T0S0M0M0(0P0B040u0o0F0S0 0o0G0c020(0M0m0U0c0k0g190P0x0S0g0T050X16181a1c140m041A1H051K0X1K1M1H140y0q0w0@0_0{0}0Q0q0$0Q0F1!0Q0!12050/0W0F0g1V0`0|011Z1#1%1#0!1-1/1+0!0W0o0y1c1,0P1I0!0Q0@1f0T0m0(0G0}0C011;1X010E0;0g0G1n0g1+2c2e2j1?2m1/2p0M2r040a0c0)0P0o0m0o0T0q1i1k0-2a0P0P0g0r2M1A2t0G1I0X282Y0!2625270y2v0}1%0G2o2J1+1S1U0^1=2,0q2.0G221T1+0m2R1I2W2Y33152d1k2@2k2|0P190F120c0v2V3713362u391?3b3d3f0C3i2e3k2W2+013p0(3e040c0L3t2X143w3n0}3z3B0c0D3F3v373x3L3f0f3P3H3R3J3y0o3c3A3f0t3W3l381W3o3#3q3C0+3*3I3-3K3/3%3C0i3?3Y3^3!3$3M0K3~3m403T040v0l3P1J311A2=2#0y2)3x0r222B0,1T1I300g323j4c4l0-4t462^010n120-0E4c3@4A0d3f4G3 4A0G0E1230220S2L4L4z2k11040h4V3,4N120(4#3x4Y0b3P0c3+3S120W4*3Z4Y0O0z3W0c4}4/4H3a120G4.4:3Z0o120N54503o0W122y4@404Y4!1B4u5b3K4(5g4A4_4|4~55474Q5a4M2k5704595k3u4 5y1?4Y0R0R5p2k0M0q124b5D2X5u5q120J5x4W1?5A0e5X4$5104535R3C5T2k4C040E3#5$4;040q5?564J5^5*335F5Y3K5d040P2e0$0g5L5H125j355m3y52690}4_5W5+064~605%1?5/5;0P5`5v5^6u4A0o5|2`6x3a63650G676h015i6I0G6g5+5-6a044`5s6n4}6P0}6r5=5+6o5@0p6C5Z6A5~3j6#3Z0G6E66686O6e6K6?5G5n5)6I4_4{6l6U716-6v0m0#0q0#6%6!6W015A5C5 7b5N5P6T726V6e6Y6t7a6e6M040n6(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;8m6w8x6Q0J8e3u7S8n6}8r7X7A7Z877~7T767%8s8u7J5/2R0!0S0P6+5E8H040m3*0X4w4s4d8-0X4g1A0!4i8=2%2Z21232#0(1.8/4g1G4y7~2R0M0#0E0(0n0g0#0Q0L121s1u1w1y0c6 351N3k1H0j0.0!1:980H1j0c2O4R0r0%0-0P2P2R2c1j2*0Z0c0_9x0%2m0G2L0q9w19280%9T0q9i0c4R2I0T0%0g0Y0c0s0F1/0c1y0!0c0!0o1h0g5;0q0?4l0I9s0S0T1:2o0c2H0%652M0?0z0c0M0S0F0 0m1%0g9D0-0S0Aaa0(2$0q0r9j0r1a0P9%0?2O1S2A0G2K9w7b1a2L0Q9T0g0A12090h0G090O4.0G0%aq0{2L1:0:aA0q0c9i0F9i0?aD0PaFaHaJ04aL0G0V0LaO4.a4a69RaA0Y1J3k8: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 ,è Ow5e(8CR0pkDojic6TS1vqA{d:xFy24fln-û]3m=)rh[u}s;^b/.àt_gLéaP7 050C0h0)0.0s0K0Y0d0t0K0.0Y0Y0R010)0s0n010406050Y0W0Q0Q0.0T0G040w0q0K0W140q0L0d020.0Q0n0Z0d0l0h1e0T0z0W0h0Y050$1b1d1f1h190n041F1M051P0$1P1R1M190C0s0y0|0~10120U0s0+0U0K1)0U0)17050@0#0K0h1!0 11011(1*1,1*0)1=1@1:0)0#0q0C1h1;0T1N0)0U0|1k0Y0n0.0L120H011_1$010J0_0h0L1s0h1:2h2j2o1{2r1@2u0Q2w040a0d0/0T0q0n0q0Y0s1n1p0=2f0T0T0h0t2R1F2y0L1N0$2d2%0)2b2a2c0C2A121,0L2t2O1:1X1Z0}1`2;0s2?0L271Y1:0n2W1N2#2%381a2i1p2|2p310T1e0K170x2!3c183b2z3e1{3g3i170H3m2j3o2#2:013t0.3j040P3x2$193A3r123D3F0I3I3z3c3B3O170g3R3K3T3M3C0q3h3E170u3Y3p3d1#3s3%3u040:3,3L3/3N3;3)040j3R1O361F2`2*0C2.3B0t272G0;1Y1N350h373n40490=4h3q3`010o170=0J403_2}010f170d4u3!4o0L0J172+0s2j0+1@4B4n4w16040i4M3.4w0L170.4S3B4P0S0D3Y0d4(4A4v3f170L3R4*4C4w0q170R4/3-3U0#172D4Y3#4P4R1G4i4+3s4W4 4o4!4%4)4`3#4V040.0*0t1f2W4_55124?044^533y4:4N4,0435270W2Q584O17523a5n3C575s2$5d59170b5m4;5w4X5K4m4T2p5a5U064)5u5W1{4q040J3%5Q5v56040s5-5%5o4y5:4.5U5$4{170T4J0h5C5X5E625/5`5G5R1{4!4$5Z5#5#5M4w5)5+0T5=3U170r6l3#0q5^2 6p4D4|045 0L0+615U6g634Q653N4-6G016b5b6e6e6D5(170s4t5{6P6H5g6J4P0V6J5f5;6C5H4P0O6!6(696W6o6-5.126*6u4=17020+0)0Z6^2p0Q0s170m6 1{6r4W0L0C756W5h5j2V6B686=6K176,7h5?5I5:6Y176+6#6n7q040O7b015p6{6}7y71737v6c385!6N7K4(6V4p5~0?0W0T673n5|3#0o0t170v0T1C6M7V4o5)2W0)7R7T5t7N7X170F3E0Y7g3n190$4k4g417~0$441F0)46832,2(26282*0.1?80441L5V3B2W0Q0*0J0.0o0h0*0U0P171x1z1B1D0d7H4i1S3o1M0e1p0Q1o2+1^8w0d0C2j0{0t1^5j0{2T2r0+7R0h0b0d1@2f0h0J2r0t0s2t0)7(4w1f2Q0U1e0)0h0E17090i5h0B0s0b0r0X090S4/2T0~8-2p8/2d8=8@8_0i0o923R0M0s0c2F0d0n5A102j8P8L1^968=0T0s9r0C000.0C0r0.8P0L9r1D8,0-0+3E0d0.0W0d310Q0#2W9s0|0U1y2 8S9t1o8V0h7R971{998;0.8?8^048`9f935{2W1,2j8,1@0{0Y0q1d0?9!9Q1c0-2L0{7N9,9b9:8`0s9g5{0?9*12aa9.9c9;0i0raf380%1O8C040,8x0=0W0E9m2L350s0-0)0-0{0-1B1Y3E8+8x8)aGax8N8Z000-319G0-0d9 0L8,0C1o0t9N0W100s0daJ5A0yaMa#8x0(8Z0.aB2M9waFaY1baLa?8yat8g0_0d8@0s0Y8?0d0W1p2 1X9ra99w9aalac0iae9@380d8?0K0d8K8!498$8(8*a#8L4I0+1o9Mbi8:ab9d0A0!0P0*8}8Y0s91bp7U0L009I9m0 a40K8YbHbk9/bKbMaq7U0CaH1)2ubB9u9.9wbh5Hakb)an0A0d09142F0{b~c00sc20d0Ab,3yas8B8g0k0?bb5yaDa~9QbWbabY0{1m0_b90-1^9xa-7eb70K8!0L0-8Pa,bbbw3E0t0Wbt2TayaA5y0C5A0)a39v9xax8H8Z8Q0q0N8,bXc62N0T0@a#cc1V1Q040p1^1e0L9j9U0+aVa6aM8Y0Y00b6b8ba1^bd0dbfcUai01b{amadca2$br0hbtbvcYbycv8+bC0.bE2ubtb%9-b|8`bL0LbO8~d5bS4/bVbX2i0{0LcJ8Y1o9m9(8,0.8%0s3h0h0Tbu0Wc btd1bbd40t0G0}1^959$1C9)dsbJan0Ldd04c,3o810?0^0`04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)