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 v56bçolgmaEdt4Shs;jké.3q/[P_)^rC8eà:1û*(c7 u2wp]=09,ixyn+fR 050m0I0n0k0#0h0r0R0P0h0k0r0r0X010n0#0V010406050r0S0j0j0k0F0%040p0g0h0S0 0g0(0R020k0j0V0s0R0+0I190F0y0S0I0r050z16181a1c140V041A1H051K0z1K1M1H140m0#0b0@0_0{0}0q0#0i0q0h1!0q0n12050/0e0h0I1V0`0|011Z1#1%1#0n1-1/1+0n0e0g0m1c1,0F1I0n0q0@1f0r0V0k0(0}0T011;1X010*0;0I0(1n0I1+2c2e2j1?2m1/2p0j2r040a0R0B0F0g0V0g0r0#1i1k0-2a0F0F0I0P2M1A2t0(1I0z282Y0n2625270m2v0}1%0(2o2J1+1S1U0^1=2,0#2.0(221T1+0V2R1I2W2Y33152d1k2@2k2|0F190h120R0L2V3713362u391?3b3d3f0T3i2e3k2W2+013p0k3e040R0x3t2X143w3n0}3z3B0R0o3F3v373x3L3f0c3P3H3R3J3y0g3c3A3f0d3W3l381W3o3#3q3C0Q3*3I3-3K3/3%3C0H3?3Y3^3!3$3M0Z3~3m403T040L0Y3P1J311A2=2#0m2)3x0P222B0,1T1I300I323j4c4l0-4t462^010u120-0*4c3@4A0U3f4G3 4A0(0*1230220S2L4L4z2k11040O4V3,4N120k4#3x4Y0!3P0R3+3S120e4*3Z4Y0D0K3W0R4}4/4H3a120(4.4:3Z0g120X54503o0e122y4@404Y4!1B4u5b3K4(5g4A4_4|4~55474Q5a4M2k5704595k3u4 5y1?4Y0A0A5p2k0j0#124b5D2X5u5q120W5x4W1?5A0N5X4$5104535R3C5T2k4C040*3#5$4;040#5?564J5^5*335F5Y3K5d040F2e0i0I5L5H125j355m3y52690}4_5W5+064~605%1?5/5;0F5`5v5^6u4A0g5|2`6x3a63650(676h015i6I0(6g5+5-6a044`5s6n4}6P0}6r5=5+6o5@0t6C5Z6A5~3j6#3Z0(6E66686O6e6K6?5G5n5)6I4_4{6l6U716-6v0V0C0#0C6%6!6W015A5C5 7b5N5P6T726V6e6Y6t7a6e6M040u6(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;8m6w8x6Q0W8e3u7S8n6}8r7X7A7Z877~7T767%8s8u7J5/2R0n0S0F6+5E8H040V3*0z4w4s4d8-0z4g1A0n4i8=2%2Z21232#0k1.8/4g1G4y7~2R0j0C0*0k0u0I0C0q0x121s1u1w1y0R6 351N3k1H0G0.0n1:980f1j0R2O4R0P0v0-0F2P2R2c1j2*0J0R0_9x0v2m0(2L0#9w19280v9T0#9i0R4R2I0r0v0I0w0R0l0h1/0R1y0n0R0n0g1h0I5;0#0?4l0M9s0S0r1:2o0R2H0v652M0?0K0R0j0S0h0 0V1%0I9D0-0S0$aa0k2$0#0P9j0P1a0F9%0?2O1S2A0(2K9w7b1a2L0q9T0I0$12090O0(090D4.0(0vaq0{2L1:0:aA0#0R9i0h9i0?aD0FaFaHaJ04aL0(0E0xaO4.a4a69RaA0w1J3k8: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.128203 v56èbFolgmadt4{SDhs;jké.3q/_P[LO)-^rC8eà:1û(c7 u$2w}p]T=0,ixynfRA 050n0O0o0m0,0j0u0W0U0j0m0u0u0)010o0,0$010406050u0X0l0l0m0L0.040r0i0j0X160i0/0W020m0l0$0v0W0;0O1g0L0B0X0O0u050C1d1f1h1j1b0$041H1O051R0C1R1T1O1b0n0,0c0~1012140t0,0k0t0j1+0t0o19050_0g0j0O1$1113011*1,1.1,0o1@1_1=0o0g0i0n1j1?0L1P0o0t0~1m0u0$0m0/140Z011{1(010:0{0O0/1u0O1=2j2l2q1}2t1_2w0l2y040a0W0E0L0i0$0i0u0,1p1r0@2h0L0L0O0U2T1H2A0/1P0C2f2)0o2d2c2e0n2C141.0/2v2Q1=1Z1#0 1|2?0,2^0/291!1=0$2Y1P2%2)3a1c2k1r2~2r330L1g0j190R2$3e1a3d2B3g1}3i3k190Z3o2l3q2%2=013v0m3l040A3z2(1b3C3t143F3H0p3K3B3e3D3Q190d3T3M3V3O3E0i3j3G190e3!3r3f1%3u3)3w040V3.3N3;3P3?3+040N3T1Q381H2|2,0n2:3D0U292I0?1!1P370O393p424b0@4j3s3|010x190@0:423{2 010!190W4w3$4q0/0:192-0,2l0k1_4D4p4y18040T4O3:4y0/190m4U3D4R0I0Q3!0W4*4C4x3h190/3T4,4E4y0i190)4;3/3W0g192F4!3%4R4T1I4k4-3u4Y514q4$4)4+4|3%4X040m0D0U1h2Y4{57144^044`553A4=4P4.0437290X2S5a4Q19543c5p3E595u2(5f5b190+5o4?5y4Z5M4o4V2r5c5W064+5w5Y1}4s040:3)5S5x58040,5/5)5q4A5=4:5W5(4}190L4L0O5E5Z5G645;5|5I5T1}4$4(5#5%5%5O4y5+5-0L5@3W190w6n3%0i5`316r4F4~04610/0k635W6i654S673P4/6I016d5d6g6g6F5*190,4v5}6R6J5i6L4R0F6L5h5?6E5J4R0%6$6*6b6Y6q6/5:146,6w4@19020k0o0v6`2r0l0,190*711}6t4Y0/0n776Y5j5l2X6D6a6@6M196.7j5^5K5=6!196-6%6p7s040%7d015r6}6 7A73757x6e3a5$6P7M4*6X4r600^0X0L693p5~3%0x0U190(0L1E6O7X4q5+2Y0o7T7V5v7P7Z190h3G0u7i3p1b0C4m4i43800C461H0o48852.2*282a2,0m1^82461N5X3D2Y0l0D0:0m0x0O0D0t0A191z1B1D1F0W7J4k1U3q1O0H1r0l1q2-1`8y0W0n2l0}0U1`5l0}2V2t0k7T0O0+0W1_2h0O0:2t0U0,2v0o7*4y1h2S0t1g0o0O0-19090T5j0q0,0+0w0#090I4;2V108/2r8;2f8@8_8{0T0x943T0J0,0f2H0W0$5C122l8R8N1`988@0L0,9t0n000m0n0w0m8R0/9t1F8.0y0k3G0W0m0X0W330l0g2Y9u0~0t1A318U9v1q8X0O7T991}9b8?0m8^8`048|9h955}2Y1.2l8.1_0}0u0i1f0^9$9S1e0y2N0}7P9.9d9=8|0,9i5}0^9,14ac9:9e9?0T0wah3a0z1Q3q2|3D1 1-1/1;8j3%2E2v2x190b0W0(8_8^424h5X3b4k7 040G8z0@0X0-9o2N370,0y0o0y0}0y1D1!3G8-8z8+a)aW8P8#000y339I0y0Wa10/8.0n1q0U9P0X120,0Wa,5C0ca/b18z0P8#0ma!2O9ya(a~1da.bf8A06060{0W8_0,0u8^0W0X1r311Z9t0Y0,0Y0W8^0j0W8M8$4b8(8*8,b18N4K0k1q9O0Y0=0K0A0D8 8!0,0#bJ0/009K9o11a60j8!b!b$bJ0na*1+2wbU9w9:9ybG0=0W09162H0}c5c70,c90W0=0Y0zbt0M0^bA5Aa$bn9Sb/bzb;0}1o0{by0y1`9zb97gbw0j8$0/0y8Rb8bAbP3G0U0XbM2VaXaZ5A0n5C0oa59x9zaW8J8#8S0i0S8.b:cd2P0L0_b1ci060s1`1g0/9l9W0ka{a8a/8!0u00bvbxbz1`bC0WbEcZ0WbHbJbLbN1Ec$8%8)cA8-bV0mbX2wbMb_0/b(90d8b,cqb:2k0}0/cO8!1q9o9*8.0mdj3j0O0Ldfd2bMd4bAd70U0.0 1`979(1E9+0Y0/ch7}aT812)8h450^0`0|04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)