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:
- Votre classe est initialisable avec un itérateur ou iterable d’arêtes.
- Une propriété
nodes
qui retourne l’ensemble des noeuds - Une propriété
edges
qui retourne une liste d’arêtes - Une propriété
size
qui retourne le nombre de noeuds - Faites en sorte que pour un graphe
G
,G[n]
retourne la liste des voisins den
- Faites en sorte que pour un graphe
G
,n in G
verifie quen
est un noeud deG
. - 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.
- 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.
- 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:
- C’est un graphe de taille \(1\)
- C’est un graphe \((V, E)\) dont il
existe un noeud \(n\), tel que son
voisinage est de taille \(1\)
(
len(G[n]) == 1
) et tel que le sous graphe privé de \(n\) est une chaine.
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:
- C’est un graph de taille \(1\)
- C’est un graphe \((V, E)\) dont il existe un noeud \(n\) tel que le sous-graphe privé de \(n\) est une forêt.
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