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

.1280133Sytbi,f4_dugj:}he sPar5lvo21/mn0p=c{050l0s0e0w0g0z0u0t0K0z0w0u0u0J010e0g0I010406050u0m0F0F0w0x0d040c0B0z0m0$0B0G050E0-0/0;0?0+0I040 1605190E191b160+0l0g0A0U0W0Y0!0r0g0n0r0z1p0r0e0)050P0f0z0s1k0X0Z011o1q1s1q0e1y1A1w0e0f0B0l0?1x0x170e0r0U0_0u0I0w0G0!0C011C1m010i0R0s0G0w0F0s1w1!1$1+1E1.1A1;1?0)0a0t0v0x0B0I0B0u0g0|0G0t0N1Y0x0x0s0K2b0 1_0G170E1W2o0e1U1T1V0l1{0!1s0G1:281w1h1j0V1D2y0g2A0G1Q1i1w0I2h172m2o2S0,1#2c2G1,2L0x0:0z0)0D2l2W2o2P0s2o2E2r0l2v2x010K1Q1@172:1a2Q2V1$2T2+052_0N2R2W2@0G0)2_0m1A0m0x0u0k0u0B0/0O0u2*310t302X1l1E0B0)0J3o2n3q2m2@0(040L3y371`2Y1E0F0g0)0H3G3r3C0)0p3G3A383J0!0u1)0401250m0n1@3P3B3X013D0h3U3Q3-3L2(3+3W3t0!3D3T102+3V3I3{013Z0)011z0s0m013_422H3.0)3:3 3p3=433@040C4c3s4e3}3;3,43453#0A0s0x1v4p3R044h2S414q1,4m0b4C3-4s4i3z4k4e4w010o0w0m2A4b4P3H4I1E3/4M4l3M040j4)4r3S4t3`4S3!4U4W4Y4.1,4(4!4H2@4m0y4{4%4:4~4R1,4T4y4A4Z2U4u4/040q3G0+0E352.182 0E2}2p2=0 2s2r1P1R2r0w482/1i0*0 0N0P0R0u04.

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

.1280133ytbIqO)N4_7uj:k}8s(ar5lRLvU21mép=cxSi,6fdg[he P]ow/Cn0EB9{050Q0U0d0v0M0y0t0V0J0y0v0t0t0I010d0M0H010406050t0n0F0F0v0w0c040L0Y0y0n0 0Y0$050!16181a1c140H041l1s051v0!1v1x1s140Q0M0B0@0_0{0}0T0M0R0T0y1L0T0d12050/0e0y0U1G0`0|011K1M1O1M0d1U1W1S0d0e0Y0Q1c1T0w1t0d0T0@1f0t0H0v0$0}0D011Y1I010P0;0U0$0v0F0U1S1}1 241!271W2a2c120a0V0W0w0Y0H0Y0t0M1i0$0V0-1{0w0w0U0J2x1l2f0$1t0!1_2K0d1@1?1^0Q2h0}1O0$292u1S1D1F0^1Z2U0M2W0$1:1E1S0H2D1t2I2K2=151~2y2$252+0w190y120V0E2H2_132^2g2{1!2}2 310D341 362I2T013b0v30040V0b3f2J143i390}3l3n0V0k3r3h2_3j3x310x3B3t3D3v3k0Y2~3m310O3I372`1H3a3N3c3o0m3S3u3V3w3X3P3o0s3#3K3%3M3O3y0*3-383/3F040E0%3@3U2%3:3Y0E331m353J3^403`0E3e453g473 2|3)3n0E3q4d3s3T3E4i120E3A4m3C484h3;4r3H4u4f4p4y3{3R4B4o3L4a3!4H3$494q3{3,4M3.4O4E0E3?4S4w3W4E0D3}4u1u2:1l2!2N0Q2R3j0J1:2d1t4,1w4*2@4(4;0-2;4T2|120#0h0C0A0(0C0z0L0l0W0h0L0L0f0)560L3B0V4I3/0Y120I5k5m4011040S3B5s250t2204012r0n0R2d5x4N255u0N5r5J1!5A12010o0v0n2W015I501!5L5N5Z0}5Q5C0B0U0w1R5Y4Z0}5#4u5l5O5(5B011V0U0n5X4(5^015u0X3I4C3L0q120-0P5/4g1!0Z316c3E0P120d0U0t0d0l0J0T0Y0M0K6p0Y0n1W0n0w6h3L5u0u0i0p3I0V6I5@5%3k120R442=6K5:015o045q5?5y5!120+6B3/0F0M124%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:120X7M4e7%7(7F717H7`7C7j7V7!7o6@7~6`8i7J7#4B877O7@7 7+7K7.3g8q3/7;8t7r8t7D7/898k7?8y7|7E70127Y8c8m83853s8p7)718N817T8v2J8x6|5v8A717_8X7{7U7}7W8s8l8g040X0r657a7u0$124;6x5}0w0t0l0t0Y180.0t8f3L6U6W6Q8#7i046#8;8r6*8C8e8.3j5)5D6w5G5 8H8$8R3o8U127A8O8=8Z9x619p5+5-9t9B6C8J8E8L048b8+8d7-993/9p5T5V5H9i8I048^8o6J7u68041Z5,0d9U498}6r6t6v8 6z9l040u8t8|046O9{9w9e7q8)a29:51048~6y9193952c0d989!8$0ia81!9b9c9N6S0t0E12005|0n00a79n3L9p0G6q2E2z0n0V6l6n0V0%9J869)619+9-5-am3w9=6s6uab909{9}aja9a1a%6Z8-8K8j9Paza-7J9 aZ6z929496ah9{alaA5n5pap8w7uasau5E5Gaya*7,a3b45`aD0TaF0QaHaJ0d32aN3s0679aP6La?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/9ab1bz0q0J120j1j0Ub@b39FbeaE0J0V0g0n1 2S0;0V0$000c0V0v0V0H1g0?2Aa@91c(2u2v5|0tb$bpc5bsct9_ada`agcyb^3j9bbCb-0+c346c_6SaR0{9.bza?9?aYcu9`bJ6Dcha0cob-cr7Pa6dk9McNc`aadic}bxa|dt04cBd1cD6Vb28!b4at0400bNb9cz7KdqaBcPbgcR2t6z0V1Wc(2D6(5,0@dgc@1l4}0U2K2/d.4+1E4-2N2P2L1/1;2N0v5|2K4,140!0-0/0;0t04.

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

.1280133Sytbi,6)f4_d7ugj[:khe8 sPar(5]lvow21/mn0p;=c-9050n0w0e0B0g0G0z0y0T0G0B0z0z0S010e0g0Q010406050z0p0N0N0B0C0d040c0I0G0p0:0I0O050M0`0|0~100^0Q04191g051j0M1j1l1g0^0n0g0H0(0*0,0.0v0g0q0v0G1z0v0e0?050Z0f0G0w1u0+0-011y1A1C1A0e1I1K1G0e0f0I0n101H0C1h0e0v0(130z0Q0B0O0.0K011M1w010k0#0w0O0B0N0w1G1.1:1^1O1{1K1~200?0a0y0A0C0I0Q0I0z0g160O0y0X1,0C0C0w0T2l19230O1h0M1*2y0e1(1%1)0n250.1C0O1}2i1G1r1t0)1N2I0g2K0O1!1s1G0Q2r1h2w2y2$0_1/2m2Q1_2V0C0}0G0?0L2v2*0@2)242,1O2.2:0?0K2@1:2_2w2H012~0B2;040b322x0^352|0.383a0l3d342*363j0?0E3m3f3o3h370I2/390?0i3t2`2+1v2}3y2 040o3D3g3G3i3I3A040x3M3v3O3x3z3a0V3m1i2!192O2B0n2F360T1!211h3)1k3%2(1a2^053.0X2#3V2R010u0?0X0k3#3N400J0?0y463 2-0k0?2C0g0m0z0I0|0Y0z4c2{3W0=040D4p3F400O0?0q0C0B0Q0v0w4v364s0j0t3t0y4M4b472-0?1C0z0e0w0m4h0w4F3_334O4d1O0I0?0S3m4$4q404s0s4G3w4y044k4m0e4,3E3642040k3y4|4P2}0?4_204{4!2x4-4w1_0I49042T534%3i4z4B4D4Z2(540.4s0F4L4N4}3w4 510C5j4.4Q5h5C5d4(5g5i5a045c3p0f0?4B0O0q5p3`5r014s4u5L5x3W0N0g2=4=4r0?0h5G5O4R1}5*4/0?5Z5q5k374R0g4T4V4X5U335#5?040j4J5v4N5w5W4@0r5.3w4)044+5L5N4?0?0g68696k3W4 0J1y1K6e3W6c6w406g020q0e0R6z1_5%0?0P6G5I0?1:0n6L5l040O0f0m0H0I5}2T4o5!5W5Y5=5E4A4C4E6(1O4s5-6j635E4S4U4W0C0g4Y6-5s0?4;6#5`6y715D6.0?0F0j6Q016B6D6F6;6b0?6T6V6X2j0O6!5_756~4t6}5{046*5o7s6/7a4@6@5 6`6|745H7q707o7G7t6d7F366g0U7s6I042?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^7s7P7R8e7U8t640F7}2^7 55048q838c647=627g047_7?7p5X776o7$8I6R8T4#8o7b4*7z8x8j8V8z8-7K7S8C2^067!6a5`4 2r0e0p0C188:3p7)827D7-2_0M3|0w2y2Z9b3(1s3*2B2D2z1Z1#2B0B1J9e0M3)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

.128013x3Sytbi,q6)f4_d7ugj[:k}he sPar(5].lRLvow21/mn0p;=c-{050p0z0f0D0h0J0B0A0Y0J0D0B0B0X010f0h0V010406050B0r0S0S0D0E0e040d0N0J0r0^0N0T0A020D0S0V0W0A0K0z120E0j0r0z0B050R0 1113150}0V041t1A051D0R1D1F1A0}0p0h0M0-0/0;0?0y0h0s0y0J1T0y0f0{050(0g0J0z1O0:0=011S1U1W1U0f1$1(1!0f0g0N0p151#0E1B0f0y0-180B0V0D0T0?0P011*1Q010m0*0z0T1g0z1!25272c1,2f1(2i0S2k040a0A0C0E0N0V0N0B0h1b1d0$230E0E0z0Y2F1t2m0T1B0R212R0f1 1~200p2o0?1W0T2h2C1!1L1N0.1+2#0h2%0T1{1M1!0V2K1B2P2R2|0~261d2-2d2=0E120J0{0Q2O300|2 2n321,34360{0P3a273c2P2!013h0D37040c3l2Q0}3o3f0?3r3t0n3w3n303p3C0{0G3F3y3H3A3q0N353s0{0k3M3d311P3g3R3i040q3F1C2`1t2+2U0p2Y3p0Y1{2u0#1M1B2_0z2{3b3)3=0$3}3e3Z0?0w0{0$0m3)3z44010O0{0A4a3O4c0T0m0{3=0J3R0h0z0o0s0E0D0V0y0z4h432.010`040F4z3Y4B0T0{4t4v4x4G3p4D0l0v3M0A4U4g4b4I0{0B0N110%0B0o2V4q1s1u3b4W4i4B0N0{0X3F4/4A330{4*0o4!4$0f4O3P4D4F4-3m3X3I4K4u4w4y562Q58530{0l4T4V5g4j470h3=0o3=0r1(0r0E4,2|4_4H2d4=044@5e045z4P0{0!0x5k4U5m4B46040m3R4^5O4{044 2t515F5H3P0N4e042:5U4X5W5Y4%4)0E4+524c4D4S5F064V5}5$5n041L5q5s5u5w5@4B4D0u675.4#5Z6b1,4D0H5,4:5B4?6j4`3g4m0y0N0h0b5r0N5t0z5v6f0?546A3q5a4M5d2~5-6g0{0i6n5A6p5X6d0%6D4D6M5#5V6P620N6v6x5v5x3~6J6B5i3M5|5l6*015Q2K0f5v0T6N59615p6!646y665{1t403|3*750R3-1t0f3/7a2W2S1`1|2U0D1%773-1z426O0?2K0S0o0m0D0w4r0y0c0{1l1n1p1r0A5`2~1G3c1A0L1)740A2h0^0z0E0A0B1)2V6w0M7M0h0Z0$0;6w0,5`1J3^2,4c1.1V1X1Z7o3p2q2h2j0{2w0d0Y5=0V0f2x0e211c3)3{7o2}3~747?3P5Q486D5)4g5F6X3B4l040T0g0o0M6s2D0T6(576:6C8j6:4J044L5c6T6L6`3P8B5/5!6I6k6K044R5M5 5P0{6?6^8H4j0g0{2r8F4E6D8B8D4N8z8N6+046a8,6o3B4Z6R8L6)8-4C0{0H5j5{3N8=6;470z498;7p4d4f8(8m4}8K8$558M928)5b8+9h984Q7G3b6.5N8A8!0h0B0f4r4*0z6H4.8k015C5E5y9D698(8@508X8T5R5T6W9t6Q9M9R8{5(0{5+9V9i6F8E975I046i5{5}9D5Q5S0E9N5W0h9=1,9X5*6_9!988o8U270s9B8w8{8y9m3p0S0h388$6V9H8A8Z048#9(5h8%aj601W9w9y5=9A8$0l8Q9,5~9s8{8B0t9^0?9FaC6E5*8R9-6:5Q0O1S1(aFaAaF5C020s0f0WaFa90{0UaR5)270paP0{8o8q8s2:8v5f8x0{9g8`9#8C9ka3a:a58G9}6{ao9x5;4qa{8c5^0{8:a78I0{aBam688}8 ae9W0{aTaVa)8n8p8r9va.9f9Ka_6Gacbnb1aqb48$b9a@9~bc6D5C0Z6DaY0439be2d6hav2|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;0h7kaR6mc%cvcecx0B2a04012z0ra201bxdu1,dy0{010t0D0r2%dFd9d3aFdJdA7Y0E1ZdGdb4cdU017k0rdQdf8.c2dibVa^dm0o2_9v1rds5Dbnd;bq8td^dRa?cA6{d0dZb/dkd8d+8|dSdH8?dl6w65a/b6cobhd.ay929/9Qd!c(0Ya#9Y9|eq5Wd;do2DdrdR9p3mbTdjen9Y96ew9_5)2=8_d5cF4met9{d{ef70dn5=7Uehb@04eD3xbU5~c-8V0Eeve6d:6-91988ec/cx8h9b4meV6%a,br2%e!cde1a|a^e4dRd4cOeQ9T6ef8eU6$dec~b,dheEeGcLd}bsec9EdteKedf7e99Jc=9LfdfwcCawemcL2K0 0J0(eOfa6:cJe/cB8/d-fld/e?0{9:bnehd6aD5)9ZftaGfo8u8$e%0|e)c-0heJfO6{fY9D9`f$f=dce}fhe2akf,eFcE9SfG5tfJcg040Ibu4v0V2ha(e0budmbCbuf2d28~8Re+c#e-bng5fI0DfK0|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}0R8b762R7m3,0%0)0+04.

Votre figure

Votre tracé sera ici

graph TB
    a