Les Graphes
Fiche : Les Graphes. Recherche parmi 298 000+ dissertationsPar Texo • 4 Mars 2019 • Fiche • 678 Mots (3 Pages) • 473 Vues
Graphes :
Définition : représentation d’un phénomène
Graphe fini simple : Orienté/Non orienté
- Graphes simplifiés orientés
- Représentation sagittale
Soit un ensemble S = {A, B, C, D}
Ensemble G = {(A, A), (A, B), (A, C), (A, D), (B, D), (C, B) (D, C)}
Formés par des couples d’éléments de S, est orienté
A B[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6]
C D[pic 7]
Les couples de G sont représentés par des arcs orientés.
Le schéma ci-dessus est la représentation sagittale de G.
Définition 1 :
- Dans la représentation sagittale de G A, B, C D sont les sommets du graphe.
- Les couples de G sont orientés
- Une suite de sommets reliées par des arcs est un chemin
- La longueur du chemin représente le nombre d’arcs parcourus
- Un arc reliant un sommet à lui-même est une boucle
- Un chemin reliant un sommet à lui-même est un circuit
- Un chemin qui parcourt chaque sommet du graphe exactement une fois est un chemin hamiltonien
Exercice : correction
M^4=2M^3[pic 8]
2*3 2*3 2*3 2*3
2*2 2*2 2*2 2*2
2*2 2*2 2*2 2*2
2*1 2*1 2*1 2*1
[pic 9]
= 6 6 6 6
4 4 4 4
4 4 4 4 = M^4
2 2 2 2
M^4 = 2^n-3 *M3
Nombre de chemins de longueur n de D vers A
Matrice M^n, le coefficient de la i-ème ligne et j-ième colonne représente le nombre de chemins de longueur n du i-ème sommet vers le j-ième sommet.
[pic 10]
M11 M1j M1n[pic 11][pic 12]
[pic 13]
[pic 14][pic 15]
Min M^n=5i
Mnn
Mn1 Mnj
On cherche le coefficient de la 4e ligne et 1e colonne
[pic 16]
M= 2^n-3*3 2^n-3*3 2^n-3*3 2^n-3*3
M= 2^n-3*2 2^n-3*2 2^n-3*2 2^n-3*2
M= 2^n-3*2 2^n-3*2 2^n-3*2 2^n-3*2
M= 2^n-3*1 2^n-3*1 2^n-3*1 2^n-3*1
Pour n≥3 il y a 2^n-3 chemins de longueur n de D vers A
2^0=1 2^1=2 2^2=4 2^3=8 2^4=16 2^5=32 2^6=64 2^7=128
2^7=2^10-3
Chemins de longueur 10
Exercice : un réseaux de pages web est schématisé par le graphe G ci-dessous
[pic 17]
...