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. Pour chaque graphe orienté de l'énoncé :
   1. Pour chaque sommet \(s\), donner la liste des successeurs de \(s\) ainsi que le degré sortant du sommet.
   2. Pour chaque sommet \(s\), donner la liste des prédécesseurs de \(s\) ainsi que le degré entrant du sommet.
   3. Pour chaque sommet \(s\) donner le degré total de \(s\).

Matrice d'adjacence

Soient \(n\in \mathbb{N}\) et \(G = (S, A)\) un graphe d'ordre \(n\). On appelle matrice d'adjacence de \(G\) le tableau \(n \times n\) où le coefficient à l'intesection de la ligne \(i\) et de la colonne \(j\) vaut 1 si \(i\) est un voisin de \(j\), \(0\) sinon.

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é, déterminer s'il est fortement connexe. S'il ne l'est pas, en donner les composantes fortements connexes.