Aller au contenu

Recherche de circuits⚓︎

Chercher les circuits

Pour chercher les circuits, il est plus simple de faire un parcours en profondeur. C'est pourquoi nous privilégierons les parcours en profondeur récursifs.

Dans cette partie on considérera qu'un circuit est un chemin commençant et se terminant par le même sommet et ne contenant pas deux fois un autre sommet.

Par exemple si on a un circuit 0 -> 1 -> 2 -> 3 -> 0 et un circuit 2 -> 4 -> 5 -> 2, alors le chemin suivant, qui est valide, n'est pas un circuit : 0 -> 1 -> 2 -> 4 -> 5 -> 2 -> 3 -> 0.

Pour rappel, les graphes suivants sont déjà définis :

graphe1_dico = {
    0: [1, 2],
    1: [2],
    2: [0, 1],
    3: [1, 2]
    }


graphe2_dico = {
    0: [1, 2],
    1: [3],
    2: [8],
    3: [2, 4],
    4: [7],
    5: [0],
    6: [5],
    7: [5],
    8: [9],
    9: [2]
    }


graphe3_dico = {
    0: [1, 2, 3],
    1: [0, 3],
    2: [0, 3],
    3: [1]
    }


graphe4_dico = {
    0: [1, 3],
    1: [2],
    2: [7],
    3: [4],
    4: [6],
    5: [0],
    6: [2, 7],
    7: []
    }  


graphe5_dico = {
    0: [5, 7],
    1: [3],
    2: [0, 4],
    3: [2],
    4: [3],
    5: [],
    6: [5],
    7: [6]
    }
Exercice 16 : existence d'un circuit en partant d'un sommet

Compléter le code de la fonctionexiste_circuit_rec qui prend en paramètres un graphe sous forme de dictionnaire d'adjacence graphe, depart un sommet de graphe, et qui renvoie un booléen indiquant s'il y a un circuit en partant de depart.

La fonction a également un paramètre optionnel, etat, qui vaut None par défaut et sinon qui est un dictionnaire d'états des sommets de graphe

La fonction existe_circuit_rec parcourt le graphe en profondeur en partant de depart. Si on trouve un sommet qui est en attente, alors c'est qu'il y a un circuit.

Pour tester cette fonction, on peut regarder graphe2 dans lequel chaque sommet mène à un circuit, graphe4 où il n'y a aucun circuit et graphe5 où il y a un circuit si on part de 1, 2, 3 ou 4 mais pas des autres sommets.

Exemples
>>> existe_circuit_rec(graphe2_dico, 0)
True
>>> existe_circuit_rec(graphe2_dico, 6)
True
>>> existe_circuit_rec(graphe4_dico, 5)
False
>>> existe_circuit_rec(graphe5_dico, 1)
True
>>> existe_circuit_rec(graphe5_dico, 0)
False

Indications

On rappelle que lorsqu'on fait un parcours en profondeur, tous les sommets en attente forment un chemin depuis le premier sommet depart jusqu'au sommet courant. Si au cours de l'exploration on arrive sur un sommet en attente, c'est qu'on a trouvé un circuit.

Si on trouve un sommet traité, c'est qu'il ne mène pas à un circuit, sinon on aurait déjà renvoyé True. Ce n'est donc pas la peine de continuer à explorer à partir de là.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.12801348em&u6s9k]"v! r3(ntS)qf/5h[P}éi aN2podF=ycTl;,xb7_g:10{.w010F050m0A0y0L0a0h0J0L0A0a0a0H0e0m0y0D0e000z010a0806060A0i0I000n0E0L080;0E0l010r0{0}10120_0F0y0f0h0~0i0c0F0E0Y0l0/0U0e0h0a0m0I0L050/1m0S0y0l0T0U0X0Q05060h0U1L1v0^0Z1j0)0+0-0/0t0y0S0t0L1Z0t0m0@010$0P1A1U0,0.0e1Y1!1$1!0m1*1A1(0m0i001)0t0)150a0D0A1s0e0C1v0*1.0/0q0&050l0A06051(24261-1W0e2e1A2h2j0@020h0v0i0E0D0E0a0y180l0h0!220i0i050J2F1b2m0l1~0r0m0t2S1|1~2X1)0F2o1/1$0l2g2C1(1i1k2b2p2&2(2+1(0D2L1~2Q2S2_0`252G2-1/0l0E0i0~0L0@1N2P2}1R2Q2$0/32340A36000h0C39263b2}3d0e3f35370j3m2R0_3c303e333t3j033w3o2n3A3r3C3h370s3G3y3p3J3s3M3j093P2|3I1V313L3i0h0Q3X3z3!3B3g3%043(3R3*3K3,370b3/3Z2c3=3D0U0V3_2~3;3T3i0U0U3G1b2?052S2+2W0F2Y2#3J0J0E0!2*1j1~4a2^3a484j0!4q3`2p0c0@0!0q3G0h3Y423{0l0q0@050O0y1x050R0J0y0i0J082E0R2L0J483)3{0?000k4Z3:4G0@0S0i0A0D0t054'4w1/4$0N4C4E3q0l4z05250i0m4;4F2p4@4_4!2p4|000#0A521c4r581/0E0@0H533q0c0J0@0B194:5f3n4`3J4$0o0T3P0h5C4D5h0/4y000y4B5u2R5E4(594J0$5e2_5N4=0/1q0@4M575O1/5o5q5s5m5x0@5A5L0^5D5.5U54315Q5d5!5V0e5j005l5,5:3q4$0W5(430@0a0E0}0#644#5*5^5;0/0a2900070p080E0m0M250(0f086k6m6o6e5n0@0q336x3S66682j5S3a603J5X5I1a5~5w65004+4-4/6b550@0w5B5D6P3{5H5J6C6Q5c6H5v5F0e4$0u6V5=000!506*2R6#6W000d6'3{5{0H5}5T6`1/6h0@6u6n0M2g0h5d0m2g7f796w5,750/4$5+2_0z5/6!6,5H2L0m080i6N747t5p000K0i085t7p5.7l3r5?6^4v6f6-0@6/7k6,5a6?107N7K4$6}6O6,716~2p776j6l7a7c7e7g057i0M6Z5C7K5H6A0i7'6;0f0E4M1F7|5W0Y5Y7z6I7K5a6S4.7H5g5#7m7R6:3e4}6@8i7Q6|7o3a7q7r6J3;6%5K7A8f7L5b5R8m6.8m5a7~81876+8y7!835`0@0g73886,7)7;1|0%0m0x7;8M6L260F8M5a4K4M7f4P4R4T4V4X8C0@4&7T8y8a4,8c8:004^7$8@0@8G2D8I6_6,568~5_8'8B8?5_5y8p3n8r8s7s8y7u0#7x943j7^7C7E7G7?8t4)8A5@9c7P8D9z4{8k7X8{7#8x5_7&987P8T7+6o8V2E8Y9O7=5,9h9v4x0@7v9n8M5%000G3h0a8d9g1b4t4b492@1b4d1b0m4f9?1}9?0A1+9.0r4d0_a04na20!0$0&0a00
Exercice 17 : existence d'un circuit dans un graphe

Écrire le code de la fonction existe_circuit_profondeur qui prend en paramètre un graphe sous forme de dictionnaire d'adjacence graphe et qui renvoie un booléen s'il existe un circuit dans graphe.

La fonction existe_circuit_profondeur teste tous les sommets non encore vus en vérifiant s'ils mènent à un circuit ou pas.

On utilise la fonction existe_circuit_rec.

Exemples
>>> existe_circuit_profondeur(graphe2_dico)
True
>>> existe_circuit_profondeur(graphe4_dico)
False
>>> existe_circuit_profondeur(graphe5_dico)
True

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013,4ai(w3oSn s{lbthgp1kcd_;vqP62y.7 re5u}xm)&["Tf]:/=F010p0C0i05060g0e0A0o0g050e0e0R0L0i060l0L000d010e0E0H0H050B0x000b0a0g0E0+0a0c010Q0=0@0_0{0:0p060s0A0^0B0n0p0a080c0)0m0L0A0e0i0x0g0C0)1g0k060c0P0m0y0z0C0H0A0m1F1p0/0T1d0#0%0'0)0j060k0j0g1T0j0i0.010W0h1u1O0&0(0L1S1U1W1U0i1$1u1!0i0B001#0j0#0~0e0l051m0L0w1p0$1(0)0N0Y0C0c050H0C1!1}201'1Q0L281u2b2d0.020A0u0B0a0l0a0e06120c0A0U1{0B0B0C0o2z152g0c1^0Q0i0j2M1?1^2R1#0p2i1)1W0c2a2w1!1c1e252j2Y2!2%1!0l2F1^2K2M2:0;1~2A2'1)0c0a0B0^0g0.0m2J2@1L2K2W0)2{2}0530000w3320352@370L392~0.093f2L0:362_382|3m00043p3h2h3t3k3v3b0.0D3z3r3i3C3l3F000v3I2?3B1P2`3E3c0z3z152-0C2M2%2Q0p2S2V3C0o0a0U2$1d1^3!2/343Y3+0U3=3S260L0n0.0U0N3z0A3R2^3T380N0.0C0G061r0C0q0o060B0o0E2y0q2-0a0N130U0E0B3Y3s470L0-00074v3K4x0c0.0k0B050l0j0C4C3{2j4z0I0P3I0A4U444w3|4F000V050i43453j0a0.0R4&4X4P0.0f4N464Y0.0e0a0@0V4;3j4z4S16344W4D3|0e23000J0t0E0a0i0r1~0!0s0E595b5d4,542j3~004q4u513g534O2`4@4_2d4%5t2L5v4=2j1k0.1z5m5w384G4I4K4M5C3`5F1)4z0F4T4V4'3C5p5r5K5T5M004^4`5B2:5E4(085I145R5-3L0h0.4I0c0k5Q2=4-5U0.4B5R5Z4E5^002m4|3C4z635~5n5x004H4J4L6a4x4Q4R5X4V5Y600)5p06425=654?4!0W5+3?6s4y0.0K6l6z5)5A6I4.000O5%4(4*4+6x6E560.5j5c5e0&0A5h6Y5l646E4~6p6q6,6y5o5I6w5,6.6g4b4d0i4f4h4j4l0i0q2F0o6M614A745'6i5P776F00036Q3L5y5*7b4z7e6U6f5'4#6C3g6?0)4Q502:0d6,7y6-6E5p2F0i4t5;6=7B0o0.0M0B0E5}347x6r7n3}5_0V7F7f4x0n7J000S3b0e7O3g0:0Q3^3#3Z2.153%150i3'7;1@7;051%7,0Q3%7)7~7/4#0Y0e00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013.oy(FpgStmk_vue7]lP=,rT4hb{n sd&6)3fia/[:"2wc 5x1};q010x0h0b0E0D0k0w0v0L0k0E0w0w0m0I0b0D080I000M010w0g0c0c0E0o05000a040k0g0+040u010F0=0@0_0{0:0x0D0f0v0^0o0d0x040K0u0)0P0I0v0w0b050k0h0)1g090D0u0H0P030i0h0c0v0P1F1p0/0T1d0#0%0'0)0r0D090r0k1T0r0b0.010W0s1u1O0&0(0I1S1U1W1U0b1$1u1!0b0o001#0r0#0~0w080E1m0I0J1p0$1(0)0C0Y0h0u0E0c0h1!1}201'1Q0I281u2b2d0.020v0l0o0408040w0D120u0v0U1{0o0o0h0L2z152g0u1^0F0b0r2M1?1^2R1#0x2i1)1W0u2a2w1!1c1e252j2Y2!2%1!082F1^2K2M2:0;1~2A2'1)0u040o0^0k0.0P2J2@1L2K2W0)2{2}0E30000J3320352@370I392~0.0B3f2L0:362_382|3m000q3p3h2h3t3k3v3b0.0N3z3r3i3C3l3F000z3I2?3B1P2`3E3c0i3z152-0h2M2%2Q0x2S2V3C0L040U2$1d1^3!2/343Y3+0U3=3S260I0d0.0U0C3z0v3R2^3T380C0.0h0O0D1r0h0e0L0D0o0L0g2y0e2-040C130U0g0o3Y3s470I0-00064v3K4x0u0.090o0E080r0h4C3{2j4z0A0H3I0v4U444w3|4F000V0E0b43453j040.0m4&4X4P0.0t4N464Y0.0w040@0V4;3j4z4S16344W4D3|0w23000y0S0g040b0R1~0!0f0g595b5d4,542j3~004q4u513g534O2`4@4_2d4%5t2L5v4=2j1k0.1z5m5w384G4I4K4M5C3`5F1)4z0Q4T4V4'3C5p5r5K5T5M004^4`5B2:5E4(0K5I145R5-3L0s0.4I0u095Q2=4-5U0.4B5R5Z4E5^002m4|3C4z635~5n5x004H4J4L6a4x4Q4R5X4V5Y600)5p0D425=654?4!0W5+3?6s4y0.0G6l6z5)5A6I4.000j5%4(4*4+6x6E560.5j5c5e0&0v5h6Y5l646E4~6p6q6,6y5o5I6w5,6.6g4b4d0b4f4h4j4l0b0e2F0L6M614A745'6i5P776F000n6Q3L5y5*7b4z7e6U6f5'4#6C3g6?0)4Q502:0M6,7y6-6E5p2F0b4t5;6=7B0L0.0p0o0g5}347x6r7n3}5_0V7F7f4x0d7J00073b0w7O3g0:0F3^3#3Z2.153%150b3'7;1@7;0E1%7,0F3%7)7~7/4#0Y0w00
Représentation des circuits

Nous allons maintenant travailler à chercher les circuits présents dans les graphes. Les circuits seront représentés par des listes, comme les chemins, sauf que le permier élément et le dernier sont égaux.

Par exemple dans le graphe 2 il y a 2 circuits qui peuvent être représentés ainsi :

Représentations du premier circuit
[0, 1, 3, 4, 7, 5, 0]
[1, 3, 4, 7, 5, 0, 1]
[3, 4, 7, 5, 0, 1, 3]
[4, 7, 5, 0, 1, 3, 4]
[7, 5, 0, 1, 3, 4, 7]
[5, 0, 1, 3, 4, 7, 5]
Représentations du second circuit
[2, 8, 9, 2]
[8, 9, 2, 8]
[9, 2, 8, 9]

Toutes les représentations de chaque circuit sont équivalentes.

Nous n'avons pas le cas dans les exemples, mais le plus petit circuit possible correspond à un sommet qui aurait un arc pointant sur lui-même. On obtiendrait alors un circuit [sommet, sommet], où sommet est un sommet du graphe.

Nous allons commencer par écrire plusieurs fonctions qui nous servirons pour la suite.

Exercice 18 : extraire un circuit à la fin d'un chemin

Écrire le code de la fonction extrait_circuit qui prend en paramètre une liste chemin correspondant à un chemin et qui renvoie la fin de la liste correspondant à un circuit. On suppose que le chemin donné contient bien un circuit.

Exemples
>>> extrait_circuit([0, 5, 2, 1, 3, 0])
[0, 5, 2, 1, 3, 0]
>>> extrait_circuit([5, 1, 3, 4, 3])
[3, 4, 3]
>>> extrait_circuit([6, 2, 9, 4, 1, 8, 8])
[8, 8]
Indications

Il faut parcourir le chemin et commercer à rajouter des éléments dès qu'on est arrivé à un sommet égal au dernier de chemin. Quand on a commencé à rajouter des sommets, il faut continuer jusqu'à la fin.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013[ig 250Pte(n/Smplfxdws4k -=.6)vo3h1r];y7&uab"c_:010m0c0b0J040j0o0r0M0j0J0o0o0t0L0b040i0L0006010o0I0h0h0J0C0F000g0y0j0I0'0y0e010f0.0:0=0@0,0m040x0r0;0C0q0m0y0n0e0%0B0L0r0o0b0F0j0c0%1c05040e0O0B0u0G0c0h0r0B1B1l0+0P190X0Z0#0%0A04050A0j1P0A0b0*010S0K1q1K0!0$0L1O1Q1S1Q0b1Y1q1W0b0C001X0A0X0`0o0i0J1i0L071l0Y1$0%0k0U0c0e0J0h0c1W1_1{1#1M0L241q27290*020r0a0C0y0i0y0o040}0e0r0Q1@0C0C0c0M2v112c0e1;0f0b0A2I1/1;2N1X0m2e1%1S0e262s1W181a212f2U2W2Z1W0i2B1;2G2I2,0-1`2w2#1%0e0y0C0;0j0*0B2F2:1H2G2S0%2@2_0J2{00072~1{312:330L352`0*0z3b2H0,322=342^3i000p3l3d2d3p3g3r370*083v3n3e3y3h3B000v3v112)0c2I2Z2M0m2O2R3y0M0y0Q2Y191;3O2+303M3X0Q3&3x1L1%0q0*0Q0k3v0r2/3,223g0k0*0c0l1/0T0b0N0M040C0M0I2u3M3o3-0%0)000d4b3G4d3g0*0M0A1B1v4i3_2f4f0w0O3E0r4y3@4c3`0e4m46484a12304A4j3`0y0*0t3?3^2;4k4f030D4x4z4R3f3/000k2^4Q4B2f4D000o0y0:0R4'4L2f1g0*4q4I3c4K4s2?4m4o0h4^2.4(1%4f4w4_3m4z5a4{4S3`4#043=58005c3f0e0K0*2i4r5d4t0*4h5i4Z3H4E47490b5q3f4u4:4|0%4N000H050b0E5F5r1%510*095O3f4?004&5i5k5x4+4-295B5Z5w4k5I0t4P5(54344~4p105v5/0L4U5C3y5I0s5{4k5R002}5@4;550*0D572,065b6d5!4k4*455z4H53665H0*0u604C0*0J0i0i260m6q5s4g6y4}5$4.5'6l5G5_0*0w4X4y5)5e0*2B0b0I0C5?2,6f6r006i4G6F300,0f3)3P3N2*113R110b3T6-1:6-0J1Z6(0f3R6%6`6+0R0T0V00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013w1txbkamhu;( o)"=-gyr5dlpSc:n0is_327[ 4/P&.]ve6f010p0M05090x0q0y0f0t0q090y0y0j0i050x0r0i000E010y0c0a0a090n0m000s0g0q0c0'0g0v010G0.0:0=0@0,0p0x0L0f0;0n080p0g030v0%040i0f0y050m0q0M0%1c0l0x0v0u040J0C0M0a0f041B1l0+0P190X0Z0#0%0b0x0l0b0q1P0b050*010S071q1K0!0$0i1O1Q1S1Q051Y1q1W050n001X0b0X0`0y0r091i0i0B1l0Y1$0%0O0U0M0v090a0M1W1_1{1#1M0i241q27290*020f0H0n0g0r0g0y0x0}0v0f0Q1@0n0n0M0t2v112c0v1;0G050b2I1/1;2N1X0p2e1%1S0v262s1W181a212f2U2W2Z1W0r2B1;2G2I2,0-1`2w2#1%0v0g0n0;0q0*042F2:1H2G2S0%2@2_092{000B2~1{312:330i352`0*0A3b2H0,322=342^3i000F3l3d2d3p3g3r370*0o3v3n3e3y3h3B000N3v112)0M2I2Z2M0p2O2R3y0t0g0Q2Y191;3O2+303M3X0Q3&3x1L1%080*0Q0O3v0f2/3,223g0O0*0M061/0T050z0t0x0n0t0c2u3M3o3-0%0)000e4b3G4d3g0*0t0b1B1v4i3_2f4f0h0u3E0f4y3@4c3`0v4m46484a12304A4j3`0g0*0j3?3^2;4k4f0D0K4x4z4R3f3/000O2^4Q4B2f4D000y0g0:0R4'4L2f1g0*4q4I3c4K4s2?4m4o0a4^2.4(1%4f4w4_3m4z5a4{4S3`4#0x3=58005c3f0v070*2i4r5d4t0*4h5i4Z3H4E4749055q3f4u4:4|0%4N000I0l050d5F5r1%510*0w5O3f4?004&5i5k5x4+4-295B5Z5w4k5I0j4P5(54344~4p105v5/0i4U5C3y5I0k5{4k5R002}5@4;550*0K572,0E5b6d5!4k4*455z4H53665H0*0J604C0*090r0r260p6q5s4g6y4}5$4.5'6l5G5_0*0h4X4y5)5e0*2B050c0n5?2,6f6r006i4G6F300,0G3)3P3N2*113R11053T6-1:6-091Z6(0G3R6%6`6+0R0T0V00
Exercice 19 : tester si un circuit est valide

Écrire le code de la fonction circuit_valide qui prend en paramètres un dictionnaire graphe représentant un graphe et circuit, une liste de sommets, et qui renvoie un booléen indiquant si circuit correspond bien à un circuit de graphe.

Exemples
>>> circuit_valide(graphe1_dico, [0, 1, 2, 0])
True
>>> circuit_valide(graphe1_dico, [1, 2, 1])
True
>>> circuit_valide(graphe2_dico, [9, 2, 8, 9])
True
>>> circuit_valide(graphe4_dico, [6, 2, 7, 2])
False
>>> circuit_valide(graphe5_dico, [6, 5, 0, 6])
False
>>> circuit_valide(graphe5_dico, [2, 4, 485, 3, 2])
False
Indications

Pour qu'un circuit soit valide, il faut :

  • qu'il ait au moins 2 sommets ;
  • que le premier sommet soit égal au dernier ;
  • que pour tout couple de sommets consécutifs s1 et s2 dans le circuit sont tels que s2 est un voisin de s1.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013iuf!pv31_&-;[+4dgT0:o]r /PhslFmb" nw.S57e=(t,k)cy6a2010i0H0K0R030v0u0q0O0v0R0u0u0I0z0K03070z000A010u040x0x0R0p0P000E0n0v040+0n0B010r0=0@0_0{0:0i03080q0^0p0M0i0n0C0B0)0a0z0q0u0K0P0v0H0)1g0j030B0m0a0D0G0H0x0q0a1F1p0/0T1d0#0%0'0)0t030j0t0v1T0t0K0.010W0y1u1O0&0(0z1S1U1W1U0K1$1u1!0K0p001#0t0#0~0u070R1m0z0S1p0$1(0)050Y0H0B0R0x0H1!1}201'1Q0z281u2b2d0.020q0s0p0n070n0u03120B0q0U1{0p0p0H0O2z152g0B1^0r0K0t2M1?1^2R1#0i2i1)1W0B2a2w1!1c1e252j2Y2!2%1!072F1^2K2M2:0;1~2A2'1)0B0n0p0^0v0.0a2J2@1L2K2W0)2{2}0R30000S3320352@370z392~0.093f2L0:362_382|3m000h3p3h2h3t3k3v3b0.0F3z3r3i3C3l3F000Q3I2?3B1P2`3E3c0G3z152-0H2M2%2Q0i2S2V3C0O0n0U2$1d1^3!2/343Y3+0U3=3S260z0M0.0U053z0q3R2^3T38050.0O030p0O042y0b083b030U3Y3s470z0-000J4m3K4o0B0.0j0p0R070t0H4t3{2j4q0L43453j4w004b4d4f0K4E463|4q0N0m3I0q4Z444n3|3~00034216344#4u3|0B0y0.2m4S3j4q4s4*3g4K3L4a4c4e2y4?3C4V4J4$2j0n0.0c0v0K0e0I564-2j0x03315g4F1)1k0.2|5m4T2j4M4O514R4`2L4|4o4q0f534o5j0.0l5F4U0.0o5s3j5900065f5z004,5n384~4P525U5B5L005E5$575o0.0d5K5i5k00325)5h1)4q0o4X5U0A4!5~5W5t1)4&2F0K040p145U613j0M0O0.0w3b0u4D5|5~5%2j4&055r6a6m2`0.035O3C5p4'692:6b3L4:004z0B0j6j2=5*0)4^5.2`6E4=5?5X4p0.4_6K5@5Y4N504Q6O6M0.0N6%0z5Q5-6S621w5:5=6X6T4V5{2:5}604Z6s0)4&4(6w4v5Z5x6)5D6)4M6v6-4@5M723|6y2{5y6B6}6*0C6u6A4+7k4M4y4A4C7e587m006q7j6L3k746$7b540.5(6=6.7C4'6)5Q0g6)5H5;767d6r7B7g0n7i7p7W7x1z7v6t007s4B6J3?7B777F736!5!7Z4{7-7H786u7T000o5`4Y6{607k640V677o3g6C4o6d6f6h7+3g6`6|7B8566687&6~6e000k0p048f3q153^3#3Z2.153%150K3'8D1@8D0R1%8y0r3%0:8M3/8O0U0W0Y0u00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280136elinshb[(1dm;5+!ypT0:fr .vkF34=o27w,_/tc"PSga]u&-) 010e040G0M0605080r0H050M08080y0I0G060l0I000S01080O0f0f0M0q0k000K0z050O0+0z07010F0=0@0_0{0:0e060t0r0^0q0u0e0z0C070)0d0I0r080G0k05040)1g0L06070o0d0s0B040f0r0d1F1p0/0T1d0#0%0'0)09060L09051T090G0.010W0a1u1O0&0(0I1S1U1W1U0G1$1u1!0G0q001#090#0~080l0M1m0I0A1p0$1(0)0p0Y04070M0f041!1}201'1Q0I281u2b2d0.020r0J0q0z0l0z080612070r0U1{0q0q040H2z152g071^0F0G092M1?1^2R1#0e2i1)1W072a2w1!1c1e252j2Y2!2%1!0l2F1^2K2M2:0;1~2A2'1)070z0q0^050.0d2J2@1L2K2W0)2{2}0M30000A3320352@370I392~0.0w3f2L0:362_382|3m000x3p3h2h3t3k3v3b0.0h3z3r3i3C3l3F00033I2?3B1P2`3E3c0B3z152-042M2%2Q0e2S2V3C0H0z0U2$1d1^3!2/343Y3+0U3=3S260I0u0.0U0p3z0r3R2^3T380p0.0H060q0H0O2y0E0t3b060U3Y3s470I0-000c4m3K4o070.0L0q0M0l09044t3{2j4q0D43453j4w004b4d4f0G4E463|4q0R0o3I0r4Z444n3|3~00064216344#4u3|070a0.2m4S3j4q4s4*3g4K3L4a4c4e2y4?3C4V4J4$2j0z0.0P050G0g0y564-2j0f06315g4F1)1k0.2|5m4T2j4M4O514R4`2L4|4o4q0b534o5j0.0n5F4U0.0N5s3j59000j5f5z004,5n384~4P525U5B5L005E5$575o0.0Q5K5i5k00325)5h1)4q0N4X5U0S4!5~5W5t1)4&2F0G0O0q145U613j0u0H0.0v3b084D5|5~5%2j4&0p5r6a6m2`0.065O3C5p4'692:6b3L4:004z070L6j2=5*0)4^5.2`6E4=5?5X4p0.4_6K5@5Y4N504Q6O6M0.0R6%0I5Q5-6S621w5:5=6X6T4V5{2:5}604Z6s0)4&4(6w4v5Z5x6)5D6)4M6v6-4@5M723|6y2{5y6B6}6*0C6u6A4+7k4M4y4A4C7e587m006q7j6L3k746$7b540.5(6=6.7C4'6)5Q0i6)5H5;767d6r7B7g0z7i7p7W7x1z7v6t007s4B6J3?7B777F736!5!7Z4{7-7H786u7T000N5`4Y6{607k640V677o3g6C4o6d6f6h7+3g6`6|7B8566687&6~6e000m0q0O8f3q153^3#3Z2.153%150G3'8D1@8D0M1%8y0F3%0:8M3/8O0U0W0Y0800
Exercice 20 : trouver un circuit accessible à partir d'un sommet

Écrire le code de la fonction trouve_circuit_rec qui prend en paramètre un dictionnaire graphe représentant un graphe et un sommet depart, et qui renvoie un circuit de graphe accessible depuis depart ou la liste vide s'il n'y en a pas. Un circuit peut ne pas être accessible depuis n'importe quel sommet.

Il y a également deux paramètres optionnels : etat, correspondant à l'état des sommets et chemin qui est la liste des sommets permettant d'aller à depart.

Par exemple dans le graphe 5, le circuit n'est pas accessible en partant de 0.

Exemples
>>> trouve_circuit_rec(graphe2_dico, 2)
[2, 8, 9, 2]
>>> trouve_circuit_rec(graphe2_dico, 6)
[2, 8, 9, 2]
>>> trouve_circuit_rec(graphe1_dico, 1)
[1, 2, 0, 1]
>>> trouve_circuit_rec(graphe4_dico, 5)
[]
>>> trouve_circuit_rec(graphe5_dico, 0)
[]
>>> trouve_circuit_rec(graphe5_dico, 1)
[3, 2, 4, 3]
Explications de l'algorithme
  • Si on n'a pas défini etat et chemin, on les initialise.
  • On rajoute le depart au chemin.
  • Si on est sur un sommet en attente, c'est que le chemin se termine par un circuit. On renvoie donc le circuit extrait de chemin.
  • Sinon on met le sommet à en attente puis on parcourt chacun de ses voisins.
    • Si le voisin n'a pas été traité, on regarde s'il mène à un circuit.
    • Si c'est le cas, on renvoie vrai.
  • Si à la fin on n'a pas trouvé de circuit, on marque le sommet comme traité et on l'enlève de la fin du chemin. On renvoie alors une lite vide.

⚠ Selon la façon dont le parcours est réalisé vous pouvez ne pas forcément obtenir le même circuit ou au moins obtenir un circuit partant d'un autre sommet.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013Sp;i_8w0hl=547"&qr!,dé: [.ng6e]v/xP)tycf(m oaN92bsu31{}k010n0w0D0L060c0Q0q0F0c0L0Q0Q0d0h0D06040h000J010Q0R0I0I0L0k0E00030K0c0R0/0K0t010z0_0{0}100@0n060y0q0|0k0W0n0K090t0-0T0h0q0Q0D0E0c0w0-1k0u060t0p0T0s0g0w0I0q0T1J1t0?0X1h0'0)0+0-0b060u0b0c1X0b0D0=010!0P1y1S0*0,0h1W1Y1!1Y0D1(1y1&0D0k001'0b0'130Q040L1q0h0O1t0(1,0-0G0$0w0t0L0I0w1&22241+1U0h2c1y2f2h0=020q0B0k0K040K0Q06160t0q0Y200k0k0w0F2D192k0t1|0z0D0b2Q1`1|2V1'0n2m1-1!0t2e2A1&1g1i292n2$2&2)1&042J1|2O2Q2@0^232E2+1-0t0K0k0|0c0=1L2N2{1P2O2!0-30320L34000q0O3724392{3b0h3d33350S3k2P0@3a2}3c313r3h0f3u3m2l3y3p3A3f350e3E3w3n3H3q3K3h0v3N2`3G1T2~3J3g0q0g3V3x3Y3z3e3#083&3P3(3I3*350N3-3X2a3:3B0T0a3@2|3/3R3g0T0T3~3o420=0T3j1a383O3^2n48000T3t4c3l4e403_4h0T3D4l3v3W4o4g3!493M4t3F4w3Z3;4i3U4B4n474y4i3%4B192;0w2Q2)2U0n2W2Z3H0F0K0Y2(1h1|4Q2?383E014Z0Y4(4f1-0W0=0Y0G3E0q4v470G0=1`0K0R0y0w070F060k0F0R2C072J0F4*3'3_0;000H5e3.4p0=0u0k0L040b0w5k4/0-5h0m4^4`3Q4=0w230k0D5u4D5w0=5y4B4_5f4g0=0Z0L5G4O5O1-0K0=0d5H3o0W0F0=0M175t5U5l2n5x5z5V3c0=0F5s0I1D5!3H5X005Z5*5v0h5$5&5(5_3/5h0C0p3N0q6b5N5+4:0=064@5M5A415;5?5^6j5/0h1o6g0Q5.6e0-62005'2%655g0=694I6c6H6d600t6m1J6o2@6J5I6r5Y6v605h0r0x6a6c6k3_4;006h6U6R6L005R5T6P6#2n6s6&6u6p6w615%6z645~6R5h6F2@0J6I6!6q6*6,6(3o5{5}6.6q5h0U6C5P000Q0K0{0Z7h1-70793H0Q27000i0j0R0K0D05230&0y0R7w7y7A7r3/6%0G317J5m7j7l2h6-386Q7a096g186@6K5n5p5r5)2_7e0=0V6Z6b6/2~6M5@7Z7(6^5{0s7o5:005q042e0n7`0h5h5j6}475C5E7T3l7.5J000C7,7V3H6%6'7!6)5Q0!8a2P8c830=0r826*0Y89825h6Y8l7a5Y7c7U8r7t0=7G7z052e0q5S0D2e8Q8K7I863H7q6G748h7K0=2J0D0R0k7=8G765Q0A1`0#0D5456582C8z0=857?7#005=6N8)8b7)8e8g8r778o8^008u8V6l008x0}8p4.6~0=8B7d7@6T8C7s7u8T8M2E8P8R0w9s956q7L7N9p9d0y0K062B912P8!3_6;6O8*6^6*5o5q5s999b8{8m9e5D9g990x714d8Z9L2n8j6i9m8|789c6D9a8v0=9F9H9O926^8A7O6:0=0l8F3l9)1-8I7v7x8L8.2C0o9y9:5,6E8g9(965;8=599ha50-7b9~7/004~51535557an5b2K998`4)8+009S7&995L9-9Y9^9IaKas7{9/9X3o5-9D7P8~7;998f8Y9(7-9A6g9,9P6K0P0=2qaD9?8}am8@af7p0=a$aM8D7v0u8Ua|3H5@0=3}a^8d9&4ma&8Z8r6%8%8'9J3haka=aza@726HbjaTaF9|8ta;9f5F9$aR6S5|bya79sab0Dada9b19'759Q7:9`8q6q7^a;2z04aDa{bJa'6^be0Zbgby6W9l4d194,4R4P2=194T190D4Vb/1{b/0L1)b*0z4T0@b{4%b}0Y0!0$0Q00
Exercice 21 : trouver un circuit quelconque dans un graphe

Écrire le code de la fonction trouve_circuit_profondeur qui prend en paramètre un dictionnaire graphe correspondant à un graphe et qui renvoie un circuit qu'il contient ou la liste vide s'il n'y en a pas.

Exemples
>>> trouve_circuit_profondeur(graphe1_dico)
[0, 1, 2, 0]
>>> trouve_circuit_profondeur(graphe2_dico)
[2, 8, 9, 2]
>>> trouve_circuit_profondeur(graphe3_dico)
[0, 1, 0]
>>>  trouve_circuit_profondeur(graphe4_dico)
[]
>>> trouve_circuit_profondeur(graphe5_dico)
[3, 2, 4, 3]

⚠ Selon le parcours réalisé, le résulat peut être un autre circuit du graphe ou une autre représentation du même circuit.

Indication sur l'algorithme

On teste les sommets un par un en cherchant s'ils permettent de mener à un circuit ou pas.

Si on n'en trouve pas, on renvoie la liste vide.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013pP8ie[_oS)rqun=lm&64 t]wd2h;k703(/c}."sb1,v:g{ya5 f010r070o0O060i0F0Q0B0i0O0F0F0h0E0o06030E000n010F0f0j0j0O0d0N000b0a0i0f0*0a0g010A0;0?0^0`0/0r060J0Q0@0d0v0r0a0q0g0(0H0E0Q0F0o0N0i070(1f0L060g0K0H0D0w070j0Q0H1E1o0.0S1c0!0$0&0(0t060L0t0i1S0t0o0-010V0G1t1N0%0'0E1R1T1V1T0o1#1t1Z0o0d001!0t0!0}0F030O1l0E0s1o0#1'0(0R0X070g0O0j071Z1|1~1&1P0E271t2a2c0-020Q040d0a030a0F06110g0Q0T1`0d0d070B2y142f0g1@0A0o0t2L1=1@2Q1!0r2h1(1V0g292v1Z1b1d242i2X2Z2$1Z032E1@2J2L2/0:1}2z2&1(0g0a0d0@0i0-0H2I2?1K2J2V0(2`2|0O2~000s321~342?360E382}0-0y3e2K0/352^372{3l000m3o3g2g3s3j3u3a0-0P3y3q3h3B3k3E000l3H2=3A1O2_3D3b0w3P3r3S3t393b053y142,072L2$2P0r2R2U3B0B0a0T2#1c1@3(2.333&3;0T3{3R250E0v0-0T0R3y0Q3Q2@3Z3j0R0-1=0a0f0J07090B060d0B0f2x092,0a0R120T0f0d3&3Y430,000z4B3J4d0g0-0L0d0O030t074H422i4E0c0K3H0Q4Z4a4C2i4K000U0O0o494b3i0a0-0h4+4$1(4E0M4S4c434&0F0a0?0U4_3i4E4X15334#4I430F22000k0e0f0a0o0u1}0Z0J0f5e5g5i4;592i45004w4A563f584T2_0-4}504*5y2K5A4`2i1j0-1y5r5B374L4N4P4R5H415K4?0-0C4Y4!4,3B5u5w5P5Y5R005E2c5G2/5J4-0q5N135W5=3K5S4O4Q523B545$4!5%4=0(5u06485`5&4J0-4(5:3|670E4E08616e5-4~5/6n4D0-0p5*4-4/4:6c6j5b0-5o5h5j0%0Q5m6E5q5W6d6t00552/0n656T665s5C004n4p4r6h5z6N5L4/6w5|004h4j4l6Z4q4s2E0B6s4U0-4G6M6j4&4M5~5V2;6j4E0I6)6o5.516{6W0(74764{6f0V6$2K6&5Z000c646U6V5Q445N6b5;7k370G0-2l6@7l6`727b3j0-6/6#7B7c0-7n6A7F4.5d0L6L7v6j0j060-0x7K6k0-6Q336S7p7(7w7s002E0o4z5_7U7F4&7I2x7o7*5u7-7/7e6^00086v5W0/0A3~3)3'2-143+140o3-8d1?8d0O1$880A3+858n8b4(0X0F00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280135;3(4)yfqov}Pw rb"nt07p{81&[c_,2]Skg./=ulis:a6demh 010N0O0m0L0I0H0J0h0v0H0L0J0J0F0k0m0I0p0k000R010J0G0P0P0L0i09000A0c0H0G0*0c0l010E0;0?0^0`0/0N0I0d0h0@0i0B0N0c0g0l0(0s0k0h0J0m090H0O0(1f0C0I0l0K0s0D0o0O0P0h0s1E1o0.0S1c0!0$0&0(0Q0I0C0Q0H1S0Q0m0-010V0j1t1N0%0'0k1R1T1V1T0m1#1t1Z0m0i001!0Q0!0}0J0p0L1l0k0y1o0#1'0(0a0X0O0l0L0P0O1Z1|1~1&1P0k271t2a2c0-020h0f0i0c0p0c0J0I110l0h0T1`0i0i0O0v2y142f0l1@0E0m0Q2L1=1@2Q1!0N2h1(1V0l292v1Z1b1d242i2X2Z2$1Z0p2E1@2J2L2/0:1}2z2&1(0l0c0i0@0H0-0s2I2?1K2J2V0(2`2|0L2~000y321~342?360k382}0-053e2K0/352^372{3l00073o3g2g3s3j3u3a0-033y3q3h3B3k3E000M3H2=3A1O2_3D3b0o3P3r3S3t393b0r3y142,0O2L2$2P0N2R2U3B0v0c0T2#1c1@3(2.333&3;0T3{3R250k0B0-0T0a3y0h3Q2@3Z3j0a0-1=0c0G0d0O0w0v0I0i0v0G2x0w2,0c0a120T0G0i3&3Y430,00064B3J4d0l0-0C0i0L0p0Q0O4H422i4E080K3H0h4Z4a4C2i4K000U0L0m494b3i0c0-0F4+4$1(4E0q4S4c434&0J0c0?0U4_3i4E4X15334#4I430J22000t0b0G0c0m041}0Z0d0G5e5g5i4;592i45004w4A563f584T2_0-4}504*5y2K5A4`2i1j0-1y5r5B374L4N4P4R5H415K4?0-0e4Y4!4,3B5u5w5P5Y5R005E2c5G2/5J4-0g5N135W5=3K5S4O4Q523B545$4!5%4=0(5u0I485`5&4J0-4(5:3|670k4E0u616e5-4~5/6n4D0-0z5*4-4/4:6c6j5b0-5o5h5j0%0h5m6E5q5W6d6t00552/0R656T665s5C004n4p4r6h5z6N5L4/6w5|004h4j4l6Z4q4s2E0v6s4U0-4G6M6j4&4M5~5V2;6j4E0x6)6o5.516{6W0(74764{6f0V6$2K6&5Z0008646U6V5Q445N6b5;7k370j0-2l6@7l6`727b3j0-6/6#7B7c0-7n6A7F4.5d0C6L7v6j0P0I0-0n7K6k0-6Q336S7p7(7w7s002E0m4z5_7U7F4&7I2x7o7*5u7-7/7e6^000u6v5W0/0E3~3)3'2-143+140m3-8d1?8d0L1$880E3+858n8b4(0X0J00
Équivalences de circuits

Afin de pouvoir tester les résultats du dernier exercice de cette partie, il faut définir des fonctions permettant de comparer des circuits et des listes de circuits.

Exercice 22 : équivalence de deux circuits

Écrire le code de la fonction circuits_equivalents qui prend en paramètres deux listes qui correspondent à des circuits et qui renvoit un booléen indiquant si ce sont deux représentations du même circuit. On ne vérifiera pas si les circuits sont valides ou pas.

On rappelle que [1, 2, 3, 4, 1] est équivalent à [2, 3, 4, 1, 2] ou à [3, 4, 1, 2, 3].

Par contre, ils ne sont pas équivalents à [1, 4, 3, 2, 1].

Exemples
>>> circuits_equivalents([1, 2, 1], [2, 1, 2])
True
>>> circuits_equivalents([1, 2, 3, 4, 5, 6, 7, 8, 1], [4, 5, 6, 7, 8, 1, 2, 3, 4])
True
>>> circuits_equivalents([4, 7, 4], [4, 7, 4])
True
>>> circuits_equivalents([6, 3, 5, 6], [6, 5, 3, 6])
False
Explications de l'algorithme

Pour que deux circuits soient équivalents, il faut déjà qu'ils aient la même longueur.

Ensuite, puisque le dernier élément d'un circuit correspond au premier, on peut l'ignorer dans les deux listes.

On commence par chercher l'indice du premier élément de circuit1 qui correspond au premier de circuit2.

S'il n'existe pas, alors les deux circuits ne sont pas équivalents.

Sinon, on parcourt les éléments de circuit2 (sauf le dernier) tout en vérifiant qu'il y a bien une correspondance avec les éléments de circuit1. Une fois arrivé à l'avant-dernier élément de circuit1, il faut bien penser à revenir au premier pour pouvoir continuer.

Indication pour les indices de circuit1

Si i1 est l'indice du premier élément de circuit1 égal à circuit2[0], alors i1+i2 est l'indice de l'élément de circuit1 qui doit être égal avec celui de circuit2 d'indice i2.

Sauf qu'il bien faire attention parce que i1+i2 peut ne pas être un indice de circuit1...

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013&)t3+_4":9=q21S5%e[bsTn/8gp06c;d ik( h-]muvwyrla.7f!oFP,010y0k050O0A0N0n0z0w0N0O0n0n0d0a050A0t0a000D010n0I0H0H0O0M0L000h0T0N0I0/0T0p010q0_0{0}100@0y0A0J0z0|0M0B0y0T0K0p0-0g0a0z0n050L0N0k0-1k0s0A0p0b0g0P0Q0k0H0z0g1J1t0?0X1h0'0)0+0-0E0A0s0E0N1X0E050=010!0m1y1S0*0,0a1W1Y1!1Y051(1y1&050M001'0E0'130n0t0O1q0a0f1t0(1,0-0R0$0k0p0O0H0k1&22241+1U0a2c1y2f2h0=020z0V0M0T0t0T0n0A160p0z0Y200M0M0k0w2D192k0p1|0q050E2Q1`1|2V1'0y2m1-1!0p2e2A1&1g1i292n2$2&2)1&0t2J1|2O2Q2@0^232E2+1-0p0T0M0|0N0=1L2N2{1P2O2!0-30320O34000z0f3724392{3b0a3d3335063k2P0@3a2}3c313r3h093u3m2l3y3p3A3f350i3E3w3n3H3q3K3h0v3N2`3G1T2~3J3g0z0Q3V3x3Y3z3e3#0r3&3P3(3I3*350c3-3X2a3:3B0g0u3@2|3/3R3g0g0g3~3o420=0g3j1a383O3^2n48000g3t4c3l192;0k2Q2)2U0y2W2Z3H0w0T0Y2(1h1|4o2?383E014x0Y4E4f1-0B0=0Y0R3E0z3W403_0p0R0=0w0A0M0w0I2C0n080k0e4%0J3f2e050n4G3'3_0;000C4;3.4V4Y4!4$2C454l2P4T3o4@0W4R553Q4}4#4%054b2_4=2n4@040b3N0z5o4S5i4M0=0A4Q533h5a410m0=2q4`4L0-4@4_5w5y4|004Z5d515D4U5j0=04595r0-0T0=0S0d5U4{4g5A005C5I5V0a5G5P475c505f5-3H5k5m5w0D5p5{5q5$5s002J050I0M185w5}5E0a0B0w0=0U3f0n0k5n5p5J4g0=662@685Q1-5X005!676k2~5&5(5h5~5F0=5H6A690p5/5e526F6q6C005T6v5*6s0F5#690H0A496i5o6w3c5t6K386p3o6s6u6o6#0a6W0=3}5_5{6-4N000K1W1y6U6M3p6%6}6)0=030N050x725b006n6'6-1o0=240y79416I5O5)6B5+0=0l5=7k000A6&4m5*4@0G7j3_6s5Z7B6l5L4~5e5g4F7y7q7s3_6/006;6L560=0G5^2@5`5|6!5*6H7u7w2P6(3H6*7F2~716Q7o6s077,1A6X4i6Z7)3/6^5u7?707&806*6+7d7$6m7O5R007X4d7!7#7o6^62647c3l7{3_6b6d6f6h6=6j5*6^0R31807%0A7K8l7e0K5t8k7(6-0p5&0M240s8r7T5?6D897-7b8S6N5l7`6?8u5t5v6,877H5N057'4K6~4@0l6E7L7o8z8*7e0=7=7n6G5t8B547M6O8V0a6s0j927%8G8+7U007A7/697D858C8&5M5:8}998Q007r8`6~8z9l6-7z8c3l7Z8e8t8g0=8i65808o006e0%8O8d9A698h0Z8j9F6c000o0M0I9K9x194I4p4n2=194r19054t9(1{9(0O1)9#0q4r0@9;4B9?0Y0!0$0n00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013=m%0hP!_,u&F/"ea7)vcl[k6;i+gTot 1:. fds58(9bp4q3r2wn-S]y010E0h0x0i0s0n0F0y0m0n0i0F0F030g0x0s0L0g000C010F0c04040i0P0W000U0w0n0c0/0w0S010f0_0{0}100@0E0s0l0y0|0P0p0E0w0R0S0-0z0g0y0F0x0W0n0h0-1k0u0s0S0A0z0B0j0h040y0z1J1t0?0X1h0'0)0+0-070s0u070n1X070x0=010!0K1y1S0*0,0g1W1Y1!1Y0x1(1y1&0x0P001'070'130F0L0i1q0g0Q1t0(1,0-0D0$0h0S0i040h1&22241+1U0g2c1y2f2h0=020y080P0w0L0w0F0s160S0y0Y200P0P0h0m2D192k0S1|0f0x072Q1`1|2V1'0E2m1-1!0S2e2A1&1g1i292n2$2&2)1&0L2J1|2O2Q2@0^232E2+1-0S0w0P0|0n0=1L2N2{1P2O2!0-30320i34000y0Q3724392{3b0g3d33350O3k2P0@3a2}3c313r3h0M3u3m2l3y3p3A3f350G3E3w3n3H3q3K3h0q3N2`3G1T2~3J3g0y0j3V3x3Y3z3e3#0H3&3P3(3I3*350J3-3X2a3:3B0z063@2|3/3R3g0z0z3~3o420=0z3j1a383O3^2n48000z3t4c3l192;0h2Q2)2U0E2W2Z3H0m0w0Y2(1h1|4o2?383E014x0Y4E4f1-0p0=0Y0D3E0y3W403_0S0D0=0m0s0P0m0c2C0F0a0h0N4%0l3f2e0x0F4G3'3_0;000I4;3.4V4Y4!4$2C454l2P4T3o4@0b4R553Q4}4#4%0x4b2_4=2n4@0k0A3N0y5o4S5i4M0=0s4Q533h5a410K0=2q4`4L0-4@4_5w5y4|004Z5d515D4U5j0=0k595r0-0w0=09035U4{4g5A005C5I5V0g5G5P475c505f5-3H5k5m5w0C5p5{5q5$5s002J0x0c0P185w5}5E0g0p0m0=0e3f0F0h5n5p5J4g0=662@685Q1-5X005!676k2~5&5(5h5~5F0=5H6A690S5/5e526F6q6C005T6v5*6s0T5#69040s496i5o6w3c5t6K386p3o6s6u6o6#0g6W0=3}5_5{6-4N000R1W1y6U6M3p6%6}6)0=0d0n0x0r725b006n6'6-1o0=240E79416I5O5)6B5+0=0o5=7k000s6&4m5*4@0V7j3_6s5Z7B6l5L4~5e5g4F7y7q7s3_6/006;6L560=0V5^2@5`5|6!5*6H7u7w2P6(3H6*7F2~716Q7o6s0t7,1A6X4i6Z7)3/6^5u7?707&806*6+7d7$6m7O5R007X4d7!7#7o6^62647c3l7{3_6b6d6f6h6=6j5*6^0D31807%0s7K8l7e0R5t8k7(6-0S5&0P240u8r7T5?6D897-7b8S6N5l7`6?8u5t5v6,877H5N0x7'4K6~4@0o6E7L7o8z8*7e0=7=7n6G5t8B547M6O8V0g6s05927%8G8+7U007A7/697D858C8&5M5:8}998Q007r8`6~8z9l6-7z8c3l7Z8e8t8g0=8i65808o006e0%8O8d9A698h0Z8j9F6c000v0P0c9K9x194I4p4n2=194r190x4t9(1{9(0i1)9#0f4r0@9;4B9?0Y0!0$0F00
Exercice 23 : vérifier si un circuit est dans une liste de circuits

Écrire le code de la fonction appartient_circuit qui prend en paramètre une liste circuit correspondant à un circuit et une liste de listes liste_circuits, et qui renvoie un booléen indiquant si circuit est équivalent à un circuit contenu dans liste_circuits.

Il est conseillé d'utiliser circuits_equivalents.

Exemples
>>> appartient_circuits([1, 2, 1], [[5, 5], [9, 3, 9], [2, 1, 2]])
True
>>> appartient_circuits([7, 6, 2, 7], [[3, 6, 7, 3], [7, 6, 2, 7]])
True
>>> appartient_circuits([6, 3, 6], [[6, 4, 6], [6, 3, 7, 6], [3, 6, 7, 3]])
False

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013u3TmFhl4bc/=wqtS2:Pf in(.k"r,v5)sg yd1pe7oa_010D0G0h0J0o090z0n0c090J0z0z0e0t0h0o0F0t000B010z0306060J0u0C000i0I09030#0I0p010d0*0,0.0:0(0D0o0w0n0-0u0s0D0I0f0p0Z0E0t0n0z0h0C090G0Z180A0o0p0k0E0r0H0G060n0E1x1h0'0L150T0V0X0Z080o0A08091L080h0&010O0b1m1G0W0Y0t1K1M1O1M0h1U1m1S0h0u001T080T0?0z0F0J1e0t0j1h0U1Y0Z0m0Q0G0p0J060G1S1=1@1X1I0t201m23250&020n0l0u0I0F0I0z0o0_0p0n0M1:0u0u0G0c2r0|280p1-0d0h082E1+1-2J1T0D2a1Z1O0p222o1S14161|2b2Q2S2V1S0F2x1-2C2E2(0)1?2s2X1Z0p0I0u0-090&0E2B2,1D2C2O0Z2:2=0J2@000j2`1@2|2,2~0t312?0&04372D0(2}2.302;3e000a3h39293l3c3n330&0x3r0|2%0G2E2V2I0D2K2N3u0c0I0M2U151-3C2'2{3A3L0M3S3t1H1Z0s0&0M0m3r0n2+3Y1}3c0m0&0J0F1?0u0#220h0K0c0o0u0c032q0z3A3k3Z0Z0%000q423a3u0p0&3`3|3~0h493*2b460v3'3)2-443c0&1O1j0G3_3{3}404i4p3+460y0k3r0B0n4I3(433+3#000m2;4n4L2b4c004e4y0h360}2{4K4a4q1c0&1r4R4%3+4U4t0h4v4W4g414!384o3b464F4@3i4J504$4j3!4(3&4}00524B4T4d4x4=0K0G0g3~0w333@4?2*4S1Z4648574_4b5c4f2q4A4`0&4m57593b4U4;2q4Z5n4+4k0&4E4G515P5D3u4N2x0h030u0{5C5t4q0s0c0&050u030G5O4J5!4M0&5U5W5Y2(5R5#5%0007330z5*570(0d3V3D3B2&0|3F0|0h3H691,690J1V640d3F616j670N0P0R00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013y3vebno2Fdiu")pgf wk7s5mS(T,.hcPr/t =:1aql4_010c060B0G0d0I0o0k0x0I0G0o0o0D0f0B0d0h0f000C010o0e0q0q0G0z03000r090I0e0#0908010A0*0,0.0:0(0c0d050k0-0z0m0c090l080Z0F0f0k0o0B030I060Z180i0d080E0F0v0n060q0k0F1x1h0'0L150T0V0X0Z0w0d0i0w0I1L0w0B0&010O071m1G0W0Y0f1K1M1O1M0B1U1m1S0B0z001T0w0T0?0o0h0G1e0f0a1h0U1Y0Z0j0Q06080G0q061S1=1@1X1I0f201m23250&020k0y0z090h090o0d0_080k0M1:0z0z060x2r0|28081-0A0B0w2E1+1-2J1T0c2a1Z1O08222o1S14161|2b2Q2S2V1S0h2x1-2C2E2(0)1?2s2X1Z08090z0-0I0&0F2B2,1D2C2O0Z2:2=0G2@000a2`1@2|2,2~0f312?0&04372D0(2}2.302;3e000J3h39293l3c3n330&0p3r0|2%062E2V2I0c2K2N3u0x090M2U151-3C2'2{3A3L0M3S3t1H1Z0m0&0M0j3r0k2+3Y1}3c0j0&0G0h1?0z0#220B0K0x0d0z0x0e2q0o3A3k3Z0Z0%000s423a3u080&3`3|3~0B493*2b460u3'3)2-443c0&1O1j063_3{3}404i4p3+460g0E3r0C0k4I3(433+3#000j2;4n4L2b4c004e4y0B360}2{4K4a4q1c0&1r4R4%3+4U4t0B4v4W4g414!384o3b464F4@3i4J504$4j3!4(3&4}00524B4T4d4x4=0K060H3~05333@4?2*4S1Z4648574_4b5c4f2q4A4`0&4m57593b4U4;2q4Z5n4+4k0&4E4G515P5D3u4N2x0B0e0z0{5C5t4q0m0x0&0t0z0e065O4J5!4M0&5U5W5Y2(5R5#5%000b330o5*570(0A3V3D3B2&0|3F0|0B3H691,690G1V640A3F616j670N0P0R00
Exercice 24 : vérifier l'équivalence de listes de circuits

Écrire le code de la fonction listes_equivalentes qui prend en paramètres deux listes de listes correspondant à des circuits liste_circuits1 et liste_circuits2, et qui renvoie un booléen indiquant si les deux listes contiennent les mêmes circuits.

Il est conseillé d'utiliser appartient_circuits.

Puisque cette fontion va nous servir à comparer les circuits trouvés avec les circuits attendus, il se peut que le même circuit apparaisse plusieurs fois dans une des listes. On supposera donc qu'une des deux listes ne contient pas plusieurs circuits équivalents.

Exemples
>>> listes_equivalentes([[1, 2, 1], [4, 7, 3, 4]],
                        [[7, 3, 4, 7], [2, 1, 2]])
True
>>> listes_equivalentes([[5, 5], [9, 7, 3, 1 ,6, 9], [6, 3, 4, 6]],
                        [[6, 3, 4, 6], [5, 5], [9, 7, 3, 1 ,6, 9]])
True
>>> listes_equivalentes([[1, 2, 1], [2, 1, 2]],
                        [[7, 3, 4, 7], [2, 1, 2]])
False
>>> listes_equivalentes([[7, 3, 4, 7], [2, 1, 2]],
                        [[1, 2, 1], [2, 1, 2]])
False
Explications de l'algorithme

Il faut que les listes de circuits soient de même taille.

Ensuite il faut s'assurer que tous les circuits dans la première liste correspondent à un circuit dans la deuxième et réciproquement.

Si on posait l'hypothèse qu'une des listes ne contient des circuits duppliqués, il suffirait de vérifier la taille et que tous les circuits d'une liste sont inclus dans l'autre pour pouvoir conclure.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013ta(!_ .Tp"yi3mo e1whvl:u9k8P0fS2,rdg75/6qs=ncb)4F010B0j03040e0o0I0i0L0o040I0I0J0c030e0b0c0008010I0q0g0g040A0d000x0h0o0q0(0h0K010F0/0;0?0^0-0B0e0n0i0=0A0s0B0h0l0K0&0k0c0i0I030d0o0j0&1d0C0e0K0p0k090D0j0g0i0k1C1m0,0Q1a0Y0!0$0&0m0e0C0m0o1Q0m030+010T0M1r1L0#0%0c1P1R1T1R031Z1r1X030A001Y0m0Y0{0I0b041j0c0y1m0Z1%0&0w0V0j0K040g0j1X1`1|1$1N0c251r282a0+020i0u0A0h0b0h0I0e0~0K0i0R1^0A0A0j0L2w122d0K1=0F030m2J1:1=2O1Y0B2f1&1T0K272t1X191b222g2V2X2!1X0b2C1=2H2J2-0.1{2x2$1&0K0h0A0=0o0+1E2G2;1I2H2T0&2^2`042|000i0y301|322;340c362{2}0f3d2I0-332?352_3k3a0O3n3f2e3r3i3t382}0E3x3p3g3A3j3D3a0G3G2:3z1M2@3C390i0D3O3q3R3s373U0t3X3I3Z3B3#2}0r3&3Q233)3u0k0v3x122*0j2J2!2N0B2P2S3A0L0h0R2Z1a1=3_2,313@430R4a3.2g0s0+0R0w3x0i3P2=3(0K0w0+1T1o0j0I070j0H0q1a3827034w3@3Y3/0*00054H3'3/0K4t0e4v070L0e0A0L4B030I0k4N4g1&4K0z4m4o3h4Q004u4F4U4W4Y2v0I3c134b4I2g4K0N0p3G0i534n4|1&4i000e4l4`3e554O2g0K0M4t274%4p4J0+4M5c2I4+3J4R4T4V4X4Z4#5l3h4~4*560&0h0+060J5D5f2@5i4.5k5q4f5m4}5o5A5t4.4S4:5w4?4!4_2/5E0c4~515Q08545-5e4&0&582C030q0A115Q5/5S570L0+0P380I0j52545s3(580w2_5K5:3i0+5!4Z4$5{683/1h0+1w6d5}355u5Z4=5y6j5&5L0&4K5*2-5,5.536l4h6o5b2-5|3h6n002^036q4,0+040b1{0A0(4E4;5x4@5V3(4K5p6y6e4-6h2v6x4{6z5(0+4)6k5'4-4/0j6#5#4^6&5n0050666F5-6H570+5?5^5`6L785;6000620W655+775'6a6c6^6;6,6v2v5%316M3A6O6p7r6+6t6|6-5$715T006C316E6F7f0c585a6S7z0l0+6Q7T4q6U6W0?6Z0K036}5y7I4'5U5Q7P7t6$037w3e7P4(7Y4P7E7(4@6/7?5'5)75766G7o7a0S7c7_4h7h7j64837P5=885_8a5~0+0a0A0q7l6D124d3`3^2+123|12033~8z1;8z041!8u0F3|0-8I478K0R0T0V0I00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013tTuF q4wv0koy7P!i6rnae:lp3hS 9sd,8gm/"=2fc).(51_b010y0o030n0j0q0x0v0I0q0n0x0x0F0E030j0r0E0007010x050C0C0n0l0f000u0e0q050(0e0m010D0/0;0?0^0-0y0j0b0v0=0l0d0y0e0a0m0&0N0E0v0x030f0q0o0&1d0B0j0m0p0N0K0g0o0C0v0N1C1m0,0Q1a0Y0!0$0&0t0j0B0t0q1Q0t030+010T0P1r1L0#0%0E1P1R1T1R031Z1r1X030l001Y0t0Y0{0x0r0n1j0E0G1m0Z1%0&0H0V0o0m0n0C0o1X1`1|1$1N0E251r282a0+020v0h0l0e0r0e0x0j0~0m0v0R1^0l0l0o0I2w122d0m1=0D030t2J1:1=2O1Y0y2f1&1T0m272t1X191b222g2V2X2!1X0r2C1=2H2J2-0.1{2x2$1&0m0e0l0=0q0+1E2G2;1I2H2T0&2^2`0n2|000v0G301|322;340E362{2}0s3d2I0-332?352_3k3a093n3f2e3r3i3t382}0M3x3p3g3A3j3D3a0k3G2:3z1M2@3C390v0g3O3q3R3s373U0A3X3I3Z3B3#2}0w3&3Q233)3u0N0c3x122*0o2J2!2N0y2P2S3A0I0e0R2Z1a1=3_2,313@430R4a3.2g0d0+0R0H3x0v3P2=3(0m0H0+1T1o0o0x0O0o08051a3827034w3@3Y3/0*000L4H3'3/0m4t0j4v0O0I0j0l0I4B030x0N4N4g1&4K0z4m4o3h4Q004u4F4U4W4Y2v0x3c134b4I2g4K0J0p3G0v534n4|1&4i000j4l4`3e554O2g0m0P4t274%4p4J0+4M5c2I4+3J4R4T4V4X4Z4#5l3h4~4*560&0e0+0i0F5D5f2@5i4.5k5q4f5m4}5o5A5t4.4S4:5w4?4!4_2/5E0E4~515Q07545-5e4&0&582C03050l115Q5/5S570I0+06380x0o52545s3(580H2_5K5:3i0+5!4Z4$5{683/1h0+1w6d5}355u5Z4=5y6j5&5L0&4K5*2-5,5.536l4h6o5b2-5|3h6n002^036q4,0+0n0r1{0l0(4E4;5x4@5V3(4K5p6y6e4-6h2v6x4{6z5(0+4)6k5'4-4/0o6#5#4^6&5n0050666F5-6H570+5?5^5`6L785;6000620W655+775'6a6c6^6;6,6v2v5%316M3A6O6p7r6+6t6|6-5$715T006C316E6F7f0E585a6S7z0a0+6Q7T4q6U6W0?6Z0m036}5y7I4'5U5Q7P7t6$037w3e7P4(7Y4P7E7(4@6/7?5'5)75766G7o7a0S7c7_4h7h7j64837P5=885_8a5~0+040l057l6D124d3`3^2+123|12033~8z1;8z0n1!8u0D3|0-8I478K0R0T0V0x00
Exercice 25 : trouver tous les circuits passant par un sommet donné

Écrire le code de la fonction trouve_circuits_rec qui prend en paramètre un dictionnaire graphe correspondant à un graphe, un sommet depart et une liste circuits, et qui rajoute à circuits tous les circuits de graphe passant par depart. La représentation des circuits trouvés doivent tous commencer par depart.

Il y a également deux paramètres supplémentaires etat et chemin qui sont initialisés à None par défaut :

  • etat est un dictionnaire correspondant aux états des sommets ;
  • chemin est la liste des sommets ayant permi d'arriver au sommet actuel. On supose que depart est le dernier élément de chemin.

Contrairement à trouve_circuit_rec, on n'accepte pas les circuits qui sont accessibles depuis depart mais qui n'y reviennent pas.

Rappels des graphes déjà définis 

graphe1_dico = {
    0: [1, 2],
    1: [2],
    2: [0, 1],
    3: [1, 2]
    }


graphe2_dico = {
    0: [1, 2],
    1: [3],
    2: [8],
    3: [2, 4],
    4: [7],
    5: [0],
    6: [5],
    7: [5],
    8: [9],
    9: [2]
    }


graphe3_dico = {
    0: [1, 2, 3],
    1: [0, 3],
    2: [0, 3],
    3: [1]
    }


graphe4_dico = {
    0: [1, 3],
    1: [2],
    2: [7],
    3: [4],
    4: [6],
    5: [0],
    6: [2, 7],
    7: []
    }  


graphe5_dico = {
    0: [5, 7],
    1: [3],
    2: [0, 4],
    3: [2],
    4: [3],
    5: [],
    6: [5],
    7: [6]
    }
Exemples
>>> circuits = []
>>> trouve_circuits_rec(graphe2_dico, 0, circuits)
>>> circuits
[[0, 1, 3, 4, 7, 5, 0]]


>>> circuits = []
>>> trouve_circuits_rec(graphe2_dico, 6, circuits)
>>> circuits
[]

>>> circuits = []
>>> trouve_circuits_rec(graphe2_dico, 9, circuits)
>>> circuits
[[9, 2, 8, 9]]

>>> circuits = []
>>> trouve_circuits_rec(graphe3_dico, 0, circuits)
>>> circuits
[[0, 1, 0], [0, 2, 0], [0, 2, 3, 1, 0], [0, 3, 1, 0]]

⚠ Pour les tests, puisque les circuits ne peuvent pas être trouvés dans le même ordre mais qu'on veut qu'ils commencent tous par le départ choisi, on n'utilisera pas listes_equivalentes.

Astuce pour tester plus facilement la fonction

Si vous rajoutez return circuits à la fin de la fonction, vous pouvez tester la fonction en une seule ligne :

Exemple en ayant rajouté `return circuits`
>>> trouve_circuits_rec(graphe3_dico, 0, [])
[[0, 1, 0], [0, 2, 0], [0, 2, 3, 1, 0], [0, 3, 1, 0]]
Explications de l'algorithme
  • Si chemin ou etat sont à None, on leur donne une valeur initiale. Pour chemin, on y met le sommet actuel.
  • Si le sommet est en attente, alors c'est qu'on vient de trouver un circuit.
    • Si le circuit commence au sommet actuel, c'est que le circuit passe bien par depart.
    • On rajoute une copie du chemin à la liste des circuits.
  • Sinon, on marque le sommet actuel comme étant en attente.
  • On parcourt alors chaque voisin. Si le voisin n'a pas été marqué comme traité :
    • on le rajoute au chemin ;
    • on rajoute tous les circuits qu'on peut trouver en passant par l'arc depart -> voisin à l'aide d'un appel récursif ;
    • on le retire du chemin pour pouvoir prendre un autre chemin.
  • On repasse le sommet courant à "pas vu" pour pouvoir y revenir par un autre chemin.

Aucun sommet n'est marqué comme "traité" dans cette fonction, mais ils le seront dans la fonction suivante. Cela permettra d'éviter de prendre deux fois des circuits déjà vus.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280138nko_2hS.artP]wd&iqvb,e/;fp =1)[}u0(s3y{4:65 émgN!"lc79010i0p0e0c0k0S0D0u0T0S0c0D0D0v0R0e0k0t0R000L010D0A0N0N0c0d0F000a060S0A0.0604010q0^0`0|0~0?0i0k0m0u0{0d050i060h040,0w0R0u0D0e0F0S0p0,1j0O0k040I0w0b0U0p0N0u0w1I1s0=0W1g0&0(0*0,090k0O090S1W090e0;010Z0n1x1R0)0+0R1V1X1Z1X0e1'1x1%0e0d001&090&120D0t0c1p0R081s0'1+0,0s0#0p040c0N0p1%21231*1T0R2b1x2e2g0;020u0f0d060t060D0k15040u0X1~0d0d0p0T2C182j041{0q0e092P1_1{2U1&0i2l1,1Z042d2z1%1f1h282m2#2%2(1%0t2I1{2N2P2?0@222D2*1,04060d0{0S0;1K2M2`1O2N2Z0,2~310c33000u083623382`3a0R3c32340E3j2O0?392|3b303q3g0H3t3l2k3x3o3z3e340K3D3v3m3G3p3J3g0J3M2_3F1S2}3I3f0u0U3U3w3X3y3d3!033%3O3'3H3)340V3,3W293/3A0w0B3?2{3.3Q3f0w0w3}3n410;0w3i19373N3@2m47000w3s4b3k4d3~3^4g0w3C4k3u3V4n4f3Z483L4s3E4v3Y3:4h3T4A182:0p2P2(2T0i2V2Y3G0T060X2'1g1{4J2=373D014S0X4Z4e1,050;0X0s3D0u4u460s0;1_060A0m0p070T0k0d0T0A2B0D072I0T4#3&3^0:000C583-4o0;0O0d0c0t090p5e4(0,5b0o4.4:3P4+0p220d0e5o4C5q0;5s4A4/594f0;4}50520e0D5B3n5r5t5I2}0;0Y0c5A4H5U0,060;0v5Q3G050T0;0P165n5!5f2m5S5G5u405K5m0N1C5(3.5%005'5:5p0R5*5,5.5~5a0;0x0I3M0u6g5H5;4)0;0k4-5@5#3o5`1I5}6o6j5$0h6l5P6u6567005-2$6a5=0;6e4A0L6h6M6i65046r5|176A5C0R61632?6O6V5b0y6G5V000X5y5Z2^6p5b0g6f6h5^3^4*006m5T6v6q005X6+376!3n1n6y6`6B5+6D69646#6I6:6N725v6}0Z703k7g605&767c000G6&3b0;0D060`0Y7t0R5b6J6Z6=2m0D26000j0l0A060e0r220%0m0A7K7M7O7p3n6@0s307X7h7w7y7k2O7m3^746^6T7E6p6Q005i5k5m7A5b0z7e7*2m6@6_6U465W7j7_0;6%7b836(5x0|7(4'7q6/823G6X6Y717F1,7H0;7U7N0r2d0u5Y0e2d8x8r7W893G7C7|6M8n0,806n7/6{7;0T5{6t6,6{6$7A5|0;3|8C3.6.7$7n628l7l8H6|6)8d86007D4c7f7f8(8N4~51537A610b7A7;5k0t2d0i8,5d8Y4o0n0;1Z1u948}6R8Q4!6-6c0x7|8(6@0p0$5/8R658E6K8:7}6'6~8,889q6V7;8*5z8,8h8L656X8#3^8p7J7L8s8u8w8y0p8A0r8F6;6p7Z7#8i5_000m060k2A7.8m6p7,9f8'7:5h5j5l9p9g8S879d8b6*9F8.4l9u8G9Y6l8K9+8M845Y9y9{9&9(9.2O8(8!9#7+0;0Q8&7)8(9M9U1_0!0e0M9U8,a03ua28:8=9e9*3k8(8{9{90929c965J9%9'9)8,9j9taA6NaC004@4_4{5L8^5O552JaL9A8a7?9?8,5F9H9B0;adaQaM1,5?a/8aa#5N6za)8D5E9KaN9xa@5D00a.a76PaDaR9WaAaW8O6saEag9,0;8|b66|2y0t94aS2?6LaB9:7iaabo8Tbo9C8c9EbA0;9Gba6V9Jaj7G7I9U7Q0u7Saw6K184%4K4I2;184M180e4Ob$1`b$0c1(bX0q4M0?b-4Wb/0X0Z0#0D00
Exercice 26 : trouver tous les circuits d'un graphe

Écrire le code de la fonction trouve_tous_circuits qui prend en paramètre un dictionnaire correspondant à un circuit et renvoyant la liste de tous les circuits de ce graphe.

Exemples
>>> trouve_tous_circuits(graphe3_dico)
[[0, 1, 0], [0, 2, 0], [0, 2, 3, 1, 0], [0, 3, 1, 0], [1, 3, 1]])
>>> trouve_tous_circuits(graphe4_dico)
[]
>>> trouve_tous_circuits(graphe2_dico)
[[0, 1, 3, 4, 7, 5, 0], [2, 8, 9, 2]])

⚠ Selon l'ordre de parcours, les résutats peuvent ne pas être dans le même ordre.

Explications de l'algorithme

On parcourt chaque sommet, on cherche les circuits qu'il contient et on le marque comme traité pour ne plus le revisiter en regardant les sommets suivants.

Normalement au début de la recherche des circuits passant par un sommet, tous les autres sommets sont marqués soit à "non vu", soit à "traité".

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013w"e yp&,mf7u6bg3ésP2=qc]nti8k;a_d5[{ S.v4h1rol/(:)}010z050s0x0t0M0k0D0p0M0x0k0k0n040s0t08040006010k0e0b0b0x0K07000E0L0M0e0*0L0r010N0;0?0^0`0/0z0t0G0D0@0K0v0z0L030r0(0J040D0k0s070M050(1f0h0t0r0P0J0F0d050b0D0J1E1o0.0S1c0!0$0&0(0I0t0h0I0M1S0I0s0-010V0g1t1N0%0'041R1T1V1T0s1#1t1Z0s0K001!0I0!0}0k080x1l040m1o0#1'0(0c0X050r0x0b051Z1|1~1&1P04271t2a2c0-020D0l0K0L080L0k0t110r0D0T1`0K0K050p2y142f0r1@0N0s0I2L1=1@2Q1!0z2h1(1V0r292v1Z1b1d242i2X2Z2$1Z082E1@2J2L2/0:1}2z2&1(0r0L0K0@0M0-0J2I2?1K2J2V0(2`2|0x2~000m321~342?3604382}0-0i3e2K0/352^372{3l000H3o3g2g3s3j3u3a0-0A3y3q3h3B3k3E000f3H2=3A1O2_3D3b0d3P3r3S3t393b0u3y142,052L2$2P0z2R2U3B0p0L0T2#1c1@3(2.333&3;0T3{3R25040v0-0T0c3y0D3Q2@3Z3j0c0-1=0L0e0G050y0s4i0k0y0p0t0K0p0e2x0k3&3Y430,000O4y3J4d0r0-0h0K0x080I054E422i4B0Q0P3H0D4W4a4z2i4H000U0x0s494b3i0L0-0n4(4Z1(4B0C4P4c434#0k0L0?0U4?3i4B4U15334Y4F430k2200090o0e0L0s0w1}0Z0G0e5b5d5f4.562i45000c2{5o4Q2_0-4`4|4'533f555w0(1j0-1y5v4@4!4I4K4M4O5C2K4)3B4B0R4V4X5T4G0-4r4t4v0s4x5R005E5L1(4+004-5)5+500-0B0q5X4W5Z435r5t0K5K3i4#0T1}0K5B2/5=3B5H005J5;5|5M004J4L4N4~5U0-522/064X6s6a4d5r0t486f4/370-4%683|6A044B0B6m5!00650^6E3f6g4:0-5_6z5p5-4,5:696R0(580-5l5e5g0%0D5j6'5n5)6#6H6o5`6t6s6:4#4h4j4l5$4u4w0y2E0p6K4A0-4D6/6G4#6j5P754R0-0a623K4605666P5S6G4B7h6V5F3j5#4s705'7e6S007r6!7a6C0V7n415,0(4S6?6@5{7E4$7G7z7K5@7S7u6M7l6O7V4B6U7D6W5G4,7i4d6%5a5c6(1=0W0s0j6-0w6?6:5r2E0s0e0K137s7J7W6~5&5(6q143~3)3'2-143+140s3-8f1?8f0x1$8a0N3+0/8o3^8q0T0V0X0k00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013rnq.[;f"kpuS}wlhd4sPv/ab{t&73]ée:5=(m1_cy)g2 oi 8,6010j0y0s0p0N0h0l0L0G0h0p0l0l0B0a0s0N0c0a000O010l0d0D0D0p030H000e0M0h0d0*0M04010o0;0?0^0`0/0j0N0n0L0@030b0j0M0g040(0E0a0L0l0s0H0h0y0(1f0J0N040z0E060u0y0D0L0E1E1o0.0S1c0!0$0&0(0i0N0J0i0h1S0i0s0-010V0q1t1N0%0'0a1R1T1V1T0s1#1t1Z0s03001!0i0!0}0l0c0p1l0a0K1o0#1'0(090X0y040p0D0y1Z1|1~1&1P0a271t2a2c0-020L0m030M0c0M0l0N11040L0T1`03030y0G2y142f041@0o0s0i2L1=1@2Q1!0j2h1(1V04292v1Z1b1d242i2X2Z2$1Z0c2E1@2J2L2/0:1}2z2&1(040M030@0h0-0E2I2?1K2J2V0(2`2|0p2~000K321~342?360a382}0-0v3e2K0/352^372{3l000k3o3g2g3s3j3u3a0-0A3y3q3h3B3k3E000R3H2=3A1O2_3D3b0u3P3r3S3t393b0P3y142,0y2L2$2P0j2R2U3B0G0M0T2#1c1@3(2.333&3;0T3{3R250a0b0-0T093y0L3Q2@3Z3j090-1=0M0d0n0y0F0s4i0l0F0G0N030G0d2x0l3&3Y430,000C4y3J4d040-0J030p0c0i0y4E422i4B0I0z3H0L4W4a4z2i4H000U0p0s494b3i0M0-0B4(4Z1(4B0r4P4c434#0l0M0?0U4?3i4B4U15334Y4F430l22000t050d0M0s081}0Z0n0d5b5d5f4.562i4500092{5o4Q2_0-4`4|4'533f555w0(1j0-1y5v4@4!4I4K4M4O5C2K4)3B4B0f4V4X5T4G0-4r4t4v0s4x5R005E5L1(4+004-5)5+500-070w5X4W5Z435r5t035K3i4#0T1}035B2/5=3B5H005J5;5|5M004J4L4N4~5U0-522/0O4X6s6a4d5r0N486f4/370-4%683|6A0a4B076m5!00650^6E3f6g4:0-5_6z5p5-4,5:696R0(580-5l5e5g0%0L5j6'5n5)6#6H6o5`6t6s6:4#4h4j4l5$4u4w0F2E0G6K4A0-4D6/6G4#6j5P754R0-0Q623K460y666P5S6G4B7h6V5F3j5#4s705'7e6S007r6!7a6C0V7n415,0(4S6?6@5{7E4$7G7z7K5@7S7u6M7l6O7V4B6U7D6W5G4,7i4d6%5a5c6(1=0W0s0x6-086?6:5r2E0s0d03137s7J7W6~5&5(6q143~3)3'2-143+140s3-8f1?8f0p1$8a0o3+0/8o3^8q0T0V0X0l00