Scribd
Importer
60 vues2 pages

CC Théorie

Ce document est un contrôle continu pour l'année académique 2020-2021 à l'Institut Africain d'Informatique, portant sur la théorie des graphes. Il contient plusieurs exercices demandant des analyses sur des graphes, y compris la détermination des degrés, la vérification de propriétés comme le lemme des poignées de mains, et des questions sur des relations et des matrices d'adjacence. Les étudiants doivent également travailler sur des expressions algébriques et des représentations graphiques.

Transféré par

alexkuitche07
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
60 vues2 pages

CC Théorie

Ce document est un contrôle continu pour l'année académique 2020-2021 à l'Institut Africain d'Informatique, portant sur la théorie des graphes. Il contient plusieurs exercices demandant des analyses sur des graphes, y compris la détermination des degrés, la vérification de propriétés comme le lemme des poignées de mains, et des questions sur des relations et des matrices d'adjacence. Les étudiants doivent également travailler sur des expressions algébriques et des représentations graphiques.

Transféré par

alexkuitche07
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

Institut Africain D’informatique African Institute of computer Sciences

Représentation du Cameroun Cameroon office


CENTRE D’EXCELLENCE TECHNOLOGIQUE PAUL BIYA PAUL BIYA TECHNOLOGICAL CENTER OF EXCELLENCE
B.P. 13719 Yaoundé (Cameroun)
Tél.: 699 68 25 56 /675 88 57 08 Email : contact@[Link]
Academic year 2020-2021

CONTRÔLE CONTINU
EPREUVE DE THEORIE DES GRAPHES
DUREE : 2H00 NIVEAU II

Exercice 1 : /4pts
Soit les graphes G1 et G2 suivant :

1. Déterminer les degrés de chaque sommet des deux graphes.


2. Déterminer le degré de chaque graphe.
3. Pour chaque graphe, vérifier le lemme des poignées de mains.
4. Les graphes ci-dessus sont-ils Hamiltoniens ou Eulériens ? Justifier dans chaque cas et
nommer le cycle Hamiltonien ou Eulérien correspondant.
5. Y’a-t-il des points de coupure dans ces graphes ? si oui, les préciser.

Exercice 2: /6pts
Soit le graphe orienté simple défini par le tableau de suivants :
Sommets Précédants
1 /
2 1,3
3 1,4
4 1,3,2
1. Représenter le graphe G.
2. Ecrire la matrice d’adjacence M du graphe G.
3. Déterminer les degrés interne et externe de chaque sommet. Comment les retrouver à
partir de la matrice d’adjacence M du graphe G ?
4. Quel est le nombre de chemin de longueur 3 allant du sommet 1 au sommet 4 ?
5. Déterminer le nombre de circuits de longueur 4 de G.
6. Le graphe G est-il faiblement, unilatéralement ou fortement connexe ?
7. Etablir le graphe de fermeture transitive de G.

Exercice 3 : /7pts
Soit R la relation définie sur A= {1,2,3,4,5,6} ; R= {(1,2) ;(1,3) ;(2,4) ;(3,2) ;(3,6) ;(4,6) ;(5,2) ;(5,6)}.
1- Quelles sont ses domaines et étendues ?
2- Tracer son graphe orienté G.
Page 1 of 2
3- Donner dans un tableau la liste de tous les précédents de chaque sommet.
4- Déterminer ainsi les niveaux N(0), N(1), N(2), N(3), et N(4).
5- Ordonnancer par niveau le graphe G, puis en donner une représentation sagittale.
6- Ecrire l’expression de la matrice de fermeture du graphe orienté G.
7- Déterminer 𝑅 −1, tracer son graphe.

Exercice 4 : /3pts

Soit l’expression algébrique :


 3x  5 y 
2

2
b  2a  d 
2 3

1. Tracer l’arborescence ordonnée correspondant, en utilisant (  ) pour l’exponentiation, (  ) pour


la multiplication et (/) pour la division.
2. Ecrire l’expression en notation polonaise préfixée.

Powered by: KUITCHE Alex ([Link])

Page 2 of 2

Vous aimerez peut-être aussi