Loading [MathJax]/jax/output/HTML-CSS/fonts/STIX-Web/fontdata.js

Exercice 1

Concernant le graphe ci-dessus :

  • Combien de sommets comporte-t-il ?
  • Combien d'arcs comporte-t-il ?
  • Est-il orienté ?
  • Quels sont les voisins de F ?
  • Donner trois chemins différents allant de A jusqu'à E.
  • Donner un cycle.
  • Donner un exemple de chemin simple et élémentaire.
  • Donner un exemple de chemin ni simple ni élémentaire.
  • Donner un exemple de chemin simple mais non élémentaire.
  • Ce graphe est-il connexe ?
  • Ce graphe est-il fortement connexe ?
Solution
  • il comporte 6 sommets,
  • il comporte 11 arcs,
  • oui il est orienté,
  • les voisins de F sont les sommets E et D,
  • voici trois chemins possibles :
    • A --> F --> E,
    • A --> D --> E,
    • A --> C --> F --> D --> E,
  • un cycle : E --> B --> D --> E,
  • un chemin simple et élémentaire : A --> F --> E --> D,
  • un chemin ni simple, ni élémentaire : A --> F --> E --> D --> F --> E --> B,
  • un chemin simple mais non élémentaire : C --> F --> D --> F --> E,
  • oui ce graphe est connexe,
  • non ce graphe n'est pas fortement connexe : par exemple il n'existe pas de chemin partant du sommet B et arrivant au sommet A.

Exercice 2

Concernant le graphe ci-dessus :

  • Combien de sommets comporte-t-il ?
  • Combien d'arcs comporte-t-il ?
  • Est-il orienté ?
  • Quels sont les voisins de F ?
  • Donner trois chemins différents allant de A jusqu'à E.
  • Donner un cycle.
  • Donner un exemple de chemin simple et élémentaire.
  • Donner un exemple de chemin ni simple ni élémentaire.
  • Donner un exemple de chemin simple mais non élémentaire.
  • Ce graphe est-il connexe ?
  • Ce graphe est-il fortement connexe ?
Solution
  • il comporte 9 sommets,
  • il comporte 15 arcs,
  • oui il est orienté,
  • les voisins de F sont les sommets C, E et Z,
  • voici trois chemins possibles :
    • A --> F --> E,
    • A --> F --> Z --> G --> F --> E,
    • A --> F --> Z --> G --> E,
  • un cycle : A --> F --> E --> D --> A,
  • un chemin simple et élémentaire : A --> F --> E --> D,
  • un chemin ni simple, ni élémentaire : G --> F --> E --> D --> A --> F --> E --> B,
  • un chemin simple mais non élémentaire : G --> F --> E --> D --> A --> F --> Z,
  • oui ce graphe est connexe,
  • oui ce graphe est fortement connexe : quels que soient les sommets de départ et d'arrivée, on peut trouver un chemin reliant le départ à l'arrivée.

Exercice 3

Les trois graphes ci-dessous sont-ils identiques ?

Graphe n°1 Graphe n°2 Graphe n°3
Solution

Oui ils sont identiques : les sommets sont les mêmes et les arcs reliant les différents sommets sont identiques d'un graphe à l'autre.

Exercice 4

Donner un exemple de graphe orienté fortement connexe comportant 5 sommets et moins de 10 arcs.

Est-ce possible avec strictement moins de 6 arcs ?

Solution

Avec moins de dix arcs :

Avec seulement cinq arcs :

Exercice 5

Concernant le graphe ci-dessus :

  • Est-il orienté ?
  • Donner trois chemins différents allant de 2 jusqu'à 5.
  • Donner un cycle.
  • Donner un exemple de chemin simple et élémentaire.
  • Donner un exemple de chemin ni simple ni élémentaire.
  • Donner un exemple de chemin simple mais non élémentaire.
  • Ce graphe est-il connexe ?
Solution
  • non il n'est pas orienté,
  • voici trois chemins possibles :
    • 2 --> 4 --> 1 --> 5,
    • 2 --> 6 --> 1 --> 5,
    • 2 --> 6 --> 4 --> 1 --> 3 --> 5,
  • voici un cycle : 6 --> 1 --> 4 --> 6,
  • voici un exemple de chemin simple et élémentaire : 2 --> 4 --> 1 --> 5,
  • voici un exemple de chemin ni simple ni élémentaire : 2 --> 4 --> 1 --> 6 --> 4 --> 1 --> 3,
  • voici un exemple de chemin simple mais non élémentaire : 6 --> 1 --> 5 --> 3 --> 1 --> 4,
  • oui ce graphe est connexe.

Exercice 6

Donner un exemple de graphe orienté comportant 6 sommets et 6 composantes connexes.

Solution

Il suffit que les six sommets ne soient reliés à aucun des autres sommets :

Exercice 7

Dessiner tous les graphes non orientés ayant exactement trois sommets.

Solution 
   A
  
B     C
    
    
   A             A              A
 /                 \         
B     C       B     C        B --- C
    
    
   A             A              A
 /   \             \          /
B     C       B --- C        B --- C
    
    
   A     
 /   \    
B --- C

Exercice 8

Combien y a-t-il de graphes orientés ayant exactement trois sommets ?

Solution

Sur un graphe orienté à trois sommets, il y a potentiellement six arcs.

Par exemple, si le graphe comporte trois sommets A, B et C il y a les six arcs potentiels suivants :

A --> B      B --> A      A --> C      C --> A      B --> C      C --> B

Un graphe orienté à trois sommets est donc défini par la présence, ou l'absence, de chacun de ces six arcs potentiels. Un tel graphe peut donc être modélisé par une séquence de six bits.

Par exemple avec le graphe aux sommets A, B et C évoqué ci-dessus la séquence 101001 signifierait qu'il y'a les arcs A --> B, A --> C et C --> B.

Il y a donc autant de graphes orientés à trois sommets que de séquences de six bits, soit $2^6 = 64$ graphes orientés à trois sommets.

Remarque : C'est aussi le nombre de matrices d'adjacence de la forme :

[[ 0, a, b ],
 [ d, 0, c ],
 [ e, f, 0 ]]
```
où `a, b, c, d, e` et `f` sont à choisir parmi `0` ou `1` ... soit également @@1@@ matrices possibles.
 </div>
</details>

Exercice 9

Donner la matrice d'adjacence booléenne du graphe orienté représenté ci-dessus.

Donner ensuite son dictionnaire d'adjacence en prenant des tableaux (list Python) pour stocker les voisins de chaque sommet.

Solution 
M = [[False, False, True,  False, False],
     [False, False, False, True,  False],
     [True,  True,  False, False, False],
     [True,  False, False, False, False],
     [True,  True,  False, True,  False]]
    
    
d = {0: [2],
     1: [3],
     2: [0, 1],
     3: [0],
     4: [0, 1, 3]}

Exercice 10

Donner la matrice d'adjacence booléenne du graphe non-orienté représenté ci-dessus.

Donner ensuite son dictionnaire d'adjacence en prenant des tableaux (list Python) pour stocker les voisins de chaque sommet.

Solution 
M = [[False, False, True,  True,  True],
     [False, False, True,  True,  True],
     [True,  True,  False, False, False],
     [True,  True,  False, False, True],
     [True,  True,  False, True,  False]]
    
    
d = {0: [2, 3, 4],
     1: [2, 3, 4],
     2: [0, 1],
     3: [0, 1, 4],
     4: [0, 1, 3]}

Exercice 10

Donner la matrice d'adjacence pondérée du graphe orienté représenté ci-contre. On prendra 0 comme coefficient pour désigner l'absence d'arc entre deux sommets.

Donner ensuite son dictionnaire d'adjacence en prenant des dictionnaires pour stocker les voisins de chaque sommet ainsi que les poids des arcs.

Solution 
M = [[0, 0, 4, 0, 0],
     [0, 0, 0, 7, 0],
     [2, 1, 0, 0, 0],
     [9, 0, 0, 0, 0],
     [5, 3, 0, 8, 0]]
    
    
d = {0: {2:4},
     1: {3:7},
     2: {0:2, 1:1},
     3: {0:9},
     4: {0:5, 1:3, 3:8}

Exercice 12

Dessiner le graphe non orienté correspondant au dictionnaire d'adjacence suivant :

dic = { 1 :[2, 3, 5],
        2 :[1, 3, 5],
        3 :[1, 2, 4],
        4 :[3],
        5 :[2, 1]}

Comment se traduit, dans le dictionnaire, le fait que le graphe est non orienté ?

Solution

Le fait que le graphe n'est pas orienté se traduit par le fait que si un sommet i est présent dans dic[j] alors le sommet j est présent dans dic[i].

Exercice 13 :

Dessiner le graphe non orienté correspondant à la matrice d'adjacence suivante :

mat = [[0, 1, 1, 0, 0, 1],
       [1, 0, 1, 1, 0, 0],
       [1, 1, 0, 0, 0, 0],
       [0, 1, 0, 0, 1, 1],
       [0, 0, 0, 1, 0, 0],
       [1, 0, 0, 1, 0, 0]]

Comment se traduit, dans la matrice, le fait que le graphe est non orienté ?

Solution

Le fait que le graphe n'est pas orienté se traduit par le fait que si mat[i][j] = 1 alors mat[j][i] = 1. Dit plus simplement la matrice est symétrique par rapport à sa diagonale \.

Exercice 14 :

On dispose d'une classe Graphe implémentant des graphes orientés avec des dictionnaires d'adjacence. Les méthodes disponibles sont :

  • ajouter_sommet(self, s1) : ajoute le sommet s1 au graphe,
  • ajouter_arc(self, s1, s2) : ajoute l'arc s1 --> s2 au graphe (et les sommets s1 et s2 si besoin),
  • existe_arc(self, s1, s2) : renvoie True si l'arc s1 --> s2 existe et renvoie False sinon,
  • voisins(self, s1) : renvoie un tableau (list python) des sommets voisins du sommet s1,
  • schema(self) : produit un affichage graphique du graphe.
Entrée[ ]:

Donner une séquence d'instructions permettant d'affecter à g le graphe orienté représenté ci-dessous.

Entrée[ ]:
Solution 
g = Graphe()
g.ajouter_arc(1, 3)
g.ajouter_arc(1, 5)
g.ajouter_arc(3, 5)
g.ajouter_arc(5, 2)
g.ajouter_arc(2, 3)
g.ajouter_arc(3, 2)
g.ajouter_sommet(4)
g.schema()

Exercice 15

On dispose d'une classe Graphe implémentant des graphes orientés avec des listes d'adjacence (sous forme de dictionnaire). Les méthodes disponibles sont :

  • ajouter_sommet(self, s1) : ajoute le sommet s1 au graphe,
  • ajouter_arc(self, s1, s2) : ajoute l'arc s1 --> s2 au graphe (et les sommets s1 et s2 si besoin),
  • existe_arc(self, s1, s2) : renvoie True si l'arc s1 --> s2 existe et renvoie False sinon,
  • voisins(self, s1) : renvoie un tableau (list python) des sommets voisins du sommet s1,
  • schema(self) : produit un affichage graphique du graphe.

Cette classe dispose par ailleurs d'un seul attribut _dic correspondant à la liste d'adjacence.

Ajouter à cette classe les méthodes suivantes :

  • nb_sommets(self) : renvoie le nombre de sommets du graphe,
  • degre_sortant(self, s) : renvoie le nombre d'arcs issus du sommet s,
  • nb_arcs(self) : renvoie le nombre total d'arcs du graphe.

puis tester vos méthodes en effectuant des instructions bien choisies.

Entrée[ ]:
Entrée[ ]:
Solution 
from vizu_graphe import VizuGraphe

class Graphe:
    '''Graphe orienté représenté par un dictionnaire d'adjacence'''
    
    def __init__(self):
        self._dic = dict()
        
    def ajouter_sommet(self, s):
        if s not in self._dic:
            self._dic[s] = []
    
    def ajouter_arc(self, s1, s2):
        self.ajouter_sommet(s1)
        self.ajouter_sommet(s2)
        self._dic[s1].append(s2)
    
    def existe_arc(self, s1, s2):
        return s1 in self._dic.keys() and s2 in self._dic[s1]
    
    def voisins(self, s):
        return self._dic[s]
    
    def nb_sommets(self):
        return len(self._dic)
        
    def degre_sortant(self, s):
        return len(self._dic[s])
        
    def nb_arcs(self):
        somme = 0
        for s, voisins in self._dic.items():
            somme = somme + len(voisins)
        return somme
    
    def schema(self):
        VizuGraphe('liste', self._dic, env='basthon', oriente = True)

et pour tester l'implémentation effectuée on peut par exemple exécuter les instructions ci-dessous :

g = Graphe()

g.ajouter_arc(1, 3)
g.ajouter_arc(1, 5)
g.ajouter_arc(3, 5)
g.ajouter_arc(5, 2)
g.ajouter_arc(2, 3)
g.ajouter_arc(3, 2)
g.ajouter_sommet(4)


print(g.nb_sommets())
print(g.degre_sortant(1))
print(g.nb_arcs())

g.schema()

Exercice 16

On dispose d'une classe Graphe implémentant des graphes orientés avec des matrices d'adjacence. Les méthodes disponibles sont :

  • ajouter_arc(self, s1, s2) : ajoute l'arc s1 --> s2 au graphe (et les sommets s1 et s2 si besoin),
  • existe_arc(self, s1, s2) : renvoie True si l'arc s1 --> s2 existe et renvoie False sinon,
  • voisins(self, s1) : renvoie un tableau (list python) des sommets voisins du sommet s1,
  • schema(self) : produit un affichage graphique du graphe.

Cette classe dispose par ailleurs d'un seul attribut _mat correspondant à la liste d'adjacence.

Ajouter à cette classe les méthodes suivantes :

  • nb_sommets(self) : renvoie le nombre de sommets du graphe,
  • degre_sortant(self, s) : renvoie le nombre d'arcs issus du sommet s,
  • nb_arcs(self) : renvoie le nombre total d'arcs du graphe.

puis tester vos méthodes en effectuant des instructions bien choisies.

Entrée[ ]:
Entrée[ ]:
Solution 
from vizu_graphe import VizuGraphe

class Graphe:
    '''Graphe orienté représenté par un dictionnaire d'adjacence'''
    
    def __init__(self, n):
        "initialise un graphe de taille n"
        self._mat = [[False for i in range(n)] for j in range(n)]
    
    def ajouter_arc(self, s1, s2):
        self._mat[s1][s2] = True
    
    def existe_arc(self, s1, s2):
        return s1 < len(self._mat) and s2 < len(self._mat) and self._mat[s1][s2]
    
    def voisins(self, s):
        return [j for j in range(len(self._mat)) if self._mat[s][j] == True]
    
    def nb_sommets(self):
        return len(self._mat)
        
    def degre_sortant(self, s):
        return len(self.voisins(s))
        
    def nb_arcs(self):
        somme = 0
        for lig in range(len(self._mat)):
            for col in range(len(self._mat)):
                if self._mat[lig][col]:
                    somme = somme + 1
        return somme
    
    def schema(self):
        VizuGraphe('matrice_bool', self._mat, env='basthon', oriente = True)

et pour tester l'implémentation effectuée on peut par exemple exécuter les instructions ci-dessous :

g = Graphe(6)

g.ajouter_arc(0, 1)
g.ajouter_arc(1, 3)
g.ajouter_arc(1, 5)
g.ajouter_arc(3, 5)
g.ajouter_arc(5, 2)
g.ajouter_arc(2, 3)
g.ajouter_arc(3, 2)



print(g.nb_sommets())
print(g.degre_sortant(1))
print(g.nb_arcs())

g.schema()