Exercices de compréhension

On donne ci-dessous la représentation des graphes \(G_1\), \(G_2\), \(G_3\) et \(G_4\).

Définition d'un graphe

Pour chacun des graphes de l'énoncé :

1. Donner l'ensembles des sommets.
2. Donner l'ensemble des arêtes.
3. Donner l'ordre, la taille du graphe.

Graphe complet

Soit \(n\in \mathbb{N}\). On appelle graphe complet d'ordre \(n\) et on note \(K_n\) le graphe non orienté à \(n\) sommets \(\{1, 2, \ldots, n\}\) avec \(\{i, j\} \in A\) pour tout \(1 \leq i, j \leq n\), \(i \neq j\).

1. Dessiner \(K_3\), \(K_{4}\).
2. Quelle est la relation entre le degré et la taille du graphe \(K_n\) ?

Voisins, successeurs, prédécesseurs

1. Pour chaque sommet \(s\) de chacun des graphes non orientés \(G\) de l'énoncé, donner la liste des voisins de \(s\) ainsi que le degré du sommet.
2. 1. Pour chaque sommet \(s\) de chacun des graphes orientés \(G\) de l'énoncé, donner la liste des successeurs de \(s\) ainsi que le degré sortant du sommet.
   2. Pour chaque sommet \(s\) de chacun des graphes orientés \(G\) de l'énoncé, donner la liste des prédécesseurs de \(s\) ainsi que le degré entrant du sommet.

Matrice d'adjacence

Soient \(n\in \mathbb{N}\) et \(G = (S, A)\) un graphe orienté d'ordre \(n\). On appelle matrice d'ajacence de \(G\) le tableau \(n \times n\) où le coefficient à l'intesection de la ligne \(i\) et de la colonne \(j\) vaut le nombre d'arcs \((i, j) \in A\).

Ainsi, l'indice de ligne \(i\) correspond au sommet de départ et l'indice de colonne \(j\) correspond au sommet d'arrivée.

1. À quel graphe orienté correspond la matrice d'adjacence :

   \[ \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ \end{bmatrix} \]

2. 1. Donner les matrices d'adjacence des graphes de l'énoncé.

   2. Quelle propriété possède la matrice d'adjacence d'un graphe non orienté ?

Chemin, Distance, diamètre

Pour chaque graphe \(G\) de l'énoncé :

1. 1. Pour chaque couple \((u, v)\) de sommets, donner (si possible) la distance entre \(u\) et \(v\).
   2. En déduire le diamètre du graphe.
2. Donner, si cela est possible, un cycle.

Composantes connexes

1. Pour chaque graphe non orienté de l'énoncé, déterminer s'il est connexe. S'il ne l'est pas, en donner les composantes connexes.
2. Pour chaque graphe orienté de l'énoncé :
   1. Déterminer s'il est faiblement connexe. S'il ne l'est pas, en donner les composantes faiblements connexes.
   2. Déterminer s'il est fortement connexe. S'il ne l'est pas, en donner les composantes fortements connexes.