L3 MIASHS, Algorithme et Programmation 3, année 2023

Théorie des graphes et programation objet

L’objectif de ce DM est de construire une classe de Graphe en python. Cette classe va fortement s’inspirer de networkx que vous pouvez regarder pour l’occasion.

Un graph est une paire \((V, E)\) où \(V\) est l’ensemble des noeuds et \(E\subseteq \mathcal{P}_2(V)\) l’ensemble des arêtes qui sont des sous-ensembles de taille \(2\) de \(V\).

Une classe de Graph non dirigé

Nous allons stoquer les données du graphe dans un dictionnaire de la forme suivante:

{ 
    0: {1, 2, 3}, 
    1: {0, 2},
    2: {0, 1},
    3: {0}
}

Ce graphe est representé dans la figure suivante:

Créez une classe de Graphe avec les méthodes et propriétés suivantes:

  1. Votre classe est initialisable avec un itérateur ou iterable d’arêtes.
  2. Une propriété nodes qui retourne l’ensemble des noeuds
  3. Une propriété edges qui retourne une liste d’arêtes
  4. Une propriété size qui retourne le nombre de noeuds
  5. Faites en sorte que pour un graphe G, G[n] retourne la liste des voisins de n
  6. Faites en sorte que pour un graphe G, n in G verifie que n est un noeud de G.
  7. Implémenter une méthode subgraph qui prends un iterable de noeud et retourne le graphe restreint à ses noeuds.

Pour le graphe de l’exemple ci-dessus:

G.subgraph([0, 1, 2]) retourne le graphe:

Un peu d’algoritmique

La connexité

Un graphe est connexe s’il existe un chemin entre toutes paire de noeuds.

  1. Implémenter une propriété is_connected qui vérifie que le graphe est connexe.

Essayez sans regarder NetworkX ni wikipédia dans un premier temps.

  1. Une composante connexe est un sous-graphe connexe du graphe. Écrire une méthode connected_components qui retourne un itérateur de graphes qui sont chacun une composante connexe du graphe initial, sans répétition. C’est-à-dire, chaque noeud est dans exactement un des sous-graphe.

Les chaines

Un graphe est une chaîne si:

Montrez que un graphe est une chaine si et seulement il est connexe et s’il existe deux noeuds avec un voisinage de taille \(1\) et tous les autres avec un voisinage de taille \(2\).

En déduire un algorithme en \(O(n)\) pour vérifier qu’un graphe est une chaine

Les arbres et les forêts

Un graphe est un arbre si:

Un graphe est une forêt si chacune de ses composantes connexe est une arbre.

Proposer une implémentation naïve de methodes is_tree et is_forest. Analyez la complexité.

Montrez qu’un graphe de taille \(n\) est un arbre s’il est connexté et a au plus \(n-1\) arêtes.

Une preuve par induction sur la taille de l’arbre marche bien.

Améliorer vos implémentation avec ce résultat.

Une question difficile (facultatif)

Une \(k\)-coloration d’un graphe \(G=(V, E)\), est une fonction \(c\colon V\to \{ 0, \ldots, k-1\}\) tel que pour tout \(i,j \in V\), si \(\{i,j\}\) \(E\) alors \(c(i)\neq c(j)\).

Proposer un algorithme qui calcule une \(3\)-coloration de votre graphe si elle existe. Analyser la complexité.


Compiled the: mar. 19 mars 2024 16:13:25 CET