Analyse des besoins pour le développement logiciel

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.

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.

...