© Copyright Franck CHEVRIER 2019-2023 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
1.1. Suivre la vidéo suivante, qui introduit la notion de graphe et le vocabulaire associé.
$\quad\;$En complément, si nécessaire, vous trouverez également un lexique dans les annexes de l'activité.
bla
1.2. On considère les 10 graphes ci-dessous.
$\quad\;\;$Compléter le tableau avec les valeurs qui conviennent.
$\quad\;\;$Aide : Le graphe $\text{G}_1$ est celui qui est traité en exemple dans la vidéo précédente.
1.3.a. Quel lien peut-on conjecturer entre la somme des degrés des sommets et le nombre d'arêtes du graphe ?
$\quad\;$b. Justifier que cette conjecture est correcte.
$\quad\;$c. Un graphe peut-il avoir un nombre impair de sommets de degrés impairs ?
1.4. Une application :
À une réception, 42 personnes se retrouvent.
Chaque convive serre la main de chacun des autres convives.
Combien de poignées de main sont échangées en tout ?
2.1. Suivre la vidéo suivante, qui introduit les notions de chaînes et de cycles eulériens.
2.2. On reprend les 10 graphes étudiés dans la partie 1, rappelés ci-dessous.
$\quad\;\;$Compléter le tableau avec les valeurs qui conviennent.
2.3. Quelle règle peut-on conjecturer pour déterminer de l'existence ou non d'une chaîne ou d'un cycle eulérien ?
$\quad\;\;$Une fois votre conjecture faite, cliquez sur la zone ci-dessous pour obtenir l'énoncé du théorème d'Euler.
Théorème d'Euler
- Un graphe connexe non orienté admet une chaîne eulérienne si et seulement si le nombre de sommets de degrés impairs de ce graphe vaut 0 ou 2.
Dans le cas où il y a deux sommets de degrés impairs, ces sommets sont les extrémités de la chaîne eulérienne.- Un graphe connexe non orienté admet un cycle eulérien si et seulement si tous ses sommets sont de degrés pairs.
2.4. Automatisation de la recherche de chaines et cycles eulériens.
a. La structure Python G1 ci-dessous permet de modéliser le graphe $\text{G}_1$ vu précédemment. Expliquer brièvement comment sont codées les informations du graphe dans cette structure.
Avant de continuer, exécuter cette cellule pour mettre ce graphe en mémoire.
# exécuter cette cellule
G1 = { 'A':['C','D','E'],
'B':['D','E'],
'C':['A','D'],
'D':['A','B','C','E'],
'E':['A','B','D']
}
b. On fournit ici des fonctions Python est_complet, est_connexe, non_oriente et algo_euler permettant respectivement de déterminer si un graphe est complet, s'il est connexe, s'il est non orienté et s'il est eulérien (et si oui, on obtient une chaîne ou un cycle eulérien).
Exécuter ces cellules et vérifier qu'on retrouve les résultats obtenus précédemment pour $\text{G}_1$.
# exécuter cette cellule
from random import choice
from copy import deepcopy
def est_complet(G):
"""
fonction qui indique si le graphe G est complet
"""
for S0 in G:
for S in G:
# s'il existe deux sommets non reliés, le graphe n'est pas complet
if S!=S0 and S not in G[S0]: return False
return True
def est_connexe(G,S0=None,atteint=None,profondeur=0):
"""
fonction qui indique si le graphe G est connexe
"""
if not atteint: atteint=[]
#si on a atteint tous les sommets, le graphe est connexe
if len(atteint)==len(G): return True
#si on a effectué suffisamment profonde et qu'on n'a pas atteint tous les sommets, il n'est pas connexe
if profondeur>=len(G): return False
#on choisit un sommet de départ
if not S0:
S0 = choice([S for S in G])
atteint.append(S0)
profondeur+=1
#pour chaque sommet déjà atteint, on complète la liste avec les sommets que l'on peut atteindre
for S in atteint:
for adj in G[S]:
if adj not in atteint: atteint.append(adj)
return est_connexe(G,S0,atteint,profondeur+1)
def non_oriente(G):
for S0 in G:
for S in G[S0]:
#s'il existe une arête non réciproque, le graphe est orienté
if S0 not in G[S]: return False
return True
def algo_euler(G):
G=deepcopy(G)
#si le graphe est orienté, arrêt de l'algorithme
if not non_oriente(G):
print("Arrêt. Le graphe soumis est un graphe orienté.")
return None
#si le graphe n'est pas connexe, il n'est pas eulérien
if not est_connexe(G):
print("Le graphe n'est pas connexe, donc il n'y a ni chaîne ni cycle eulérien.")
return None
#calcul du nombre de sommets de degrés impairs
sommets_deg_impair=[S for S in G if len(G[S])%2==1]
nb_som_deg_imp=len(sommets_deg_impair)
#choix des sommets de départ et d'arrivée si G admet une chaine eulérienne et arrêt sinon
if nb_som_deg_imp== 0:
Debut=Fin=[S for S in G].pop(0)
elif nb_som_deg_imp== 2:
Debut=sommets_deg_impair.pop(0)
Fin=sommets_deg_impair.pop(0)
else:
print("Le graphe a "+str(nb_som_deg_imp)+" sommets de degrés impairs, donc il n'y a ni chaîne ni cycle eulérien.")
return None
#détermination du nombre de sommets de la chaine à construire
longueur_chaine_euler = sum([len(G[S]) for S in G])//2+1
#contruction d'une chaine quelconque reliant Debut à Fin
chaine=[Debut]
while chaine[-1]!=Fin:
suiv=choice(G[chaine[-1]])
G[chaine[-1]].remove(suiv)
G[suiv].remove(chaine[-1])
chaine.append(suiv)
#tant que la chaine construite n'emprunte pas toutes les arêtes
while len(chaine)<longueur_chaine_euler:
#choix d'un début de cycle à insérer à partir d'un sommet de la chaine
deb_cycl=choice([S for S in chaine if G[S]!=[]])
#construction du cycle
cycl=[deb_cycl]
while cycl[-1]!=deb_cycl or len(cycl)<2:
suiv=choice(G[cycl[-1]])
G[cycl[-1]].remove(suiv)
G[suiv].remove(cycl[-1])
cycl.append(suiv)
#insertion du cycle dans la chaîne
rang_insert=chaine.index(deb_cycl)
chaine = chaine[:rang_insert]+cycl+chaine[rang_insert+1:]
print("Le graphe admet un"+(" cycle eulérien" if nb_som_deg_imp== 0 else "e chaine eulérienne")+".\nExemple:")
return chaine
# exécuter cette cellule
est_complet(G1)
False
# exécuter cette cellule
est_connexe(G1)
True
# exécuter cette cellule
non_oriente(G1)
True
# exécuter cette cellule
algo_euler(G1)
Le graphe admet une chaine eulérienne. Exemple:
['A', 'E', 'B', 'D', 'C', 'A', 'D', 'E']
c. Effectuer les saisies nécessaires pour modéliser quelques autres graphes parmi ceux étudiés précédemment. Effectuer ensuite des saisies pour vérifier les résultats du tableau de la question 2.2.
Aide : On pourra commencer par effectuer un copier/coller de la structure G1 fournie précédemment.
# Utiliser ces cellules pour effectuer les saisies
# Saisies pour G8
G8 = { 'A':['B','E'],
'B':['A','C','D','F'],
'C':['B','E'],
'D':['B','E'],
'E':['A','C','D','F'],
'F':['B','E']
}
est_complet(G8)
False
est_connexe(G8)
True
non_oriente(G8)
True
algo_euler(G8)
Le graphe admet un cycle eulérien. Exemple:
['A', 'B', 'F', 'E', 'D', 'B', 'C', 'E', 'A']
2.5. Une application :
Dans son mémoire Solutio problematis ad geometriam situs pertinentis, publié en 1741, Leonhard Euler décrit un problème qui deviendra célèbre sous le nom de "problème des 7 ponts de Kœnigsberg", et considéré comme étant à l'origine de la théorie des graphes.
Voici ci-dessous un extrait de cet ouvrage et sa traduction :
a. Répondre à la question posée par Euler concernant la situation des 7 ponts de Kœnigsberg (fig. 1):
$\;\;\;$Est-il possible d'effectuer un trajet qui emprunte chaque pont une et une seule fois ?
b. De la même façon que dans la question 1.4, créer une structure Python E1 permettant de modéliser le graphe correspondant à la situation des 7 ponts de Kœnigsberg. Effectuer ensuite un appel à la fonction algo_euler pour vérifier la réponse précédente.
Aides :
# Créer ici la structure E1 correspondant à la situation des 7 ponts de Koenigsberg
E1 = {
'A':['B','B','C','C','D'],
'B':['A','A','D'],
'C':['A','A','D'],
'D':['A','B','C']
}
# Effectuer ici un appel à la fonction algo_euler
algo_euler(E1)
Le graphe a 4 sommets de degrés impairs, donc il n'y a ni chaîne ni cycle eulérien.
c. Dans son mémoire, Euler propose deux autres situations, réprésentées sur les figures ci-dessous (fig. 2 et fig. 3).
$\quad$Indiquer, pour chaque situation, s'il est possible d'effectuer un trajet qui emprunte chaque pont une et une seule fois.
d. Créer des structures Python E2 et E3 permettant de modéliser les graphes correspondant aux situations représentées ci-dessus (fig. 2 et fig. 3). Effectuer ensuite des appels à la fonction algo_euler pour vérifier vos réponses précédentes.
# Créer ici la structure E2
E2 = {
'A':['B','B','B','B','B','B'],
'B':['A','A','A','A','A','A']
}
# Effectuer ici un appel à la fonction algo_euler
algo_euler(E2)
Le graphe admet un cycle eulérien. Exemple:
['A', 'B', 'A', 'B', 'A', 'B', 'A']
# Créer ici la structure E3
E3 = {
'A':['B','C','C','D','E','E','F','F'],
'B':['A','E','F','F'],
'C':['A','A','D','F'],
'D':['A','C','E'],
'E':['A','A','B','D','F'],
'F':['A','A','B','B','C','E']
}
# Effectuer ici un appel à la fonction algo_euler
algo_euler(E3)
Le graphe admet une chaine eulérienne. Exemple:
['D', 'E', 'F', 'C', 'D', 'A', 'F', 'B', 'A', 'C', 'A', 'E', 'A', 'F', 'B', 'E']
3.1. Lexique
- Graphes et sommets
- Un graphe est composé :
- de sommets ;
- d'arêtes qui relient ces sommets.
- L'ordre d'un graphe est le nombre de sommets de ce graphe.
- Le degré d'un sommet est le nombre de fois qu'il apparaît comme extrémité d'une arête.
- Deux sommets sont dits adjacents s'ils sont reliés par une arête.
- Structure de graphes
- Un graphe est dit connexe si n'importe lesquels de ses sommets sont reliés par une chaîne.
- Un graphe est dit complet si deux quelqconques de ses sommets sont tous adjacents.
- Chaînes et cycles
- Une chaîne est une suite quelconque d'arêtes du graphe.
- La longueur d'une chaîne est le nombre d'arêtes qui la compose.
- Une chaîne est dite fermée si ses deux extrémités sont confondues.
- Un cycle est une chaîne fermée composée d'arêtes toutes distinctes.
- Problème d'Euler
- Une chaîne est dite eulérienne si elle parcourt toutes les arêtes du graphe une seule fois.
- Un cycle est dit eulérien s'il parcourt toutes les arêtes du graphe une seule fois.
- Un graphe est dit eulérien s'il admet un cycle eulérien.
3.2. Kœnigsberg aujourd'hui
La ville de Kœnigsberg (ou Königsberg) se nomme aujourd'hui Kaliningrad, et est située dans l'oblast russe de Kaliningrad.
# Exécuter cette cellule pour obtenir la figure dynamique
from IPython.display import HTML ; HTML("""<iframe src="https://www.google.com/maps/embed?pb=!1m14!1m12!1m3!1d4610.1784389459735!2d20.5085608355321!3d54.70805343977486!2m3!1f0!2f0!3f0!3m2!1i1024!2i768!4f13.1!5e0!3m2!1sfr!2sfr!4v1686260755573!5m2!1sfr!2sfr" width="800" height="600" style="border:0;" allowfullscreen="" loading="lazy" referrerpolicy="no-referrer-when-downgrade"></iframe>""")
© Copyright Franck CHEVRIER 2019-2023 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Dernière modification de l'activité : Juin 2023