Colorier un graphe

On souhaite pouvoir colorier les différents sommets d'un graphe non orienté, avec les contraintes suivantes :

on ne dispose que de $4$ couleurs : "rouge", "jaune", "vert" et "bleu" ;
deux sommets voisins ne doivent pas avoir la même couleur.

On suppose les $n$ sommets numérotés de $0$ à $n-1$.

flowchart LR
    0([0]) --- 1([1])
    1 --- 2([2])
    0 --- 4([4])
    3([3]) --- 1
    1 --- 4
    2 --- 4
    1 --- 5([5])
    4 --- 5

Dans cet exercice, les graphes sont implémentés par un dictionnaire dont les clés sont les sommets et les valeurs les listes des sommets adjacents.

Ainsi, le graphe ci-dessous est donné par le dictonnaire :

🐍 Script Python

g1 = {0: [1, 4],
    1: [0, 2, 3, 4, 5],
    2: [1, 4],
    3: [1],
    4: [0, 1, 2, 5],
    5: [1, 4]}

Question 1

Compléter le dictionnaire ci-dessous qui pour chaque sommet du graphe précédent associe une couleur, en respectant les contraintes énoncées :

Évaluations restantes : 10/10

.128013s3o_bcdufvg/0ly napSr1me,P2=4:}jti5h{050h0y0H0s0I0o0b0q0g0o0s0b0b0C010H0I0t010406050b0i0x0x0s0v0p040u0d0o0i0$0d0r050m0-0/0;0?0+0t040 1605190m191b160+0h0I0k0U0W0Y0!0K0I0l0K0o1p0K0H0)050P0f0o0y1k0X0Z011o1q1s1q0H1y1A1w0H0f0d0h0?1x0v170H0K0U0_0b0t0s0r0!0B011C1m010j0R0y0r0s0x0y1w1!1$1+1E1.1A1;1?0)0a0q0A0v0d0t0d0b0I0|0r0q0N1Y0v0v0y0g2b0 1_0r170m1W2o0H1U1T1V0h1{0!1s0r1:281w1h1j0V1D2y0I2A0r1Q1i1w0t2h172m2o2S0,1#2c2G1,2L0v0:0o0)0w2l2W2o2P0y2o2E2r0h2v2x010g1Q1@172:1a2Q2V1$2T2+052_0N2R2W2@0r0)2_0i1A0i0v0b0e0b0d0/0O0b2*310q302X1l1E0d0)0C3o2n3q2m2@0(040L3y371`2Y1E0x0I0)0n3G3r3C0)0E3G3A383J0!0b1)0401250i0l1@3P3B3X013D0z3U3Q3-3L2(3+3W3t0!3D3T102+3V3I3{013Z0)011z0y0i013_422H3.0)3:3 3p3=433@040B4c3s4e3}3;3,43453#0k0y0v1v4p3R044h2S414q1,4m0c4C3-4s4i3z4k4e4w010G0s0i2A4b4P3H4I1E3/4M4l3M040D4)4r3S4t3`4S3!4U4W4Y4.1,4(4!4H2@4m0J4{4%4:4~4R1,4T4y4A4Z2U4u4/040F3G0+0m352.182 0m2}2p2=0 2s2r1P1R2r0s482/1i0*0 0N0P0R0b04.

Votre figure

Votre tracé sera ici

Algorithme

Dans les questions suivantes, on se propose de créer une fonction qui puisse déterminer automatiquement une coloration du graphe.

L'algorithme de Welsh-Powell que nous allons utiliser repose sur une méthode gloutonne, selon le principe suivant :

on classe les sommets selon l'ordre décroissant du nombre de leurs voisins,
on associe un ordre aux différentes couleurs (arbitraire, mais qui reste constant tout le long du coloriage),
pour chaque sommet, on choisit la première couleur non utilisée par les voisins.

Tri des couleurs

Les couleurs sont triés de façon arbitraire.

L'important est que cet ordre soit conservé tout le long de l'algorithme.

Question 2

On classe les couleurs dans un tableau COULEURS_POSSIBLES.

La fonction choix_couleur, dont le code est chargé en mémoire, prend en paramètre un graphe, un sommet et un dictionnaire associant les sommets avec leur couleur, et renvoie la première couleur non utilisée par les voisins du sommet ou None si toutes les couleurs sont déjà utilisées.

Dictionnaire incomplet

Il est à noter que le dictionnaire est incomplet et peut même être vide.

Compléter la fonction test_choix_couleur en ajoutant au moins trois autres tests pertinents. Pour chaque test ajouté, une brève justification doit être donnée afin d’expliquer pourquoi ce cas est important à vérifier.

Tests

Il est possible d'utiliser l'IDE ci-dessous afin de visualiser des solutions, en ayant la possibilité de changer le graphe ainsi que les couleurs.

Votre figure

Votre tracé sera ici

>>> COULEURS_POSSIBLES = ["rouge", "jaune", "vert", "bleu"]
>>> choix_couleur(g1, 1, couleurs_sommets)
'bleu'
>>> choix_couleur(g1, 3, couleurs_sommets)
'rouge'
>>> COULEURS_POSSIBLES = ["rouge", "jaune"]
>>> choix_couleur(g1, 1, couleurs_sommets)
None

Évaluations restantes : 10/10

.128013s3_8ufvIy n7aS1me(P24C:jtwi][hE)6OobcdUgx/0lqBprL,}=Nk95R{é050M0r0z0n0B0S0b0k0L0S0n0b0b0!010z0B0V010406050b0f0q0q0n0W0j040o0J0S0f0 0J0l050Q16181a1c140V041l1s051v0Q1v1x1s140M0B0h0@0_0{0}0E0B0O0E0S1L0E0z12050/0K0S0r1G0`0|011K1M1O1M0z1U1W1S0z0K0J0M1c1T0W1t0z0E0@1f0b0V0n0l0}0u011Y1I010g0;0r0l0n0q0r1S1}1 241!271W2a2c120a0k0t0W0J0V0J0b0B1i0l0k0-1{0W0W0r0L2x1l2f0l1t0Q1_2K0z1@1?1^0M2h0}1O0l292u1S1D1F0^1Z2U0B2W0l1:1E1S0V2D1t2I2K2=151~2y2$252+0W190S120k0p2H2_132^2g2{1!2}2 310u341 362I2T013b0n30040k0c3f2J143i390}3l3n0k0v3r3h2_3j3x310(3B3t3D3v3k0J2~3m310H3I372`1H3a3N3c3o0m3S3u3V3w3X3P3o0e3#3K3%3M3O3y0%3-383/3F040p0R3@3U2%3:3Y0p331m353J3^403`0p3e453g473 2|3)3n0p3q4d3s3T3E4i120p3A4m3C484h3;4r3H4u4f4p4y3{3R4B4o3L4a3!4H3$494q3{3,4M3.4O4E0p3?4S4w3W4E0u3}4u1u2:1l2!2N0M2R3j0L1:2d1t4,1w4*2@4(4;0-2;4T2|120w0I0N0X0F0N0)0o0d0t0I0o0o0i0U560o3B0k4I3/0J120!5k5m4011040D3B5s250b2204012r0f0O2d5x4N255u0Y5r5J1!5A12010y0n0f2W015I501!5L5N5Z0}5Q5C0h0r0W1R5Y4Z0}5#4u5l5O5(5B011V0r0f5X4(5^015u0C3I4C3L0$120-0g5/4g1!0A316c3E0g120z0r0b0z0d0L0E0J0B0P6p0J0f1W0f0W6h3L5u0s0G0x3I0k6I5@5%3k120O442=6K5:015o045q5?5y5!120*6B3/0q0B124%2@615u6G6X6-125w606L6(4r6$5t125M6:6^6)044t6,6L636~2=066J7a6R6d0}6_3{6{5K126/6Q6Y5;6=7h1!7f6+357m626}5$6S7f4c746S5=7l617f4l7B7d7v0477357c3j7f737t6;7L7x7J7f4A7I3j766H7b6I7u7z7p7n047k7N7u5u6?7Z3L7f6P7S757w6 7y717R3g7:120C7M4e7%7(7F717H7`7C7j7V7!7o6@7~6`8i7J7#4B877O7@7 7+7K7.3g8q3/7;8t7r8t7D7/898k7?8y7|7E70127Y8c8m83853s8p7)718N817T8v2J8x6|5v8A717_8X7{7U7}7W8s8l8g040C0Z657a7u0l124;6x5}0W0b0d0b0J180.0b8f3L6U6W6Q8#7i046#8;8r6*8C8e8.3j5)5D6w5G5 8H8$8R3o8U127A8O8=8Z9x619p5+5-9t9B6C8J8E8L048b8+8d7-993/9p5T5V5H9i8I048^8o6J7u68041Z5,0z9U498}6r6t6v8 6z9l040s8t8|046O9{9w9e7q8)a29:51048~6y9193952c0z989!8$0Ga81!9b9c9N6S0b0p12005|0f00a79n3L9p0+6q2E2z0f0k6l6n0k0R9J869)619+9-5-am3w9=6s6uab909{9}aja9a1a%6Z8-8K8j9Paza-7J9 aZ6z929496ah9{alaA5n5pap8w7uasau5E5Gaya*7,a3b45`aD0EaF0MaHaJ0z32aN3s0679aP6La?6waca_af97aU6T5p5ka47,9h9u258Bba8ubz9pb79ZbGa+bc8F049A9R8P9Ta 409G9.bn4 9SbR9O9Q2J82bXa;9o5`9X5Wa:aq8/1280b,8Y8t9pawb$b-9%788`aQ12aS9/bYa96qaX9^aca#9~6N8*b|8,b)a.cjb%bWcma=8}bu90bwa{aibP7,a~b/9ab1bz0$0L120#1j0rb@b39FbeaE0L0k0T0f1 2S0;0k0l000j0k0n0k0V1g0?2Aa@91c(2u2v5|0bb$bpc5bsct9_ada`agcyb^3j9bbCb-0*c346c_6SaR0{9.bza?9?aYcu9`bJ6Dcha0cob-cr7Pa6dk9McNc`aadic}bxa|dt04cBd1cD6Vb28!b4at0400bNb9cz7KdqaBcPbgcR2t6z0k1Wc(2D6(5,0@dgc@1l4}0r2K2/d.4+1E4-2N2P2L1/1;2N0n5|2K4,140Q0-0/0;0b04.

Question 3

Compléter la fonction tri_sommets qui prend en paramètre un graphe et qui renvoie la liste des sommets classés par ordre décroissant du nombre de voisins.

Quand plusieurs sommets ont le même nombre de voisins, l'ordre entre eux n'a pas d'importance.

fonction nb_voisins

On pourra s'aider de la fonction nb_voisins, déjà chargée en mémoire, qui prend en paramètre un graphe représenté par un dictionnaire et un sommet, et renvoie le nombre de voisins au sommet initial.

>>> voisins(g1, 1)
5
>>> voisins(g1, 3)
1

🐍 Script Python

>>> tri_sommets(g1)
[1, 4, 0, 2, 5, 3]

Indice

Il s'agit d'un tri par insertion.

Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0ly n7apSr1-me,(P2=4:jtwki9][5h)6050j0C0L0v0O0q0b0s0i0q0v0b0b0H010L0O0w010406050b0k0B0B0v0y0r040x0d0q0k0:0d0t050o0`0|0~100^0w04191g051j0o1j1l1g0^0j0O0m0(0*0,0.0T0O0n0T0q1z0T0L0?050Z0h0q0C1u0+0-011y1A1C1A0L1I1K1G0L0h0d0j101H0y1h0L0T0(130b0w0v0t0.0G011M1w010l0#0C0t0v0B0C1G1.1:1^1O1{1K1~200?0a0s0F0y0d0w0d0b0O160t0s0X1,0y0y0C0i2l19230t1h0o1*2y0L1(1%1)0j250.1C0t1}2i1G1r1t0)1N2I0O2K0t1!1s1G0w2r1h2w2y2$0_1/2m2Q1_2V0y0}0q0?0z2v2*0@2)242,1O2.2:0?0G2@1:2_2w2H012~0v2;040c322x0^352|0.383a0I3d342*363j0?0S3m3f3o3h370d2/390?0V3t2`2+1v2}3y2 040u3D3g3G3i3I3A040f3M3v3O3x3z3a0P3m1i2!192O2B0j2F360i1!211h3)1k3%2(1a2^053.0X2#3V2R010N0?0X0l3#3N400M0?0s463 2-0l0?2C0O0e0b0d0|0Y0b4c2{3W0=040E4p3F400t0?0n0y0v0w0T0C4v364s0U0J3t0s4M4b472-0?1C0b0L0C0e4h0C4F3_334O4d1O0d0?0H3m4$4q404s0R4G3w4y044k4m0L4,3E3642040l3y4|4P2}0?4_204{4!2x4-4w1_0d49042T534%3i4z4B4D4Z2(540.4s0Q4L4N4}3w4 510y5j4.4Q5h5C5d4(5g5i5a045c3p0h0?4B0t0n5p3`5r014s4u5L5x3W0B0O2=4=4r0?0D5G5O4R1}5*4/0?5Z5q5k374R0O4T4V4X5U335#5?040U4J5v4N5w5W4@0K5.3w4)044+5L5N4?0?0O68696k3W4 0M1y1K6e3W6c6w406g020n0L0g6z1_5%0?0p6G5I0?1:0j6L5l040t0h0e0m0d5}2T4o5!5W5Y5=5E4A4C4E6(1O4s5-6j635E4S4U4W0y0O4Y6-5s0?4;6#5`6y715D6.0?0Q0U6Q016B6D6F6;6b0?6T6V6X2j0t6!5_756~4t6}5{046*5o7s6/7a4@6@5 6`6|745H7q707o7G7t6d7F366g0A7s6I042?7N3w5t675L066p7#6q4x5|5~6_6{612x6=76047I5V720?7M7J4H776:2$7%6?5}6^607x6 7s737`6f0?7Q7V5$5(7T84045u7f5`6g6i7~7/6R7B7+7E885+7;867^7s7P7R8e7U8t640Q7}2^7 55048q838c647=627g047_7?7p5X776o7$8I6R8T4#8o7b4*7z8x8j8V8z8-7K7S8C2^067!6a5`4 2r0L0k0y188:3p7)827D7-2_0o3|0C2y2Z9b3(1s3*2B2D2z1Z1#2B0v1J9e0o3)0^9r0Y0!0$04.

Question 4

Compléter la fonction colorie_graphe qui prend en paramètre un graphe représenté par un dictionnaire et qui renvoie un dictionnaire associant à chaque sommet une des quatre couleurs.

Il est à noter qu'il peut exister plusieurs solutions, mais il existe toujours une solution.

fonctions auxiliaires

On pourra s'aider des fonctions précédentes, déjà chargées en mémoire.

>>> colorie_graphe(g1)
{0: "rouge", 1: "bleu", 2: "vert", 3: "jaune",4: "jaune", 5: "bleu"}

Test

Le résultat n'est pas forcément unique car les sommets ayant le même nombre de voisins peuvent se retrouver dans un ordre différents.

La fonction test_coloration (chargée en mémoire) permet de vérifier si les contraintes de coloration sont bien respectée par le résultat obtenu.

Évaluations restantes : 10/10

.128013s3o_;bcdufvgx/0lyq n7apS.r1L-meh,(P2=4:}jtwki][5R{)6050i0F0Q0w0T0q0b0t0h0q0w0b0b0L010Q0T0x010406050b0j0E0E0w0A0r040y0d0q0j0^0d0u0t020w0E0x0f0t0X0F120A0s0j0F0b050o0 1113150}0x041t1A051D0o1D1F1A0}0i0T0l0-0/0;0?0G0T0m0G0q1T0G0Q0{050(0g0q0F1O0:0=011S1U1W1U0Q1$1(1!0Q0g0d0i151#0A1B0Q0G0-180b0x0w0u0?0K011*1Q010k0*0F0u1g0F1!25272c1,2f1(2i0E2k040a0t0J0A0d0x0d0b0T1b1d0$230A0A0F0h2F1t2m0u1B0o212R0Q1 1~200i2o0?1W0u2h2C1!1L1N0.1+2#0T2%0u1{1M1!0x2K1B2P2R2|0~261d2-2d2=0A120q0{0B2O300|2 2n321,34360{0K3a273c2P2!013h0w37040c3l2Q0}3o3f0?3r3t0M3w3n303p3C0{0W3F3y3H3A3q0d353s0{0!3M3d311P3g3R3i040v3F1C2`1t2+2U0i2Y3p0h1{2u0#1M1B2_0F2{3b3)3=0$3}3e3Z0?0S0{0$0k3)3z44010R0{0t4a3O4c0u0k0{3=0q3R0T0F0e0m0A0w0x0G0F4h432.010`040I4z3Y4B0u0{4t4v4x4G3p4D0Z0N3M0t4U4g4b4I0{0b0d110%0b0e2V4q1s1u3b4W4i4B0d0{0L3F4/4A330{4*0e4!4$0Q4O3P4D4F4-3m3X3I4K4u4w4y562Q58530{0Z4T4V5g4j470T3=0e3=0j1(0j0A4,2|4_4H2d4=044@5e045z4P0{0Y0O5k4U5m4B46040k3R4^5O4{044 2t515F5H3P0d4e042:5U4X5W5Y4%4)0A4+524c4D4S5F064V5}5$5n041L5q5s5u5w5@4B4D0V675.4#5Z6b1,4D0U5,4:5B4?6j4`3g4m0G0d0T0n5r0d5t0F5v6f0?546A3q5a4M5d2~5-6g0{0H6n5A6p5X6d0%6D4D6M5#5V6P620d6v6x5v5x3~6J6B5i3M5|5l6*015Q2K0Q5v0u6N59615p6!646y665{1t403|3*750o3-1t0Q3/7a2W2S1`1|2U0w1%773-1z426O0?2K0E0e0k0w0S4r0G0c0{1l1n1p1r0t5`2~1G3c1A0C1)740t2h0^0F0A0t0b1)2V6w0l7M0T0D0$0;6w0,5`1J3^2,4c1.1V1X1Z7o3p2q2h2j0{2w0y0h5=0x0Q2x0r211c3)3{7o2}3~747?3P5Q486D5)4g5F6X3B4l040u0g0e0l6s2D0u6(576:6C8j6:4J044L5c6T6L6`3P8B5/5!6I6k6K044R5M5 5P0{6?6^8H4j0g0{2r8F4E6D8B8D4N8z8N6+046a8,6o3B4Z6R8L6)8-4C0{0U5j5{3N8=6;470F498;7p4d4f8(8m4}8K8$558M928)5b8+9h984Q7G3b6.5N8A8!0T0b0Q4r4*0F6H4.8k015C5E5y9D698(8@508X8T5R5T6W9t6Q9M9R8{5(0{5+9V9i6F8E975I046i5{5}9D5Q5S0A9N5W0T9=1,9X5*6_9!988o8U270m9B8w8{8y9m3p0E0T388$6V9H8A8Z048#9(5h8%aj601W9w9y5=9A8$0Z8Q9,5~9s8{8B0P9^0?9FaC6E5*8R9-6:5Q0R1S1(aFaAaF5C020m0Q0faFa90{0paR5)270iaP0{8o8q8s2:8v5f8x0{9g8`9#8C9ka3a:a58G9}6{ao9x5;4qa{8c5^0{8:a78I0{aBam688}8 ae9W0{aTaVa)8n8p8r9va.9f9Ka_6Gacbnb1aqb48$b9a@9~bc6D5C0D6DaY0439be2d6hav2|9rax6/az9uapb3asbO8ObDa4a^bdbab79*ad9C9SbzbZb59Ib8bub*bE3pbIbKaabM8$9+bi92aEa bbah9vb29zb?a;8/b_bH0{bJb#0?bLbNb+bfb-byc9bAb!cnbPb^cjaGb`b(9n8}aIbU9DaQc64cc5c3bF04cz2Q8S6l04cicKa8b cm9qbT9.8U0%8WcH4Yc8bYcb6-cZ61958g9acx4k6q6s6u6 6zcxa6b{c78*cca}04b.3mcP6P9ec|a~cTc7c`71cu8ObR9qaJbW04dd4(2B0;0T7kaR6mc%cvcecx0b2a04012z0ja201bxdu1,dy0{010P0w0j2%dFd9d3aFdJdA7Y0A1ZdGdb4cdU017k0jdQdf8.c2dibVa^dm0e2_9v1rds5Dbnd;bq8td^dRa?cA6{d0dZb/dkd8d+8|dSdH8?dl6w65a/b6cobhd.ay929/9Qd!c(0ha#9Y9|eq5Wd;do2DdrdR9p3mbTdjen9Y96ew9_5)2=8_d5cF4met9{d{ef70dn5=7Uehb@04eD3xbU5~c-8V0Aeve6d:6-91988ec/cx8h9b4meV6%a,br2%e!cde1a|a^e4dRd4cOeQ9T6ef8eU6$dec~b,dheEeGcLd}bsec9EdteKedf7e99Jc=9LfdfwcCawemcL2K0 0q0(eOfa6:cJe/cB8/d-fld/e?0{9:bnehd6aD5)9ZftaGfo8u8$e%0|e)c-0TeJfO6{fY9D9`f$f=dce}fhe2akf,eFcE9SfG5tfJcg040zbu4v0x2ha(e0budmbCbuf2d28~8Re+c#e-bng5fI0wfK0|e=3pe@f;f 4ce`c=8m4n4p4rfvficof4ei5WgKgCejg1fmf?8^4(9zf@fMfsf{609d8^btfybv9%fB8Pgo9S6Z6#egd_9Gg$co5Kg:8{eo9;fq8Jg)fqf_e.eP9S8KgXargl925_cDfE6{g=gidRb%f5cLe8gLdvfRfLbjd`h1c@6tg?70g*e99jbwfehvfc6ShEf%8Bhif}hcfPekeEcYaKc!6@grhFhLfgeh0}0o8b762R7m3,0%0)0+04.

Votre figure

Votre tracé sera ici

graph TB
    a