TEST de cours spé maths TES 2014
--------------------------------------------------------------------------------------------
Nom: ........................ classe: .......................
--------------------------------------------------------------------------------------------
Partie A
QUESTIONS:
Quel est l'ordre d'un graphe G? C'est le nombre de ses sommets.
Quelle information donne un 1 de rang ( i ; j )
dans la matrice adjacente M d'un graphe G ? Il y a une arête du i ième sommet au j ième sommet
Que doit-on considérer pour avoir des informations sur les chemins
de longueur 3 d'un graphe G de matrice adjacente M? La matrice M3
Dans la matrice adjacente M d'un graphe G que signifie le fait d'avoir
la j ième colonne qui ne comporte que des 0 ? Aucune arête n'arrive au j ième sommet.
Dans un graphe qu'est-ce qu'une boucle ? Une arête dont les extrémités sont
confondues.
Dans un graphe G non orienté qu'est-ce qu'une chaîne eulérienne ? Une chaîne qui
passe une et une seule fois par chaque arête.
Dans un graphe G non orienté qu'est-ce que le degré d'un sommet ?
C'est le nombre fois que ce sommet est une extrémité d'une
arête.
Dans un graphe G non orienté que peut-on dire de la somme des degrés des sommets ?
C'est le double du nombre d'arêtes.
Dans un graphe G non orienté combien compte une boucle en un sommet A pour le degré de A ? Pour 2
Qu'est-ce qu'un graphe non orienté connexe ? Deux sommets quelconques y sont
reliés au moins par une arête.
Qu'est-ce qu'un graphe non orienté complet ? Deux sommets quelconques y sont
adjacents.
Un graphe non orienté complet est-il toujours connexe ? OUI
Un graphe non orienté connexe est-il toujours complet ? NON
a.Quel est, dans un graphe non orienté (simple) connexe,
le critère qui permet de justifier l'existence d'une chaîne eulérienne ?
S'Il y a 0 ou 2 sommets de degrés impairs. ( Th. d'Euler )
b.Comment peut-on en connaître les extrémités ?
S'il y a deux sommets de degré impair seulement la chaîne
eulérienne les relie. S'il n'y a aucun sommet de degré impair
on a seulement l'existence d'un cycle eulérien.
14. Quel est, dans un graphe non orienté (simple) connexe,
le critère qui permet de justifier l'existence d'un cycle eulérien?
Un seul sommet de degré 0
15. Quels outils utilise-t-on pour dans un graphe orienté connaître
le chemin de longueur minimale ?
L'algorithme de Moore-Dijstra.
-----------------------------------------------------------------------
Partie B
Dans cette partie G est un graphe probabiliste d'ordre 2
de sommets A et B, de matrice de transition M.
n est un entier naturel.
QUESTIONS:
1. Combien y a-t-il d'arcs ? 4 arc
2. Que donne la somme d'une ligne de M ? 1
3. Quels sont les termes de l'état initial P0 ?
P0 = ( a0 b0 ) avec a0 + b0 = 1
a0 est la probabilité au début de A et b0 est celle de B.
4. Quel critère permet de justifier l'existence d'un état stable ?
Si la matrice de transition ( M d'ordre 2 ) ne comporte aucun 0
il y a un état stable P= ( a b ) tel que : P = P × M
5. Que peut-on dire des deux égalités données par ?
P = P × M
Elles sont identiques.
Pour obtenir P on considère l'une d'elles et a + b = 1
6. Comment obtient -on l'état Pn ?
En considérant : Pn = P0 × Mn
----------------------------------------------------------------------------