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

Analyse des besoins pour le développement logiciel

Guide pratique : Analyse des besoins pour le développement logiciel. Recherche parmi 297 000+ dissertations

Par   •  18 Mars 2020  •  Guide pratique  •  7 938 Mots (32 Pages)  •  419 Vues

Page 1 sur 32

GRAPHES 1

  1. Généralités sur les graphes
  1. Notion de graphe[pic 1][pic 2]

De nombreuses autres situations peuvent être représentées à l’aide de schémas de ce genre appelés graphes.

  1. Graphe non orienté                                                                                                                       Exemples de graphes non orientés :[pic 3]

[pic 4]

Définitions et exemples :                                                                                                                                                       - Un graphe non orienté est un ensemble de sommets pouvant être reliés par des arêtes, une boucle étant une arête reliée deux fois au même sommet. Les sommets sont généralement représentés par des points et les arêtes par des segments ou des arcs de cercle.                                                                                                                                                                        Par exemple, le graphe 1 a ……..  sommets et  ………  arêtes, le graphe 2 a lui

………  sommets et  ………  arêtes.                                                                                                                                                        

– L’ordre d’un graphe est le nombre total de ses sommets. Par exemple, le graphe 1 est

d’ordre ……… et le graphe 2  est d’ordre ……..    .                                                                                                

– Le degré d’un sommet est le nombre d’arêtes arrivant à ce sommet, une boucle étant comptée double.  

Complétons les tableaux suivants correspondants respectivement aux graphes 1 et 2.

Sommet

A

B

C

D

E

F

Total

Degré

Sommet

A

B

C

D

E

Total

Degré

Graphe 1                                                                 Graphe 2

Théorème: Dans un graphe non orienté, la somme des degrés de tous ses sommets est égale au double de son nombre d’arêtes.

Définitions et exemples (suite) :                                                                                

– Deux sommets reliés par une arête sont dits adjacents.  Par exemple, les sommets

adjacents au point A du graphe 1 sont     …………………..      et les sommets adjacents au point

B du graphe 2 sont     …………………………………………..                                                                                                

– Un sommet est dit isolé s’il n’est relié à aucun autre sommet du graphe.  Par exemple, le

point     ………     du graphe     ……..     est isolé.

  1. Graphe complet

Définition : Un graphe non orienté est dit complet si tous les sommets de ce graphe sont adjacents (c’est-à-dire si chaque sommet est relié directement à chacun des autres).

Exemples :[pic 5][pic 6][pic 7]

Dans le cas où un graphe n’est pas complet, pour justifier qu’il ne l’est pas, il suffit de citer deux sommets de ce graphe qui ne sont pas adjacents, c’est-à-dire pas reliés par une arête. Par exemple, le graphe 1 du I) 2) n’est pas complet car   ……   et   ……. ne sont pas adjacents.

  1. Chaînes et cycles
  1. Définitions

Définitions :                                                                                                                                                                - Une chaîne est une liste ordonnée de sommets telle que chaque sommet de la liste soit adjacent au suivant (c’est-à-dire relié par une arête).                                                                                                                                        - Une chaîne fermée est une chaîne dont l’origine et l’extrémité sont les mêmes.                                           - Un cycle est une chaîne fermée composée d’arêtes toutes distinctes.       [pic 8][pic 9]

  1. Connexité

Définition : Un graphe est connexe si on peut relier n’importe quelle paire de sommets par une chaîne.                                                                                                                                                                                   [pic 10][pic 11][pic 12]

Pour justifier de la connexité ou non d’un graphe, si on trouve une chaîne passant pas tous les sommets de ce graphe, alors ce graphe est connexe. Si on trouve une paire de sommets qui ne peuvent pas être reliés par une chaîne, alors ce graphe n’est pas connexe.

...

Télécharger au format  txt (16.4 Kb)   pdf (599.5 Kb)   docx (274 Kb)  
Voir 31 pages de plus »
Uniquement disponible sur LaDissertation.com