Scribd
Importer
77 vues2 pages

Cours 1

Un graphe est une structure de données utilisée pour modéliser des relations entre objets, appelés sommets, reliés par des arêtes. Des exemples d'application incluent les réseaux sociaux, les réseaux de transport et les réseaux informatiques. Les graphes peuvent être orientés ou non orientés et peuvent être représentés de manière textuelle, graphique ou par matrice d'adjacence.

Transféré par

amoula77
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd
77 vues2 pages

Cours 1

Un graphe est une structure de données utilisée pour modéliser des relations entre objets, appelés sommets, reliés par des arêtes. Des exemples d'application incluent les réseaux sociaux, les réseaux de transport et les réseaux informatiques. Les graphes peuvent être orientés ou non orientés et peuvent être représentés de manière textuelle, graphique ou par matrice d'adjacence.

Transféré par

amoula77
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd

Cours 1 : Notion de graphes

1. Définition :
Un graphe est une structure de données fondamentale utilisée pour modéliser
des relations entre les objets. Les objets sont appelés des sommets, les
relations entre objets sont appelées des arêtes ou des arcs.
Un graphe peut être orienté A->B ou non oriente A-B
2. Quelques exemples concrets sur l’utilisation des graphes :
a. Réseaux sociaux :
Les utilisateurs sont représentés par des sommets
Les relations d’amitié, de suivi et de connexion sont représentés par des arêtes
b. Réseaux de transport :
Les villes sont représentées par des sommets, les routes ou les voies ferrés sont
représentés par des arêtes.
c. Réseaux informatique :
Les ordinateurs, les routeurs, les serveurs sont représentés par des sommets
Les connexions réseaux sont représentées par des arêtes.
3. Représentation des graphes :

Representation textuelle
Exemple
Soit G un graphe orienté tel que G =(V,E) v= E=
Representation graphique
Representation par matrice d’adjacence
Vocabulaire de la theorie des graphes :
L’ordre d’un graphe
Le degre d’un sommet
Deux sommets sont adjacents lorsqu’ils sont reliés par une arête.
Une arête est une boucle si elle relie un sommet à lui-même

Vous aimerez peut-être aussi