Aller au contenu

Graphes et complexité

On rappelle le code de la classe Graphe, tel qu'implémenté à l'aide d'un dictionnaire d'adjacence. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Graphe:
    """ Un graphe représenté par un dictionnaire d'adjacence. """
    def __init__(self):
        self.adj = dict()

    def ajouter_sommet(self, s):
        """ Graphe, str -> Nonetype
        Ajoute le sommet s au graphe self.
        Ne fait rien si s est déjà un sommet du graphe. """
        if not s in self.adj:
            self.adj[s] = []

    def ajouter_arc(self, source, destination):
        """ Graphe, str, str -> Nonetype
        Ajoute l'arc source -> destination au graphe self """
        self.adj[source].append(destination)

Création de graphe

Écrire une méthode ajouter_liste_arcs de la classe Graphe qui ajoute au graphe orienté self tous les arcs (source, destination) présents dans la liste arcs. Si source ou destination n'est pas un sommet du graphe, on prendra soin de créer au préalable le sommet correspondant.

On pourra utiliser sans justification supplémentaire les méthodes ajouter_sommet et ajouter_arc de la classe Graphe.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def ajouter_liste_arcs(self, arcs):
    """ Graphe, [(str, str)] -> Nonetype """
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................
    .............................................................

1
2
3
g = Graphe()
g.ajouter_liste_arcs([('A', 'B'), ('B', 'A'), ('B', 'C'), ('C', 'A')])
print(g.adj)

{'A': ['B'], 'B': ['A', 'C'], 'C': ['A']}

Étude de complexité

On considère la fonction récursive mystere dont on donne le code ci-dessous :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def mystere(liste, elt):
 """ Liste, int -> int """
 if est_vide(liste):
  return 0
 else:
  reste = queue(liste)
  nombre = mystere(reste, elt)
  a = 1 if tete(liste) == elt else 0
  nombre = nombre + a
  return nombre

On rappelle que l'instruction x if b else y renvoie x si le booléen b est True, sinon elle renvoie y.

1
2
print(42 if True else 24)    
print(42 if False else 24)    

42
24

  1. Si liste est la liste (1, 2, 1), et elt l'entier 1, que renvoie mystere(liste, elt) ?

    Dresser un arbre d'appel pour justifier votre réponse.

  2. Si liste est une liste consitutée de \(n\) éléments et elt un entier, on note \(c_n\) le nombre d'opérations élémentaires effectuées lors de l'exécution de l'instruction mystere(liste, elt).

    1. Sans justifier votre réponse, donner \(c_0\).

    2. Pour tout \(n \geq 1\), exprimer \(c_n\) en fonction de \(c_{n - 1}\). Justifier votre réponse à l'aide d'un tableau indiquant pour chaque ligne de code exécutée le nombre d'opérations élémentaires correspondant.

    3. Exprimer \(c_n\) en fonction de \(n\). Quelle est la complexité de la fonction mystere ?