from dirmaths import *
import numpy as np
Comme au TP précédent, nous aurons besoin de dirmaths
, numpy
et de vos fonctions du TP1.
Problèmatique :
Un problème de coloration consiste à affecter une couleur à chaque sommet d'un graphe de sorte que deux sommets voisins soient de couleurs différentes. L'objectif est de minimiser le nombre de couleurs utilisées.
color
¶On donne la matrice Mat
du graphe non orienté G
suivant :
Mat = np.array([[0,1,1,0,1,1],[1,0,1,1,0,0],[1,1,0,0,0,1],[0,1,0,0,0,0],[1,0,0,0,0,0],[1,0,1,0,0,0]])
display(Mat,directed=False,title="Gblanc")
La fonction display()
possède un paramètre color
, qui reçoit une liste d'entiers associés à des couleurs.
liste_couleur = [5,2,2,1,7,4]
display(Mat,directed=False,color=liste_couleur,title="G_couleur")
Explication :
A noter qu'un même entier ne sera pas toujours associé à la même couleur !
Mais le plus grand entier donné sera toujours associé au magenta, les autres couleurs établissant une correspondance entre entiers et positions sur le spectre lumineux.
Le nombre 0 correpond lui au blanc : on l'utilisera comme absence de couleur.
couleur2 = [5,0,2,1,15,4]
display(Mat,directed=False,color=couleur2,title="G_couleur2")
Les fonctions suivantes devront retourner une liste d'entiers comportant autant d'éléments que le nombre de sommets du graphe.
Cette liste sera affectée à l'argument color
de la fonction display
.
exo1(M,sommets)
qui retourne une liste d'entiers permettant : Exemple :
couleur_exo1 = exo1(Mat,[0,2,4])
print(couleur_exo1)
[1, 0, 2, 0, 3, 0]
display(Mat,directed=False,color=couleur_exo1,title="G_exo1")
exo2(M,x)
qui retourne une liste d'entiers permettant: Exemple :
couleur_exo2 = exo2(Mat,2)
print(couleur_exo2)
[2, 3, 1, 0, 0, 4]
display(Mat,directed=False,color=couleur_exo2,title="G_exo2")
exo3(M)
qui retourne une liste d'entiers permettant: Exemple :
couleur_exo3 = exo3(Mat)
print(couleur_exo3)
[1, 0, 0, 2, 2, 0]
display(Mat,directed=False,color=couleur_exo3,title="G_exo3")
exo4(M,sommet,L)
qui retourne une liste d'entiers permettant de colorer le sommet sommet
avec la couleur non blanche associée au plus petit entier qui n'est pas dans la liste L
.Exemple :
couleur_exo4 = exo4(Mat,2,[1,4,5,2])
### le sommet 2 devrait être colorer avec la couleur 3
### (3 est bien le plus petit entier qui n'est pas dans [1,4,5,2])
print(couleur_exo4)
[0, 0, 3, 0, 0, 0]
definition de gloutonSimple(g) S = liste des sommets de g pour tout x de S pc = première couleur non utilisée par les voisins de x colorer le sommet x avec pc fin pour tout retourner la liste des couleurs de g
Créer une fonction gloutonSimple(M)
qui retourne une liste d'entiers, permettant de colorer un graphe de matrice M
grâce à l'algorithme glouton simplifié.
Tester gloutonSimple(Mat)
.
Exemple :
couleur_gloutonSimple_mat = gloutonSimple(Mat)
display(Mat,directed=False,title='gloutonSimple_G',color=couleur_gloutonSimple_mat)
Assurez vous de bien obtenir une coloration cohérente !
display(M0,directed=False, title='G0')
couleur_gloutonSimple = gloutonSimple(M0)
display(M0,directed=False,title='gloutonSimple_G0',color=couleur_gloutonSimple)
La coloration obtenue est-elle optimale ?
display(M1,directed=False, title='G1')
couleur_gloutonSimple = gloutonSimple(M1)
display(M1,directed=False,title='gloutonSimple_G1',color=couleur_gloutonSimple)
Grâce au mot clef lambda
, il est possible de créer à la volée des fonctions anonymes, c'est à dire des fonctions déclarées sans nom.
Sa syntaxe est : lambda arguments:expression
Les arguments peuvent être multiples, mais il n'y aura toujours qu'une seule expression
Exemples :
###Construisons une fonction qui calcule le carré d'un nombre
def carre(x):
return x**2
###la même chose avec une fonction lambda
lambda x : x**2
<function __main__.<lambda>(x)>
print(carre(3), (lambda x : x**2)(3))
9 9
###Construisons une fonction qui calcule la somme des carrés de deux nombres
def somme_carres(x,y):
return x**2 + y**2
###la même chose avecune fonction lambda
lambda x,y : x**2 + y**2
<function __main__.<lambda>(x, y)>
print(somme_carres(2,3), (lambda x,y : x**2 + y**2)(2,3))
13 13
La fonction sorted()
permet de trier une liste.
sorted([2,0,4,9,5]) #tri par ordre croissant, par défaut
[0, 2, 4, 5, 9]
sorted([2,0,4,9,5],reverse=True) #tri par ordre décroissant
[9, 5, 4, 2, 0]
sorted(["AB","AAA","A","BA","B"]) #tri par ordre alphabétique
['A', 'AAA', 'AB', 'B', 'BA']
La fonction sorted()
admet un paramètre optionnel key
.
Ce paramètre prend comme argument une fonction, qui va s'appliquer sur les valeurs de la liste à trier. Le tri se fait ensuite.
Exemples :
#Exemple 1
#tri suivant la longuer de la chaîne de caractère.
sorted(["AB","AAA","A","BA","B"], key=len)
['A', 'B', 'AB', 'BA', 'AAA']
#Exemple 2
#définition de la fonction qui calcule le reste dans la division euclidienne modulo 3
def modulo3(n):
return(n%3)
#tri suivant la valeur du reste modulo 3
sorted([2,0,4,9,5],key=modulo3)
[0, 9, 4, 2, 5]
#Exemple 3
#même exemple que ci-dessus, mais avec l'utilisation d'une fonction lambda
sorted([2,0,4,9,5],key= (lambda n : n%3) )
[0, 9, 4, 2, 5]
#Exemple 4
#tri suivant la distance de l'entier par rapport à 5
sorted([2,0,4,9,5],key= (lambda n : abs(n-5)) )
[5, 4, 2, 9, 0]
tri_degre(M,Bool)
qui renvoie la liste des sommets triés suivant leur degré (dans l'ordre décroissant si Bool = True
, croissant sinon).Exemple :
display(M1,directed=False, title='G1')
tri_degre(M1,True)
[3, 2, 4, 0, 1]
définition de glouton(g) S = liste ordonnée des sommets, suivant la valeur décroissante de leur degré. pour tout x de S pc = première couleur non utilisée par les voisins de x colorer le sommet x avec pc fin pour tout retourner la liste des couleurs de g
glouton(M)
qui retourne une liste d'entiers, permettant de colorer un graphe de matrice M
grâce à l'algorithme glouton.Exemple :
couleur_glouton = glouton(M1)
display(M1,directed=False,title='glouton_G1',color=couleur_glouton)
On rappelle que : DSAT(x) = degré de saturation du sommet x = nombre de couleurs différentes dans les voisins de x
défintion de DSATUR(g) S = liste ordonnée des sommets, suivant la valeur décroissante de leur degré. colorer un des sommets de degré max avec la plus petite couleur tant que tous les sommets ne sont pas colorés choisir un sommet x non coloré avec un DSAT max (en cas d'égalité, choisir un sommet de degré max) pc = première couleur non encore utilisée par les voisins de x colorer le sommet x avec pc fin tant que retourner la liste des couleurs de g
def dsatur(g):
n = np.shape(g)[0]
couleur = n*[0]
#liste des sommets par ordre de degrés décroissants
sommets_ord = tri_degre(g,True)
#tant qu'il y a des sommets sans couleur
while 0 in couleur:
#recherche du sommet à colorer, de degré de saturation maximum
dsat = n*[0]
degre_sat_max = 0
sommetchoisi = sommets_ord[0]
for i in sommets_ord:
#si le sommet i est sans couleur
if couleur[i]==0:
vois = voisins(g,i)
#calcul du degré de saturation du sommet i
couleurvois = []
for k in vois:
if couleur[k]>0:
couleurvois = couleurvois+[couleur[k]]
dsat[i] = len(np.unique(couleurvois))
#le sommet i est-il de degre de saturation maximum ?
if dsat[i]>degre_sat_max :
degre_sat_max = dsat[i]
sommetchoisi = i
#couleur des voisins du sommet choisi
vois_sommetchoisi = voisins(g,sommetchoisi)
couleurvois_sommetchoisi = []
for k in vois_sommetchoisi:
couleurvois_sommetchoisi = couleurvois_sommetchoisi+[couleur[k]]
#choix de la plus petite couleur non présente chez les voisins du sommet choisi
j=1
while j in couleurvois_sommetchoisi:
j=j+1
#coloration du sommet choisi avec la couleur trouvée ci-dessus
couleur[sommetchoisi]=j
return couleur
Copier l'algorithme ci-dessus.
Construire la matrice $M_2$ du graphe $G_2$ ci-dessous :
M2 = np.array([[0,1,1,0,0,0],[1,0,0,1,1,0],[1,0,0,1,0,1],[0,1,1,0,1,1],[0,1,0,1,0,1],[0,0,1,1,1,0]])
display(M2,directed=False,title="G2",dispo="neato")
Trouver une coloration du graphe grâce à l'algorithme glouton simplifié.
Trouver une coloration du graphe grâce à l'algorithme glouton.
Trouver une coloration du graphe grâce à l'algorithme DSATUR.
display(M2,directed=False,title="gloutonSimple_G2",dispo="neato",color = gloutonSimple(M2))
display(M2,directed=False,title="glouton_G2",dispo="neato",color = glouton(M2))
display(M2,directed=False,title="DSATUR_G2",dispo="neato",color = dsatur(M2))
Un graphe est dit planaire ssi il existe une représentation de ce graphe où aucune arête n'en coupe une autre. Le théorème des 4 couleurs dit qu'un tel graphe peut être coloré avec au plus 4 couleurs.
on pourra utiliser la liste des pays ["Fr","Lux","Bel","All","PB","Sui","It"]
, à rentrer dans le paramètre label
de la fonction display
.
On considère le mini-sudoku de 16 cases suivant :
On cherche à remplir ce sudoku avec 4 couleurs en considérant les contraintes habituelles :
deux cases d'une même ligne ne peuvent pas avoir la même couleur
deux cases d'une même colonne ne peuvent pas avoir la même couleur
deux cases d'un même carré ne peuvent pas avoir la même couleur
On donne ci-dessous la matrice d'adjacence sud
du graphe à 16 sommets correspondant à une grille de mini-sudoku, sachant que deux sommets sont reliés ssi ils ne peuvent pas avoir la même couleur.
Exemple :
le sommet 0 est relié aux sommets 1, 2, 3, 4, 5, 8 et 12.
le sommet 10 est relié aux sommets 2, 6, 8, 9 ,11, 14 et 15.
sud=np.array([[0,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0],
[1,0,1,1,1,1,0,0,0,1,0,0,0,1,0,0],
[1,1,0,1,0,0,1,1,0,0,1,0,0,0,1,0],
[1,1,1,0,0,0,1,1,0,0,0,1,0,0,0,1],
[1,1,0,0,0,1,1,1,1,0,0,0,1,0,0,0],
[1,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0],
[0,0,1,1,1,1,0,1,0,0,1,0,0,0,1,0],
[0,0,1,1,1,1,1,0,0,0,0,1,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0],
[0,1,0,0,0,1,0,0,1,0,1,1,1,1,0,0],
[0,0,1,0,0,0,1,0,1,1,0,1,0,0,1,1],
[0,0,0,1,0,0,0,1,1,1,1,0,0,0,1,1],
[1,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1],
[0,1,0,0,0,1,0,0,1,1,0,0,1,0,1,1],
[0,0,1,0,0,0,1,0,0,0,1,1,1,1,0,1],
[0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,0]])
DSATUR
donné plus haut, construire une fonction sudoku(sommets, couleurs)
, qui propose une coloration du sudoku, en respectant les contraintes initiales suivantes : sommets
contient la liste de sommets déja colorés couleurs
contient la liste des couleurs associées aux sommets précédents.Exemple :
#dans l'exemple de l'illustration ci-dessus, les sommets déja colorés sont les sommets 0,2,4,11 et 13, associés aux couleurs 1,2,3,4 et 1
sudoku([0,2,4,11,13],[1,2,3,4,1])
[1, 4, 2, 3, 3, 2, 4, 1, 2, 3, 1, 4, 4, 1, 3, 2]
sudoku_tableau(sommets, couleurs)
qui propose une représentation du sudoku sous forme de tableau 4 par 4.Exemple :
#Affichage du sudoku résolu
sudoku_tableau([0,2,4,11,13],[1,2,3,4,1])
array([[1, 4, 2, 3], [3, 2, 4, 1], [2, 3, 1, 4], [4, 1, 3, 2]])