(* 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;;