Voici ci-dessous un graphe non-orienté qui repré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.

   Importer aussi le module matplotlib.pyplot, sous l'alias plt ici, afin de pouvoir tracer le graphe implémenté.

   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 sous forme d'un dictionnaire 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 : il y a alors une 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 bibliothèque 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.

   le type de l'objet renvoyé peut dépendre de l'IDLE utilisé : sous Edupython, l'objet renvoyé est de type list tandis que sous jupyter c'est un itérateur dict_keyiterator. Ne pas hésiter dans ce seconde cas à transtyper sous forme de liste l'itérateur obtenu avec la méthode successors afin de lire plus facilement l'ensemble renvoyé.

   Code de déblocage de la correction :

5. Tester aussi la méthode successors avec :

   graphe.successors('E')
           

   Ne pas hésiter à transtyper si besoin sous forme de liste l'itérateur obtenu avec la méthode successors afin de lire plus facilement l'ensemble renvoyé.

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 sans networkx.

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.

Le graphe est cette fois-ci implémenté par le dictionnaire suivant :

reseau = {
    	  "A": ["B"],
    	  "B": ["D"],
    	  "C": ["F"],
    	  "D": ["A", "C"],
    	  "E": ["A"],
    	  "F": ["E"]
	     } 

Compléter le script suivant afin que la fonction dicoAdj_vers_matrice prenne en paramètre un dictionnaire graphe de type dictionnaire associant à chaque sommet du graphe sa liste d'adjacence et renvoie la matrice associé à ce graphe.

def dicoAdj_vers_matrice(graphe):
	# ensemble des sommets du graphe
	liste_sommets = list(...)

	# Création d'une matrice carrée nulle
	matrice = []
	for li in range(len(liste_sommets)):
		ligne = []
		for col in range(len(liste_sommets)):
			...
		...

	# Remplacement des 0 par un 1 dans le cas d'un arc
	for li in range(len(liste_sommets)):
		for col in range(len(liste_sommets)):
			if ...:
				matrice[...][...] = 1

	return matrice 

Pour tester le script écrit, dicoAdj_vers_matrice(reseau) doit renvoyer [[0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]].

Dans cet exercice, vous allez construire un graphe à partir d'une matrice d'adjacence sans utiliser networkx.

Une matrice, étant une sorte de tableau à deux dimensions, peut être implémentée en langage Python sous la forme d'une liste de listes.

On considère la matrice d'adjacence suivante :

Cette matrice représente les liens d'amitié dans un réseau social de 8 personnes : Ada, Bryan, Carla, Duc, Elie, Felix, Grace, Hector. (l'ordre alphabétique permet de retrouver l'ordre d'apparition dans la matrice d'adjacence .)

Explications :
Le fait que M[0][1]=1 signifie Qu'Ada considère Bryan comme un ami ; le fait que M[2][0]=0 signifie que Carla ne considère pas Ada comme un amie .

Compléter le code suivant de sorte que creer_dicoAdj(M, liste_sommets) renvoie le dictionnaire suivant :

{'Ada': ['Bryan', 'Carla'], 
 'Bryan': ['Duc', 'Elie'], 
 'Carla': ['Bryan', 'Duc'], 
 'Duc': ['Ada', 'Elie', 'Felix'], 
 'Elie': ['Felix', 'Grace'], 
 'Felix': ['Grace', 'Hector'], 
 'Grace': ['Bryan', 'Elie', 'Felix'], 
 'Hector': ['Ada', 'Carla', 'Grace']}

M = [[0, 1, 1, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 1, 0, 0, 0],
     [0, 1, 0, 1, 0, 0, 0, 0],
     [1, 0, 0, 0, 1, 1, 0, 0],
     [0, 0, 0, 0, 0, 1, 1, 0],
     [0, 0, 0, 0, 0, 0, 1, 1],
     [0, 1, 0, 0, 1, 1, 0, 0],
     [1, 0, 1, 0, 0, 0, 1, 0]]

liste_sommets = ["Ada", "Bryan", "Carla", "Duc", "Elie", "Felix", "Grace", "Hector"]

def creer_dicoAdj(matrice: list, sommets: list) -> dict:
    n = len(sommets)
    dico = {}
    for i in range(n):
        ... # À chaque sommet du graphe on associe une liste d\'adjacence vide
        for j in range(n):
            if ...:
                ... 
    return dico

print(creer_dicoAdj(M, liste_sommets))

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 tableau.