GraphTheo - TP 2015 - H. Glotin et R. Bendadouche

Pour chaque TP, il faut envoyer le compte rendu incluant tous les TPs précédents, dans un seul .pdf, à :
i42graph@gmail.com
Avant de sortir du TP, le "subject" de votre email sera :
I42_TP_numero du TP_votrenom
et le nom du fichier sera :
I42_TP_numeroTP_votrenom.pdf
Bon travail.

Nous travaillerons sous :
sage
qui est un ensemble sous pylab, numpy... notamment pour manipuler des graphes. Vous pouvez cependant répondre en restant sous python seulement, et n'utiliser Sage que pour sa bonne fonction de représentation graphique qui est décrite ici: sagemath tour graphics
A chaque question vous donnerez les codes et des représentations graphiques pertinentes de votre choix. Une bonne partie des points de votre TP portera sur vos illustrations et vos commentaires associés (temps de calcul comparés sur plusieurs exemples...).

Vous ne travaillerez qu'avec des graphes simples non orientés.

TP1 : Fonction de base


1) Ecrire une fonction qui ajoute une arête à un graphe
2) Ecrire une fonction pour Générer un graphe simple (sans boucle) avec une densité souhaitée
3) idem (2) mais G de degré max donné
4) idem (3) mais on contraint AUSSI par le degré min

TP2 : Polynôme chromatique d'une clique


5) Ecrire une fonction qui teste si un graphe est une clique
6) Ecrire une fonction qui renvoie le polynôme (*) chromatique d'une clique

TP3 : Décomposition de Hajos


7) La décomposition de Hajos permet de construire le polynôme chromatique d'un graphe. Vous allez coder cette fonction.
7.1) Ecrire les fonction Relier et Contracter d'un graphe
7.2) Décomposer un graphe récursivement jusqu'à obtenir des cliques
7.3) Ecrire la fonction finale qui appelle les autres pour calculer le polynôme (*) chromatique du graphe.

NB: (*) Un polynôme sera simplement représenté par un vecteur de taille fixe, le premier élément étant A(0), le Nième A(n-1), est le polynôme SUM_i( A(i)*x^i ). La somme de deux vecteurs sera donc la somme de deux polynômes.

TP4 : Graphe topologique


8.1) Ecrire une fonction qui génère un graphe planaire de densité souhaitée.
8.2) Idem en contraignant en plus le degré minimal et maximal du graphe.
NB: Pour 8.1 et 8.2 on se rappelera que le nombre chromatique d'un graphe planaire est au pire égal à 4.
8.3) Vous illustrerez plusieurs exécutions de vos fonctions 8.1 et 8.2.
8.4) Est-ce que Sage propose toujours la représentation topologique du graphe ?

TP5 : Polynôme chromatique d'un graphe articulé par une clique


9) On notera AKn un graphe articulé par un ensemble d'articulation qui est une clique Kn.
9.1) Suivant la formule du polynôme chromatique d'AKn en fonction de ses pièces, écrire la fonction qui prend en arguments les polynômes chromatiques des pièces d'AKn et Kn, et qui retourne le polynôme chromatique d'AKn (on considèrera des polynômes de degré < 20 ).
9.2) Ecrire une fonction qui construit un graphe AKn en prenant des graphes construits par vos fonctions précèdentes (considérer au plus 5 graphes (5 pièces), et une clique d'ordre < 10).
9.3) Calculer de manière brute avec votre fonction Hajos le polynôme chromatique de votre graphe AKn (mesurer le temps de calcul nécessaire).
9.4) Exécuter (9.1) sur votre graphe AKn. Commenter les temps de calcul nécessaires en (9.3) versus (9.4).