Scribd
Importer
4 vues1 page

Exercices sur les graphes eulériens

Le document présente des exercices sur les graphes, incluant des vérifications sur la nature eulérienne d'un graphe, la construction de matrices d'adjacence et de distances, ainsi que des fonctions pour calculer le degré d'un sommet, le nombre d'arcs, et les voisins d'un sommet. Les exercices demandent également de déterminer des chaînes et cycles eulériens, ainsi que de calculer la longueur de trajets dans un graphe. Ces tâches visent à approfondir la compréhension des propriétés des graphes et des algorithmes associés.

Transféré par

Adam Elhassouni
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
4 vues1 page

Exercices sur les graphes eulériens

Le document présente des exercices sur les graphes, incluant des vérifications sur la nature eulérienne d'un graphe, la construction de matrices d'adjacence et de distances, ainsi que des fonctions pour calculer le degré d'un sommet, le nombre d'arcs, et les voisins d'un sommet. Les exercices demandent également de déterminer des chaînes et cycles eulériens, ainsi que de calculer la longueur de trajets dans un graphe. Ces tâches visent à approfondir la compréhension des propriétés des graphes et des algorithmes associés.

Transféré par

Adam Elhassouni
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Graphes : Exercices

Exercice 1:

Soit le graphe ci-contre:


1- Vérifier si ce graphe est eulérien ou admet une chaine eulérienne.
2- Construire la matrice d’adjacence de ce graphe.
3- Ecrire les fonctions suivantes :
a- degre(G,i) : qui retourne le degré d’un sommet ayant l’indice i
b- nombreArcs(G) qui retourne le nombre d’arcs.
c- cycleEulerien(G) : qui retourne True si le graphe admet un cycle eulérien, False sinon.
d- chaineEulerienne(G): qui retourne True si le graphe admet une chaine eulérienne, False
sinon
e- chaineEulerienne2(G) : qui retourne une liste ayant les indices des extrémités de la chaine

eulérienne si elle existe. None sinon

Exercice 2:

1- On considère le graphe G suivant, où le


nombre situé sur l’arête joignant deux
sommets est leur distance, supposée entière :

Construire la matrice (Mij)0<i,j<4, matrice de


distances du graphe G, définie par :

Pour tous les indices i, j, Mij représente la


distance entre les sommets i et j, ou encore la
longueur de l’arête reliant les sommets i et j.

On convient que, lorsque les sommets ne sont pas reliés, cette distance vaut −1. La
distance du sommet i à lui-même est, bien sûr, égale à 0.

2- écrire une suite d’instructions permettant de dresser à partir de la matrice M la liste


des voisins du sommet 4.

3- écrire une fonction voisins, d’argument un sommet i, renvoyant la liste des voisins
du sommet i.

4- écrire une fonction degre, d’argument un sommet i, renvoyant le nombre des


voisins du sommet i, c’est-à-dire le nombre d’arêtes issues de i.

5- écrire une fonction longueur, d’argument une liste L de sommets de G, renvoyant


la longueur du trajet décrit par cette liste L, c’est-à-dire la somme des longueurs des
arêtes empruntées. Si le trajet n’est pas possible, la fonction renverra −1.

Vous aimerez peut-être aussi