Scribd
Importer
46 vues4 pages

Exercices sur les graphes et algorithmes

Le document présente une série d'exercices sur les graphes, incluant des tâches telles que dessiner des graphes hamiltoniens et eulériens, décrire des graphes par des matrices et des listes d'adjacences, et déterminer des chemins et circuits spécifiques. Il aborde également des algorithmes comme Bellman-Ford, PRIM et Kruskal, ainsi que des concepts liés aux composantes fortement connexes et aux arbres. Enfin, il pose des questions sur la possibilité de tracer des figures sans lever le crayon et sur l'unicité des chemins dans un arbre.

Transféré par

lus.isad.fsk
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 PDF, TXT ou lisez en ligne sur Scribd

Thèmes abordés

  • graphe hamiltonien,
  • recherche de chemins,
  • représentation matricielle,
  • listes d'adjacences,
  • graphe orienté,
  • graphes et réseaux,
  • graphe non orienté,
  • applications des graphes,
  • circuit élémentaire,
  • optimisation de chemins
46 vues4 pages

Exercices sur les graphes et algorithmes

Le document présente une série d'exercices sur les graphes, incluant des tâches telles que dessiner des graphes hamiltoniens et eulériens, décrire des graphes par des matrices et des listes d'adjacences, et déterminer des chemins et circuits spécifiques. Il aborde également des algorithmes comme Bellman-Ford, PRIM et Kruskal, ainsi que des concepts liés aux composantes fortement connexes et aux arbres. Enfin, il pose des questions sur la possibilité de tracer des figures sans lever le crayon et sur l'unicité des chemins dans un arbre.

Transféré par

lus.isad.fsk
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 PDF, TXT ou lisez en ligne sur Scribd

Thèmes abordés

  • graphe hamiltonien,
  • recherche de chemins,
  • représentation matricielle,
  • listes d'adjacences,
  • graphe orienté,
  • graphes et réseaux,
  • graphe non orienté,
  • applications des graphes,
  • circuit élémentaire,
  • optimisation de chemins

Exercice 1

Dessinez un graphe d’ordre au moins 5 qui est. . .


1) hamiltonien et eulérien
2) hamiltonien et non eulérien
3) non hamiltonien et eulérien
4) non hamiltonien et non eulérien
Exercice 2
Décrivez le graphe G ci-dessous par une matrice d’adjacences et des listes d’adjacences.

Exercice 3

1) En considérant le graphe comme non orienté, donner une chaîne de A à F passant par E sans
utiliser deux fois la même arête.
2) En considérant le graphe comme non orienté, donner une chaîne élémentaire de A à F
3) En considérant le graphe comme orienté idem question (1) et (2) avec les chemins et
4) arcs

Exercice 4
1) Do
nne
r un

circuit non élémentaire partant de A et passant par G


2) Donner un circuit élémentaire à partir de A
3) En considérant le graphe comme non orienté idem question (1) et (2) pour un cycle et un
cycle élémentaire

Exercice 5
Soit le graphe :

1) D
o
n
n
e
r

les composantes fortement connexes du graphe


2) Donner le graphe réduit (l’arc retenu est l’arc de poids le plus faible).

Exercice 6
Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux fois sur le
même trait !…) ? Pourquoi ?

Exercice 7
Pour chaque graphe ci-dessous, d´eterminer le chemin le plus court pour aller du sommet 1 au
sommet 6 :

Exercice 8
Considérons le graphe non orienté dont la représentation suivante :

Appliquer l’algorithme de Bellman-Ford à ce graphe en partant du sommet z.

Exercice 9
Dans un arbre, monter que pour chaque paire de sommets, il y a un chemin unique.
Exercice 10
Appliquer l’algorithme de PRIM et Kruskal au graphe G suivant en commençant par le sommet x.

Exercice 11

Pour le graphe pondéré ci-dessus on cherche à trouver l’arbre couvrant minimum en appliquant
un algorithme de cours.

Vous aimerez peut-être aussi