Voici ci-dessous un graphe non-orienté qui remprésente une modélisation possible du problème des ponts de Königsberg expliqué dans la remarque historique.

1. Donner deux sommets adjacents du graphe ci-dessus.

2. Donner deux sommets non adjacents du graphe ci-dessus.

3. Le graphe ci-dessus est-il un graphe complet ? Pourquoi ?

4. Comment rendre le graphe ci-dessous complet ?

Un des amis de votre réseau travaille pour un distributeur d'électricité.

Il doit proposer à son supérieur une représentation du réseau reliant différentes villes.
Comme il n'y arrive pas trop, il voudrait que vous la lui fassiez.

Pour simplifier le problème, il a déjà renommé les villes en A, B, C, D, E et F. De plus, il vous donne les informations suivantes :

• la ville A est reliée par un réseau électrique aux villes B, E et F,

• la ville B est reliée par un réseau électrique aux villes A, C et D,

• la ville C est reliée par un réseau électrique aux villes B, D, E et F,

• la ville D est reliée par un réseau électrique aux villes B, C et F,

• la ville E est reliée par un réseau électrique aux villes A, C et F,

• la ville F est relié par un réseau électrique aux villes A, C, D et E.

1. Proposer un graphe qui modélise la situation.

2. Ce graphe est-il complet ? Pourquoi ?

1. Quel est l'ordre de ce graphe ?

2. Quel est le degré du sommet $A$ ?

3. Lister les sommets de degré 3 de ce graphe.

1. En s'aidant de la remarque précédente, proposer une fonction ordre en langage Python qui reçoit en paramètre un dictionnaire et renvoie l'ordre de ce graphe.

2. Tester votre fonction ordre en utilisant le graphe de l'exemple introductif, implémenté en langage Python ci-dessus.

1. Écrire une fonction sommets_adjacents qui prend en paramètre un dictionnaire ainsi qu'un sommet sous forme de chaîne de caractères et qui renvoie la liste des sommets adjacents à ce sommet entré comme paramètre.

2. Tester la fonction sommets_adjacents sur le sommet $A$.

3. Proposer des préconditions.

4. Proposer une fonction lister_aretes qui prend en paramètre un dictionnaire et renvoie la liste des arêtes d'un graphe. Une arête sera représentée par un tuple à deux éléments. ( Attention aux doublons)

On considère le graphe non-orienté suivant :

1. Quel est l'ordre du graphe ?

2. Quel nom peut porter la chaîne $B - C - E - B$ ? Quelle est sa longueur ?

3. Déterminer une chaîne de longueur 8 reliant $E$ à $A$

4. Déterminer un cycle d'origine $G$.

5. Le graphe est-il connexe ?

Proposer un graphe qui n'est pas connexe.

Le graphe suivant représente le plan d’une ville. Les arcs du graphe représentent ses avenues commerçantes, en prenant en compte le sens de circulation, et les sommets du graphe les carrefours de ces avenues.

1. Est-ce un graphe orienté ou non-orienté ? Pourquoi ?

2. Quel est l'ordre du graphe ?

3. Proposer un chemin de longueur 4 d'origine $F$ et d'extrémité $B$.

4. Proposer un circuit passant par tous les sommets.

Pour implémenter le graphe de l'exercice précédent, il vous suffit de saisir progressivement les instructions suivantes :

1. Commencer par importer le module networkx, sous l'alias nx ici.

   Code de déblocage de la correction :

2. Créer un graphe orienté vide avec le script nx.DiGraph():

   Code de déblocage de la correction :

3. Ajouter au graphe chaque sommet (appelé node) avec la méthode add_node:

   Code de déblocage de la correction :

4. Ajouter au graphe chaque arc (appelé edge) avec la méthode add_edges_from:

   Code de déblocage de la correction :

   Pour ajouter à un graphe non-orienté des arêtes, il suffit d'utiliser la méthode add.edges au lieu de add.edges_from.

5. Pour visualiser le graphe utiliser ce script:

   nx.draw(graphe, node_size=800,node_color='blue', edge_color='red',with_labels=True)
   plt.show()   # pour visualiser le graphique créé
                       

   Vous devez voir apparaître une fenêtre contenant une figure proche de celle-ci :

   

   • Les flèches correspondent aux traits plus épais de la liaison entre dans deux sommets.

   • Il est possible d'intégrer séparément toutes les options du tracé du graphique ainsi :

     # ensemble des options
     options = {
         'node_size' : 800,   # taille des sommets
         'node_color' : 'blue', # couleur de fond des sommets
         'edge_color' : 'red', # couleur des arcs
         'with_labels' : 'True',  # avec le nom des sommets 
         }                                    
     nx.draw(graphe, **options)
     plt.show()   # pour visualiser le graphique créé
                         

     Cela permet entre autre de définir une fois pour toutes les caractéristiques des tracés pour les utiliser pour chacun des graphes : cohérence dans la présentation générale.

La bibliothèque networkx contient aussi différentes méthodes portant sur les graphes, sommets et arcs :

Une documentation complète est disponible à cette adresse.

Utiliser les méthodes et fonctions de la bibliothqèe networkx pour :

1. obtenir le degré du sommet 'A' du graphe de l'exercice précédent.

   Code de déblocage de la correction :

2. obtenir le nombre de sommets de ce graphe.

   Code de déblocage de la correction :

3. obtenir le nombre d'arcs de ce graphe.

   Code de déblocage de la correction :

4. obtenir la liste des sommets voisins au sommet 'D' de ce graphe.

   Code de déblocage de la correction :

5. Tester aussi la méthode successors avec :

   graphe.successors('E')
           

6. Tester aussi la méthode predecessors avec :

   graphe.predecessors('E')
           

Le graphe suivant représente le plan d’une ville. Les arcs du graphe représentent ses avenues commerçantes, en prenant en compte le sens de circulation, et les sommets du graphe les carrefours de ces avenues.

1. Écrire la matrice $M$ associée à ce graphe. (On rangera les sommets dans l’ordre alphabétique).

2. Cette matrice est-elle symétrique (par rapport à la diagonale descendante) ? Pourquoi ceci était-il prévisible ?

D'un graphe vers matrice en langage Python.

On reprend l'exercice précédent :

Le graphe suivant représente le plan d’une ville. Les arcs du graphe représentent ses avenues commerçantes, en prenant en compte le sens de circulation, et les sommets du graphe les carrefours de ces avenues.

1. En vous aidant du travail déjà effectué lors de l' exercice 10, implémenter en Python le graphe orienté ci-dessus.

2. Voici un programme à rajouter à la suite du programme précédent ; l'objectif est que la matrice M corresponde à la fin à la matrice d'adjacence du graphe :

   liste = ['A','B','C','D','E','F']
   n = len(liste)
   M = [[0]*n for i in range(n)]
   for i in range(n):
       for j in range(n):
           ...................... 
               M[i][j] = 1
           

   1. Que permet le ligne M = [[0]*n for i in range(n)] ?

   2. compléter le programme en remplaçant la ligne ............... par un script qui permet d'avoir la matrice d'adjacence stockée dans M.

Le module networkx contient aussi une fonction permettant d'obtenir la matrice d'adjacence : adjacency_matrix.

Cependant, Le type de données de cette matrice obtenue avec M = adjacency_matrix(graphe) peut être vu comme une sorte de dictionnaire de dictionnaires, où la clé est un couple de nombres, nombres correspondant à des deux sommets définissant un arc et où la valeur correspond au nombre d'arcs reliant ces deux sommets.

Or, les nombres des couples des clés ne correspondent pas forcément aux mêmes sommets lors de deux exécutions identiques.

Ainsi, nous n'utiliserons pas cette méthode ensemble.

Le graphe ci-dessous représente, dans un aéroport donné, toutes les voies empruntées par les avions au roulage. Ces voies, sur lesquelles circulent les avions avant ou après atterrissage, sont appelées taxiways. Les sommets du graphe sont les intersections. Les arcs du graphe représentent les voies de circulation (les « taxiways ») en prenant en compte le sens de circulation pour les avions dans les différentes voies ainsi que le temps de parcours pour chacune en minute(s).

1. En rangeant les sommets par ordre alphabétique, déterminer la matrice associée à ce graphe orienté pondéré.

2. Implémenter cette matrice en Python en tant que tableau de tableaux.