Vocabulaire des graphes et parcours

Dans une entreprise, un réseau informatique est composé de $6$ serveurs nommés $A$, $B$, $C$, $D$, $E$ et $F$. On modélise ce réseau par un graphe non orienté dont les sommets représentent les serveurs et les arêtes représentent les liaisons physiques directes entre eux.

Les connexions directes enregistrées sont les suivantes :

• Le serveur $A$ est relié aux serveurs $B$, $C$ et $D$.
• Le serveur $B$ est relié aux serveurs $A$, $C$ et $E$.
• Le serveur $C$ est relié aux serveurs $A$, $B$, $D$ et $F$.
• Le serveur $D$ est relié aux serveurs $A$ et $C$.
• Le serveur $E$ est relié aux serveurs $B$ et $F$.
• Le serveur $F$ est relié aux serveurs $C$ et $E$.

Combien d'arêtes comporte ce graphe ?

On considère un graphe simple non orienté d'ordre $7$ dont chaque sommet est initialement adjacent à tous les autres sommets du graphe.

On retire un certain nombre d'arêtes de ce graphe. Dans le graphe obtenu après cette opération, la somme des degrés de l'ensemble des sommets est égale à $30$.

Combien d'arêtes ont été retirées du graphe initial ?

Un graphe simple $G$ d'ordre $7$ est obtenu en retirant $4$ arêtes à un graphe complet à $7$ sommets.

On mesure les degrés de six de ses sommets, qui valent respectivement $6$, $5$, $5$, $5$, $4$ et $4$.

Déterminer le degré du septième sommet du graphe $G$.

Saisir la valeur du degré du septième sommet.

Un réseau informatique est constitué de $9$ serveurs interconnectés par des liaisons directes à double sens. Chaque liaison relie deux serveurs distincts et deux serveurs sont reliés par au plus une liaison directe.

Dans ce réseau :

• $6$ serveurs sont reliés chacun directement à exactement $4$ autres serveurs ;
• $2$ serveurs sont reliés chacun directement à exactement $2$ autres serveurs ;
• le dernier serveur est relié directement à $k$ autres serveurs.

Au total, le réseau comporte $17$ liaisons directes.

Saisir la valeur de $k$.

Soit $G$ un graphe d'ordre $6$ dont les sommets sont $A, B, C, D, E$ et $F$.

Le sommet $A$ est de degré $2$. Les cinq autres sommets $B, C, D, E$ et $F$ ont tous le même degré $k$. On sait que ce graphe comporte au total $11$ arêtes.

Déterminer et saisir la valeur du degré k.

Un graphe non orienté $G$ est obtenu en retirant $k$ arêtes à un graphe complet d'ordre $8$.

Dans le graphe $G$, $4$ sommets sont de degré $6$ et les $4$ autres sommets sont de degré $5$.

Saisir le nombre $k$ d'arêtes qui ont été supprimées.

Un centre de données héberge un réseau informatique composé de $8$ serveurs. Les liaisons de communication entre ces serveurs sont bidirectionnelles et modélisées par un graphe simple non orienté $G$, dont les sommets représentent les serveurs et les arêtes représentent les liaisons directes.

Afin de garantir que le réseau est connexe (c'est-à-dire qu'il existe toujours au moins une chaîne reliant deux serveurs quelconques), l'administrateur réseau impose que chaque serveur soit directement connecté à au moins $k$ autres serveurs.

Par une justification théorique complète, déterminer la valeur minimale de l'entier $k$ qui garantit la connexité du réseau, quelle que soit la disposition des liaisons.

Saisir la valeur minimale de $k$.

Un réseau informatique est modélisé par un graphe simple connexe d'ordre $n$ (avec $n \ge 4$).

Dans ce graphe, $4$ sommets sont de degré $5$, et tous les autres sommets sont de degré $3$.

De plus, il faudrait ajouter exactement $12$ arêtes à ce graphe pour obtenir un graphe complet ayant le même nombre de sommets.

Saisir l'ordre $n$ du graphe.

Soit $k$ un entier naturel supérieur ou égal à $3$. On considère une famille de graphes simples et connexes $G_k$ comportant chacun $10$ sommets.

Chaque graphe $G_k$ est constitué de :

• $k - 2$ sommets de degré $2k - 1$ ;
• $12 - k$ sommets de degré $k + 2$.

On sait que le graphe $G_k$ admet une chaîne eulérienne non fermée.

Saisir la valeur de $k$.