Définitions

Question 1

Définir un graphe (et un p-graphe).

Answer 1

• Un graphe orienté G(X,U) se présente par un ensemble fini X de sommets et un ensemble U d’arcs reliant certains de ces sommets entre eux.
• Un p-graphe ne contient pas plus que p arcs entre chaque sommet.

Question 2

Définir un graphe partiel et un sous-graphe.

Answer 2

• Sous-graphe : suppression de certains sommets et des arcs qui leur sont liés
• Graphe partiel : suppression de certains arcs

Question 3

Comment construit-on une matrice d’adjacence et une matrice d’incidence ? Quelles sont les places mémoires associées ?

Answer 3

• Matrice d’adjacence : matrice carrée avec mij = 1 s’il existe un arc orienté reliant xi à xj, mij = 0 sinon (n*n)
• Matrice d’incidence : mij = 1 si uj part de xi, mij = -1 si uj arrive à xi et 0 sinon (n*m)

Question 4

Définir les termes : chaîne et cycle.

Answer 4

• chaîne : suite d’arêtes telle que chacune d’elles est rattachée à la précédente par une extrémité et à la suivante par l’autre extrémité
• cycle : chaîne se refermant sur elle-même

Question 5

Définir les termes : chemin et circuit.

Answer 5

• chemin : une suite d’arcs telle que tout arc de cette suite, sauf le dernier, a pour extrémité terminale l’extrémité initiale de l’arc suivant
• circuit : chemin fini dont le sommet terminal coïncide avec le sommet initial

Question 6

Définir la connexité d’un graphe.

Answer 6

Un graphe G(X,U) est (fortement) connexe si ∀ i,j∈X, ∃ une chaine (chemin) entre i et j