LaDissertation.com - Dissertations, fiches de lectures, exemples du BAC
Recherche

Les Graphes

Fiche : Les Graphes. Recherche parmi 300 000+ dissertations

Par   •  4 Mars 2019  •  Fiche  •  678 Mots (3 Pages)  •  556 Vues

Page 1 sur 3

Graphes :

Définition : représentation d’un phénomène

Graphe fini simple : Orienté/Non orienté

  1. Graphes simplifiés orientés
  1. 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]

...

Télécharger au format  txt (2.6 Kb)   pdf (242.8 Kb)   docx (19.1 Kb)  
Voir 2 pages de plus »
Uniquement disponible sur LaDissertation.com