99 lines
3.5 KiB
OCaml
99 lines
3.5 KiB
OCaml
(* Faisons des graphes ! Parce que c'est rigolo ! *)
|
|
|
|
type besoins = (int * int) array;;
|
|
|
|
|
|
let conflit s1 s2 = let (a,b)=s1 and (c,d) = s2 in b>c;;
|
|
|
|
(* I.C.B
|
|
┌─┐ ┌─┐ ┌─┐
|
|
┌───┤1 ├───┐ ┌───┤5 ├───┤7 │
|
|
│ └┬┘ │ │ └┬┘ └┬┘
|
|
│ │ │ │ │ / │
|
|
┌─┐ │ ┌┴┐ ┌┴┐ │ │ │
|
|
│0 │ │ │3 ├───┤4 │ │ │ │
|
|
└─┘ │ └┬┘ └┬┘ │ │ │
|
|
│ │ │ │ │ / │
|
|
│ ┌─┐ │ │ ┌┴┤ ┌┴┐
|
|
└───┤2 ├───┘ └───┤6 ├───┤8 │
|
|
└─┘ └─┘ └─┘
|
|
*);;
|
|
|
|
let construit_graphe (s:besoins) =
|
|
let n = Array.length s in
|
|
let graphe = Array.make n [] in
|
|
for i = 0 to n-2 do
|
|
for j = i+1 to n-1 do
|
|
if conflit s.(i) s.(j) then
|
|
begin
|
|
graphe.(i) <- j::graphe.(i);
|
|
graphe.(j) <- i::graphe.(j)
|
|
end
|
|
done
|
|
done;
|
|
graphe;;
|
|
|
|
(*D1)
|
|
Les deux colorations obtenues sont:
|
|
(0,2,1,0,1,0,0) et (0,1,2,0,1,0,2,1,0).
|
|
Elles sont bien minimales car de longueur trois, et les
|
|
deux graphes contiennent un cycle de longueur 3
|
|
A-B-C-A, qui nécessite que les couleurs de
|
|
A,B et C soient distinctes deux à deux.*);;
|
|
|
|
|
|
(*D2)*)
|
|
let rec appartient l i = match l with
|
|
| [] -> false
|
|
| e::s -> (e=i)||(appartient s i) (* On prend parti de l'évaluation molle *)
|
|
;;
|
|
let plus_petit_absent l =
|
|
let rec aux l i = if appartient l i then aux l (i+1) else i in
|
|
aux l 0;;
|
|
let couleurs_voisins aretes couleurs i =
|
|
let rec aux voisins couleurs reste = match voisins with
|
|
| [] -> reste
|
|
| v::s -> aux s couleurs (if (couleurs.(v) = (-1)) then reste else (couleurs.(v)::reste))
|
|
in aux aretes.(i) couleurs [];;
|
|
|
|
let couleur_disponible aretes couleurs i =
|
|
plus_petit_absent (couleurs_voisins aretes couleurs i);;
|
|
|
|
(*E1)
|
|
G ne possède pas d'arete:
|
|
χ(G) = 1, on colorie tout de la meme couleur.
|
|
ω(G) = 1, si on peut prendre deux éléments distincts
|
|
x et y dans une clique, alors {x,y} ∈ A = ∅.
|
|
G est un graphe complet:
|
|
χ(G) = n, on colorie tout d'une couleur différente
|
|
C'est la solution optimale car un coloriage d'un
|
|
graphe complet doit etre injectif, puisque
|
|
i≠j ⟹ {i,j} ∈ A ⟹ c(i)≠c(j), et donc l'image du
|
|
coloriage est nécessairement superieure à n.
|
|
ω(G) = n, car S est une clique par définition de complet.*);;
|
|
|
|
(*E2)
|
|
χ(G) ≥ ω(G)
|
|
La restriction à un sous-graphe (on enlève des sommets
|
|
et on ne garde que les arretes internes) d'un coloriage est
|
|
toujours un coloriage (car propriété universelle).
|
|
Or, considérons une clique de taille maximale C, alors le
|
|
sous-graphe associé à cette clique est complet, et donc la
|
|
restriction du coloriage à cette partie à nécessairement plus de
|
|
couleurs que la taille de la clique. Donc le coloriage original a
|
|
plus de couleurs que la taille de la plus grande des cliques. *);;
|
|
|
|
(*E3) *)
|
|
|
|
let rec inclus a b = match a with
|
|
| [] -> true
|
|
| e::s -> (appartient b e)&&(inclus s b);;
|
|
let rec est_clique arretes xs = match xs with
|
|
| [] -> true
|
|
| e::s -> (inclus s arretes.(e))&&(est_clique arretes s);;
|
|
|
|
(*II.A) (0,1,2,0,1,0,2,1,0)*)
|
|
|
|
|
|
let ex1 = [| (0,3);(1,3);(2,5);(4,7);(6,10);(8,9);(11,12)|];;
|
|
construit_graphe ex1;; |