Introduction aux graphes¶

Nous aurons besoin d'importer la bibliothèque graph, permettant la création et l'affichage d'un graphe

In [2]:
from graph import *

0. Collection non ordonnée d'éléments¶

0 .1 L'ensemble (set)¶

Le set est un ensemble, au sens mathématique du terme (voir semestre 1). C'est donc une collection non ordonnée, d'élements uniques.

Attention : les sets étant non ordonnés, on ne peut pas accéder aux éléments qu'ils contiennent grâce à un indice.

In [3]:
# les éléments d'un set sont mis en accolade. Ils peuvent être de types différents !
ensemble = {"Faim", "Soif", 2, 4, True}
print(ensemble)
print(len(ensemble))

{True, 2, 4, 'Soif', 'Faim'}
5
In [4]:
# pas de doublons dans un set !
ensemble = {"Faim", "Soif", 2, 4, True, "Faim"}
print(ensemble)
print(len(ensemble))

{True, 2, 4, 'Soif', 'Faim'}
5

0.2 Opérations sur les ensembles¶

In [5]:
# créations d'un set vide
ensemble = set()

# ajouts d'élements
ensemble.add(2)
ensemble.add(4)
print(ensemble)

# suppression d'un élement
ensemble.remove(4)
print(ensemble)

# test d'appartenance
print(2 in ensemble)
print(4 in ensemble)

{2, 4}
{2}
True
False
In [6]:
ens1 = {2,5,6}
ens2 = {3,5,7}
# union d'ensembles
print(ens1 | ens2)

{2, 3, 5, 6, 7}
In [7]:
# intersection d'ensembles
print( ens1 & ens2)

{5}
In [8]:
# on peut parcourir un set avec une boucle for
for i in ens2 :
    print(i)

3
5
7

0.3 Le dictionnaire¶

Le dictionnaire est un tableau associatif, où chaque élément est la donnée d'une clef associée à une valeur.

La saisie se fait sous la forme clef : valeur, le tout entre accolades.

In [9]:
dico = {"Nom": "Coutant", "Prenom":"Etienne", "Taille": 192}
print(dico)
print(len(dico))

{'Nom': 'Coutant', 'Prenom': 'Etienne', 'Taille': 192}
3
In [10]:
# les clefs sont :
print(dico.keys())

dict_keys(['Nom', 'Prenom', 'Taille'])
In [11]:
# les valeurs associées sont :
print(dico.values())

dict_values(['Coutant', 'Etienne', 192])

Comme pour un ensemble, un dictionnaire n'est pas ordonné. On ne peut donc pas accéder à ces élements via un indice !

C'est là qu'interviennent les clefs : on peut accéder à la valeur associée à une clef grâce à la commande dictionnaire[clef].

In [12]:
print(dico["Nom"])

Coutant
In [13]:
dico = {"Noms": ["Coutant", "Blanchard"], 
        "Prenoms":["Etienne","Frederic","Robin"], 
        "Tailles": [192, 170,103]}
print(len(dico))
print(dico["Noms"])
print(dico["Noms"][0])

3
['Coutant', 'Blanchard']
Coutant
In [14]:
# cette commande permet aussi de modifier une valeur du dictionnaire
dico["Prenoms"] = ["Tinou", "Fredo", "Binouz"]
print(dico)

{'Noms': ['Coutant', 'Blanchard'], 'Prenoms': ['Tinou', 'Fredo', 'Binouz'], 'Tailles': [192, 170, 103]}
In [15]:
# on peut même modifier une partie de la valeur
dico["Prenoms"][1] = "Roger"
print(dico)

{'Noms': ['Coutant', 'Blanchard'], 'Prenoms': ['Tinou', 'Roger', 'Binouz'], 'Tailles': [192, 170, 103]}
In [16]:
# si une clef n'existe pas, la commande permet aussi d'en créer une :
dico["Poids"] = [90,50,14]
print(dico)

{'Noms': ['Coutant', 'Blanchard'], 'Prenoms': ['Tinou', 'Roger', 'Binouz'], 'Tailles': [192, 170, 103], 'Poids': [90, 50, 14]}

0.4 Parcours d'un dictionnaire¶

In [17]:
# par défaut, une boucle for parcourt les clefs d'un dictionnaire

for i in dico :
    print(i)

Noms
Prenoms
Tailles
Poids
In [18]:
# on peut aussi obtenir les valeurs à partir du parcours des clefs.
for i in dico:
    print(dico[i])

['Coutant', 'Blanchard']
['Tinou', 'Roger', 'Binouz']
[192, 170, 103]
[90, 50, 14]

0.5 Exercices¶

  • Grâce à une boucle, dédoubler la dernière lettre de chaque prénom du dictionnaire précédent.

Exemple :

In [20]:
print(dico)

{'Noms': ['Coutant', 'Blanchard'], 'Prenoms': ['Tinouu', 'Rogerr', 'Binouzz'], 'Tailles': [192, 170, 103], 'Poids': [90, 50, 14]}
  • Grâce à une boucle, dédoubler le dernier élément de chaque valeur dans le dictionnaire précédent.

Exemple :

In [22]:
print(dico)

{'Noms': ['Coutant', 'Blanchard', 'Blanchard'], 'Prenoms': ['Tinouu', 'Rogerr', 'Binouzz', 'Binouzz'], 'Tailles': [192, 170, 103, 103], 'Poids': [90, 50, 14, 14]}
  • Grâce à une boucle, transformer chaque valeur en élement set.
In [24]:
print(dico)

{'Noms': {'Coutant', 'Blanchard'}, 'Prenoms': {'Tinouu', 'Binouzz', 'Rogerr'}, 'Tailles': {192, 170, 103}, 'Poids': {90, 50, 14}}
  • Grâce à une boucle, ajouter vos Nom, Prénom, Taille et Poids au dictionnaire précédent.

Exemple : Killian MACHIN, mesurant 185cm pour 83kg se rajoute au dictionnaire.

In [26]:
print(dico)

{'Noms': {'Coutant', 'Blanchard', 'Machin'}, 'Prenoms': {'Tinouu', 'Binouzz', 'Killian', 'Rogerr'}, 'Tailles': {192, 185, 170, 103}, 'Poids': {90, 83, 50, 14}}

1 Le graphe orienté¶

1.1 Premières manipulations¶

Un graphe orienté est un objet, instance de la classe Graph. Cette classe possède plusieurs attributs, mais nous allons nous concentrer sur l'un d'entre eux : l'attribut successors.

L'attribut successors est un dictionnaire, où les clefs sont les sommets du graphe, et les valeurs associées sont les successeurs de chaque sommet.

Exemple :

In [27]:
g1 = Graph()
g1.successors = {0:{1,0}, 
                 1:{2},
                 2:{2,0,1},
                 3:set()}

# on remarque que les successeurs sont donnés sous forme d'ensemble "set"
# attention au set vide, qui se note set() et pas {}

La méthode sizepermet de connaître le nombre de sommets, tandis que la méthode displaypermet un affichage du graphe.

In [28]:
# nombre de sommets du graphe précédent
g1.size()
Out[28]:
4
In [29]:
# affichage du graphe précédent
In [30]:
g1.display()
Out[30]:
G G 0 0 0->0 1 1 0->1 2 2 1->2 2->0 2->1 2->2 3 3

La méthode copy permet de créer une copie indépendante d'un graphe.

In [31]:
g1bis = g1.copy()
g1bis.successors[3] = {1}
print(g1.successors)
print(g1bis.successors)

{0: {0, 1}, 1: {2}, 2: {0, 1, 2}, 3: set()}
{0: {0, 1}, 1: {2}, 2: {0, 1, 2}, 3: {1}}

1.2 Création et modification d'un graphe¶

1.2.1 Construction d'un graphe orienté¶

  • Construire le graphe orienté g2 correspondant à la représentation ci-dessous.
In [33]:
g2.display(title="G2")
Out[33]:
G2 G2 0 0 0->0 1 1 0->1 2 2 0->2 3 3 1->3 4 4 1->4 2->4 3->2 3->3 3->4

Pour ajouter un arc (x,y), il suffit de rajouter y dans les successeurs de x.

Exemple :

In [34]:
#On veut rajouter l'arc (2,1) au graphe précédent.
dico = g2.successors
dico[2].add(1)
g2.display(title="G2")
Out[34]:
G2 G2 0 0 0->0 1 1 0->1 2 2 0->2 3 3 1->3 4 4 1->4 2->1 2->4 3->2 3->3 3->4
In [35]:
# on supprime l'arc que l'on vient de rajouter
dico = g2.successors
dico[2].remove(1)
g2.display(title="G2")
Out[35]:
G2 G2 0 0 0->0 1 1 0->1 2 2 0->2 3 3 1->3 4 4 1->4 2->4 3->2 3->3 3->4

1.2.2 Modification de graphes¶

  • Construire une fonction mat_graphe_sans_boucle(g) qui supprime toutes les boucles d'un graphe gdonné.

Exemple :

In [37]:
mat_graphe_sans_boucle(g2)
g2.display(title="G2")
Out[37]:
G2 G2 0 0 1 1 0->1 2 2 0->2 3 3 1->3 4 4 1->4 2->4 3->2 3->4
  • Construire une fonction mat_graphe_ajoute_arcs(g,L) qui modifie le graphe orienté g en ajoutant les arcs supplémentaires donnés par la liste de couples L.

Exemple : On veut ajouter les arcs (1,2), (2,2) et (4,3) au graphe précédent.

In [39]:
mat_graphe_ajoute_arcs(g2,[(1,2),(2,2),(4,3)])
g2.display(title="G2")
Out[39]:
G2 G2 0 0 1 1 0->1 2 2 0->2 1->2 3 3 1->3 4 4 1->4 2->2 2->4 3->2 3->4 4->3

1.3 Prédecesseurs, successeurs¶

  • Construire une fonction successeurs(g,s) qui retourne l'ensemble des successeurs du sommet s dans le graphe orienté g.

  • Construire une fonction predecesseurs(g,s) sur le même modèle que la fonction précédente.

  • Construire les fonctions degre_sortant(g,s) et degre_entrant(g,s) qui retournent le degré entrant/sortant du sommet s.

Exemple :
Reprenons le graphe g1.

In [40]:
g1.display()
Out[40]:
G G 0 0 0->0 1 1 0->1 2 2 1->2 2->0 2->1 2->2 3 3
In [42]:
print(successeurs(g1,0), successeurs(g1,1))

{0, 1} {2}
In [44]:
print(predecesseurs(g1,0), predecesseurs(g1,1))

{0, 2} {0, 2}
In [46]:
print(degre_sortant(g1,1), degre_entrant(g1,1))

1 2

2. Le graphe non orienté¶

2.1 Construction¶

Un graphe non orienté sera construit via l'appel à la classe Graph, avec l'attribut directedà False (cet attribut est mis à Truepar défaut).

Exemple :
Construisons le graphe g3.

In [47]:
g3 = Graph(directed=False)
g3.successors = {0:{1,0},
                 1:{0,2},
                 2:{1}}
g3.display(title="G3")
Out[47]:
G3 G3 0 0 0--0 1 1 0--1 2 2 1--2

Il faudra bien faire attention que si $s_1$ est un voisin de $s_2$, $s_2$ doit être un voisin de $s_1$.

Exemple :
Dans le graphe g3Faux ci-dessous, la représentation du graphe s'effectue alors que le graphe n'est pas cohérent (0 n'est pas dans la liste des voisins de 1 alors que 1 est dans la liste des voisins de 0).

In [48]:
g3Faux = Graph(directed=False)
g3Faux.successors = {0:{1,0},
                     1:{2},
                     2:{1}}
g3Faux.display(title="G3Faux")
Out[48]:
G3Faux G3Faux 0 0 0--0 1 1 0--1 2 2 1--2
  • Construire une fonction coherent(g), retournant True si le graphe non orienté g est cohérent, Falsesinon.

Exemple :

In [50]:
print(coherent(g3), coherent(g3Faux), sep=",")

True,False

2.2 Voisin¶

  • Construire une fonction voisins(g,s) qui retourne l'ensemble des voisins du sommet s dans le graphe non orienté g.

  • Construire une fonction degre(g,s) qui retourne le degré du sommet s.

On fera attention aux sommets possèdant une boucle !

Exemple :

In [53]:
voisins(g3,0)
Out[53]:
{0, 1}
In [54]:
# attention, 0 possède deux voisins, mais est de degré 3
degre(g3,0)
Out[54]:
3

3. Arbres enracinés¶

3.1 Rappel¶

Un arbre est un graphe :

  • non orienté
  • connexe (il est en un "seul morceau")
  • sans cycle (et donc sans boucles)

On construit un arbre enraciné en choisissant l'un des sommets comme racine. Il en découle une orientation naturelle de la racine vers tous les autres sommets.
A noter que dans un arbre enraciné, les sommets n'ont qu'un seul prédécesseur (sauf la racine qui en a zéro).

  • Construire l'arbre enraciné a1 ci-dessous :
In [56]:
a1.display(title="A1")
Out[56]:
A1 A1 0 0 1 1 1->0 2 2 4 4 2->4 6 6 2->6 3 3 3->1 3->2 5 5 3->5 7 7 6->7
  • Construire une fonction racine(a)donnant la racine d'un arbre enraciné a.

Exemple :

In [58]:
racine(a1)
Out[58]:
3

3.2 Parcours d'un arbre¶


definition de largeur(Arbre)

Visite = liste initialisée à vide
Racine = racine de l'arbre
File = liste des sommets à traiter, initialisée à Racine

tant que File non vide
  sortir le premier sommet s de File
  mettre s dans Visite
  mettre tous les successeurs de s à la fin de la File
fin tant que

retourner Visite


definition de profondeur(Arbre)

Visite = liste initialisée à vide
Racine = racine de l'arbre
Pile = liste des sommets à traiter, initialisée à Racine

tant que Pile non vide
  sortir le premier sommet s de Pile
  mettre s dans Visite
  mettre tous les successeurs de s au début de Pile
fin tant que

retourner Visite
  • Construire une fonction largeur(a) donnant le parcours en largeur d'un arbre enraciné a.
  • Même question avec une fonction profondeur(a).

Exemple :

In [60]:
largeur(a1)
Out[60]:
[3, 1, 2, 5, 0, 4, 6, 7]
In [61]:
profondeur(a1)
Out[61]:
[3, 1, 0, 2, 4, 6, 7, 5]

3.3 Parcours d'un graphe orienté connexe 🌶️¶

On peut adapter les parcours précédents à des graphes connexes n'étant pas des arbres, mais il faudra faire deux modifications.

  • comme il n'y a plus de racine, le parcours pourra débuter d'un sommet s donné en paramètres.
  • si il y a un cycle, un même sommet pourrait être visité plusieurs fois. Afin d'éviter cela, on instaurera un système de marquage : un sommet sera ajouté à la File/Pile que s'il n'est par encore marqué, et on le marquera une fois ajouté.
  • Construire une fonction largeur_graphe(g,s) donnant le parcours en largeur d'un graphe orienté connexe g donné. Le paramètre s sera le premier sommet à visiter.

Exemple :

In [63]:
g4 = Graph()
g4.successors = {0:{0,1,2}, 1:{3,4}, 2:{4}, 3:{2,3,4}, 4:set()}
g4.display(title="G4")
Out[63]:
G4 G4 0 0 0->0 1 1 0->1 2 2 0->2 3 3 1->3 4 4 1->4 2->4 3->2 3->3 3->4
In [64]:
largeur_graphe(g4,0)
Out[64]:
[0, 1, 2, 3, 4]
  • Construire une fonction profondeur_graphe(g,s) donnant le parcours en profondeur d'un graphe orienté connexe g donné. Le paramètre s sera le premier sommet à visiter.

Exemple :

In [66]:
profondeur_graphe(g4,0)
Out[66]:
[0, 1, 3, 4, 2]

Et si on jettait un oeil à la SAE¶

Vous avez d'ors et déja acquis les compétences pour faire le début de la SAE sur les labyrinthes.
Si vous êtes curieux et/ou impatient, elle se trouve ici : http://fredbl.gitlab.io/a-maze-in-project/index.html.

4 Bonus 🌶️🌶️¶

On veut créer une fonction permettant de transformer un arbre (donc non orienté) en arbre enraciné (donc orienté), une fois un sommet choisi comme racine.

  • En vous inspirant des exercices précédents (utilisation de piles, système de marquage), créer une fonction enracine(g,s) qui choisit pour racine le sommet s, et qui donne une orientation naturelle à g, de la racine vers tous les autres sommets.

Exemple :

In [68]:
g5 = Graph(directed=False)
g5.successors = {0:{1,2,5},1:{0,3},2:{0,4},3:{1},4:{2},5:{0}}
In [69]:
g5.display(title="G5")
Out[69]:
G5 G5 0 0 1 1 0--1 2 2 0--2 5 5 0--5 3 3 1--3 4 4 2--4
In [70]:
enracine(g5,0).display()
Out[70]:
G G 0 0 1 1 0->1 2 2 0->2 5 5 0->5 3 3 1->3 4 4 2->4
In [71]:
enracine(g5,1).display()
Out[71]:
G G 0 0 2 2 0->2 5 5 0->5 1 1 1->0 3 3 1->3 4 4 2->4