Scribd
Importer
4 vues2 pages

Définition et exercices sur les digraphes

Le document présente un devoir sur la théorie des graphes pour des étudiants de TC 2 A & B, comprenant des questions théoriques et des exercices pratiques. Les exercices incluent la définition de termes, la représentation graphique de graphes, l'organisation d'examens, et l'application d'algorithmes comme celui de Dijkstra. Les étudiants doivent également démontrer leur compréhension des concepts de graphes hamiltoniens et eulériens.

Transféré par

gandawilfried404
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
4 vues2 pages

Définition et exercices sur les digraphes

Le document présente un devoir sur la théorie des graphes pour des étudiants de TC 2 A & B, comprenant des questions théoriques et des exercices pratiques. Les exercices incluent la définition de termes, la représentation graphique de graphes, l'organisation d'examens, et l'application d'algorithmes comme celui de Dijkstra. Les étudiants doivent également démontrer leur compréhension des concepts de graphes hamiltoniens et eulériens.

Transféré par

gandawilfried404
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

Charg·é de cours :: M.

Cyc e
Otrrée : 2 H'OO mtt ·
[Link] Travaux Informatiques Fi lière : TC 2 A & B

PARTJE.L 1::- '"


J7..,,0/l/G{,,lvJ
tr
J_~EORIE DES GRAPHES
SEMESTRE Il
0 ;1rc : 0310612016
: .Nll: . Documents
. .
non autorisés
i-"

•· Qüesffons .:de co·urs .: (3,5 pts)

. Définir lesterrr'fes· suivants .:

. Digraphe, cher,in, circuit, digraphe fortement connexe ; graphe de comparabilité

Exercice 1 : (6,5 pts)

Un lycée doit organiser les h·oraires des examens. On suppose qu'il y a 7 épreuves à planifi er,
~,;,yre'.:;pondant
. au:-: cours numérotés de 1 à 7 et. que les paires de cours suivantes ont des
:=!tudié1nts cnmmuns : i et 2, î et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et
i . 4 et 5, 4 et 6, 5 et 6, 5 el. 7. , et 9nfi:1 G et 7.

1. Faire· un graphe représentant la [Link]. . / · -. •


2. Comment organiser ses épreuves de façon qu'aucun étudiant n'ait /casser deux ·épreuves
· en même temps et cela syr une durée minimale?
3. Proposer. un calendrier' d·es examens.

Exercictr2 .:' (1 O pts)

c:q_nsidérons le graphe G décrit parla table des antécédents de chaque sommet:


'.'I - ·. ·- - ···- · --,---- ___
---.- 1
__
,. . __________
2.
__
. ---·-· - -- -
3·
1
·,

sommets ___ .11

__
. .

4_(p=10) 1.1_(p~15), 3(p=3), 4(p=-=3) 5(p=7)


·Anté.cé·denfs (puids) _......,

1. Représenter graphiquement le graphe G.


2. Donner la matrice d'adjacences M cle G.
3. Le graphe G est-il fortement connexe ? Justifier votre réponse.
4 .. . A 1.'aide
. [Link] l'algorithme
· . . tan t des sornm ats
de Dijkstra, trouver les chemins les plus coLirts par
1 et 2. epresenter les arborescences correspondantes. · \;,
des Travaux In forma ti que s Durée : 2 H 00 rnn
Filière : TC 2 A & 8

DÈVOIR SURVEILLE
THEORf.E DE-S GRAPHES
SEMESTRE Il

NB: Documents non autorisés . ÜlltC . 02/05/20/ 7

EXERC-l°CES ·

1. · Dess·iner U'h •[Link] d'ordre au moins 5 qui est :·


1.J Hantiltonïen et eulérien. (1,5 pts)

1:°2 Non hamiltonïen et eulérien, (1,Spts)

1:3 ~Jon hamiltonien el non eulérien. (1,5 pts)

.. . c - ·-, ~- !j i);-;t;; g,~n-eral oe I aigor/ nme oé.db6ôfüjgïf. . · · (J.,5 pts)


;_ 2 Jessiner l'arbre correspondant à la Sl:!te S . .1., ~,. 1, 1,. 1-..
= -1, :1, ' (2,5 pis) .

3. Soit G [Link] de sommets 1, 2; 3, 4, 5 et 6 d'arêt~s {1,2} ; {1,4} ; {1,5} ; {2,3}; (2,5};


. . . . .

{3,5};
.
{:3.
.
,6}.,;. {4,5} . e~ {5,6}
. de poicls respectifs?,~. ?, 5, 4, 2,. 1, 1 et 3.
3.1 .(0onner la -représentation graphique de G.
(2,5 pts)
3.2 Donnerî~:n.e prèsentation matricielle de G.
(2,5 pts)
· 3.3 Définir. Un arbre. (1 pt)
3.4 Domi·er fa)Jjoritlime de Kruskal. (2.,5 pts)
3.5 Trol!vér tin. _arbre ·de· poids total minimum.
(2 pts)

BONNE CHANCE

Vous aimerez peut-être aussi