On a schématisé ci-dessous une partie du plan du métro londonien par un graphe $\Gamma$ dont les sommets sont les stations et les arêtes sont les lignes desservant ces stations.

Chaque station de métro est désignée par son initiale comme indiqué dans la légende.

1. Proposer un cycle qui permettrait de passer par chacune des stations de métro du graphe $\Gamma$.

2. Déterminer en justifiant si le graphe $\Gamma$ est connexe.

3. Déterminer en justifiant si le graphe $\Gamma$ est complet.

4. Donner la matrice d'adjacence $M$ du graphe $\Gamma$ (les sommets seront rangés dans l'ordre alphabétique).

5. On appelle chaîne eulérienne une chaîne qui permet de passer par toutes les arêtes une et une seule fois.

   Existe-t-il une chaîne eulérienne à ce graphe $\Gamma$ ? Si oui, en donner une.

Sarah, une jeune étudiante en géologie, souhaite partir en voyage en Islande avec des amis. Elle a loué une voiture tout terrain pour pouvoir visiter les lieux remarquables qu'elle a sélectionnés.
Sarah a construit le graphe ci-dessous dont les sommets représentent les lieux à visiter et les arêtes représentent les routes ou pistes :

1. Dans cette question, chaque réponse sera justifiée.

   1. Déterminer l'ordre du graphe.

   2. Déterminer si le graphe est connexe.

   3. Déterminer si le graphe est complet.

2. 1. Dresser un tableau dans lequel apparaîtront chaque arête avec son degré.

   2. Comment peut-on en déduire le nombre d'arêtes du graphe ?

3. On appelle $M$ la matrice associée au graphe précédent sachant que les sommets sont placés dans l'ordre alphabétique.

   $$M = \begin{pmatrix} 0 &0 &0 &0 &0 &0 &0 &1 &1 \\ 0 &0 &0 &0 &0 &0 &1 &0 &0 \\ 0 &0 &0 &0 &0 &1 &0 &1 &1 \\ 0 &0 &0 &0 &0 &0 &1 &1 &0 \\ 0 &0 &0 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &1 &0 &1 &0 &1\\ \ldots&\ldots&\ldots&1 &1 &1 &0 &0 &1\\ \ldots&\ldots&\ldots&1 &0 &0 &0 &0 &0\\ \ldots&\ldots&\ldots&0 &1 &1 &1 &0 &0 \end{pmatrix}$$

   Il manque certains coefficients de la matrice $M$. Compléter et recopier uniquement la partie manquante de cette matrice.

Un parcours sportif est composé d'un banc pour abdominaux, de haies et d'anneaux. Le graphe orienté ci-dessous indique les différents parcours conseillés partant de D et terminant à F.

Les sommets sont: D (départ), B (banc pour abdominaux), H (haies), A (anneaux) et F (fin du parcours).

Les arcs représentent les différents sentiers reliant les sommets.

1. Quel est l'ordre du graphe?

2. Est-il possible de suivre un parcours en passant par toutes les étapes ?

3. On note $M$ la matrice d'adjacence de ce graphe où les sommets sont rangés dans l'ordre alphabétique. Déterminer cette matrice $M$.

4. Le responsable souhaite ajouter une barre de traction notée T. De nouveaux sentiers sont construits et de nouveaux parcours sont possibles.

   La matrice d'adjacence $N$ associée au graphe représentant les nouveaux parcours, dans lequel les sommets sont classés en ordre alphabétique, est :

   $$N = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}$$

   Compléter le graphe précédent en ajoutant les arcs nécessaires pour que le graphe orienté obtenu corresponde à la matrice $N$.

Voici la carte des arrondissements du département de la Marne lors des dernières élections législatives.

1. Modéliser cette carte des arrondissements par un graphe dans lequel les sommets sont les arrondissements (prendre l'initiale du nom de l'arrondissement comme nom du sommet) et les arêtes traduisent la présence d'une frontière entre deux régions.

2. Le graphe est-il orienté ?

3. Le graphe est-il complet ?

4. Le graphe est-il connexe ?

$P_1$, $P_2$, $P_3$, $P_4$, $P_5$ et $P_6$ désignent 6 espèces de poissons.

Dans le tableau ci-dessous, une croix signifie que deux espèces ne peuvent cohabiter dans le même milieu.

1. Le graphe où les sommets sont des espèces de poissons tandis que les arêtes indiquent les incompatibilités entre espèces est-il orienté ou non ? Justifier.

2. Représenter ce graphe.

3. Combien de bassins différents faut-il prévoir au minimum pour pouvoir élever ces 6 espèces de poissons ?

Une classe de Terminale est en voyage scolaire en Angleterre.

Les professeurs organisateurs de ce voyage décident de visiter plusieurs sites de Londres.

Les sites retenus dans Londres sont les suivants : Warren Street, Oxford Circus, Piccadilly Circus, Leicester Square, Holborn, Embankment et Temple. Ces lieux sont désignés respectivement par les lettres $W$, $O$, $P$, $L$, $H$, $E$ et $T$.

Le professeur d'anglais aimerait représenter l'ensemble des sites à visiter avec les jonctions possibles entre eux à l'aide d'un graphe.

Il y a demandé de l'aide à son collègue de mathématiques, qui très taquin, lui a transmis le "tableau de nombres" suivant :

Le professeur de maths lui a aussi dit que :

• il avait considéré les lettres des sites dans l'ordre alphabétique,

• qu'il fallait alors considéré le "tableau de nombres" comme la matrice d'adjacence du graphe recherché.

Tout cela est très obscur pour le professeur d'anglais, il est tout déo=sorienté ! Il fait donc appel à vous pour obtenir le graphe recheché.

Construire un graphe correspondant au besoin du professeur d'anglais ; il vous remerciera au moins d'un grand "Thanks a lot !"

Lors d'une soirée chez mes voisins, j'ai entendu 45 tintements de verre.

En supposant que chaque personne a trinqué une et une suele fois avec les autres, déterminer le nombre de personnes présentes.

Un État virtuel compte 11 grandes viles dont la capitale $C$.

Chacune de ces 11 viles est reliée a au moins 5 grandes villes par une autoraute.

Peut-on aller, en emprunant l'autoroute, de la capitale à chacune des autres grandes villes de ce pays ?

On donne ci-dessous le plan simplifié d'un lycée :

1. Traduire la situation par un graphe dont les sommets représentent les salles et dont les arêtes représentent les passages possibles entre ces salles.

2. Quel est l'ordre du graphe ?

3. Le graphe est-il connexe ? Qu'en déduire concrètement ?

4. Le graphe est-il complet ? Qu'en déduire concrètement ?

À la fin d'un semestre, les examines de licence prposent six options : Calcul différentiel ; Géométrie euclidienne ; Théorie des nombres ; Algèbre linéaire ; Probabilités et Statistiques.

Chacun des candidats a pu choisir deux ou trois de ces options.

Certians ont choisi Théorie des nombres et Algèbre linéaire ; d'autres le Calcul différentiel, les Probabilités et les Statistiques ; enfin d'autres ont choisi Géométrie euclidienne et Théorie des nombres.

Sachant que les étudiants passent au plus une épreuve chaque jour, combien peut-on programmer d'épreuves au maximum en une journée ?

Parmi 11 élèves volontaires, un professeur de mathématiques doit constituer des groupes d'au plus 4 personnes pour faire préparer une présentation orale.

Le professeur doit faire attention aux relations entre les élèves :

• Erwan ne supporte pas Kenza et n'apprécie ni Gwendoline, ni Blaise, ni Chloé.

• Jordan refuse de travailler avec Gwendoline,

• Kenza n'arrive jamais a resté sérieuxe ni avec Aya, ni avec Driss.

• Blaise a du mal à travailler avec Erwan,

• Chloé ne supporte ni Jordan, ni Blaise

• Comme Hector a remplacé Fred dans le coeur d'Ilana, Fred ne veut plus échanger un mot avec Hector ou Ilana.

Comme le professeur de mathématiques n'arrive pas à constituer le minimum de groupes ne dépassant pas 4 élèves, il fait appel à vous :

Combien de groupes ne dépassant pas 4 élèves peut-on faire au minimum ? Proposez une répartition des élèves pour avoir un minimum de groupes.

Partie A : Conjecture d'un théorème

Voici ci-dessous différents graphes :

• Pour chacun des graphes ci-dessus :

  • Chercher si le graphe admet une chaîne eulérienne ou non.

  • Dresser le tableau des degrés du graphe.

• Conjecturer un lien entre l'existence d'une chaîne eulérienne et les degrés du graphe.

Partie B : Application au problème du pont de Königsberg

On considère un graphe contenant une chaîne eulérienne.

1. Expliquer pourquoi tous les sommets sont d'ordre pair, sauf éventuellement le premier et le dernier de la chaîne.

2. On se place dans le cas où les extrémités sont confondues. Considérons un sommet $S$ par lequel la chaîne est passée $k$ fois, $k\in\mathbb{N}$. Quel est le degré de $S$ ?

3. On se place à présent dans le cas où les extrémités ne sont pas confondues? Quel est le degré Quel est le degré d'une extrémité par lequel la chaîne est passée $k$ fois, $k\in\mathbb{N}$ ?

4. Voici un théorème, énoncé par Euler en 1736 et prouvé par Hierholzer en 1873 :

   un graphe connexe possède une chaîne eulérienne si, et seulement si, au plus deux de sommets sont de degré impair.

   Avec les questions précédentes, a-ton prouvé ce thérème ou non ?

5. Conclure sur le problème des ponts de Königsberg.

Partie A : étude du problème

Notons $m$ l'ordre du plus grand des sous-graphes complets de $\Gamma$ et $\Delta$ le plus grand des degré des sommets de $\Gamma$.

Justifier que $m\leqslant \gamma \leqslant \Delta+1$.

Partie B : algorithme de Welh-Powell

Pour colorier un graphe, on peut utiliser l'algorithme glouton suivant :

• Étape 1 : Ranger les sommets par ordre décroissant de leurs degrés ;

• Étape 2 : Choisir une couleur ; Affecter cette couleur au premier sommet de la liste non encore coloré ;

• Étape 3 : Suivre la liste en attribuant cette même couleur à tout sommet :

  • qui n'est pas encore coloré ;

  • et qui n'est pas adjacent à un sommet coloré avec cette couleur.

• Étape 4 : Continuer jusqu'à ce que la liste soit finie :

  Si tous les sommets ne sont pas colorés, choisir une couleur qui n'est pas encore utilisée et recommencer les étapes 2 et 3 ;

  Continuer tant que chaque sommet n'est pas coloré.

Colorier le graphe ci-dessous à l'aide de cet algorithme :

Partie C : application sur un problème concret

Diogène est éducateur de chiens ; il donne donne des leçons à 9 chiots : Antisthène, Bion, Cléomène, Démétrios, Échéclès, Favonius, Gadarides, Héracléios et Isidore.

Diogène souhaite réaliser des exercices par petits groupes, de 2 ou 3 chiots tout en respectant la nature de ces animaux :

• Favonius ne pense qu'à jouer si ce chiot est trop proche de Bion, Cléomène ou d'Échéclès,

• Démétrios est très distrait si Bion et Favonius sont à proximité,

• Isidore ne supporte pas le caractère trop fougueux de Gadarides,

• Antisthène ne tolère que la présence d'Échéclès et d'Héraclios.

1. Représenter cette situation à l'aide d'un graphe $\Gamma$.

2. Le graphe est-il connexe ? Justifier.

3. 1. Déterminer un sous-graphe complet d'ordre maximal du graphe $\Gamma$.

   2. Que peut-on en déduire pour le nombre chromatique du graphe $\Gamma$ ?

4. Doner la valeur du nombre chromatique du graphe $\Gamma$.

5. Peut-on proposer une répartition des chiots en groupes de deux ou trpois chiots pouvant travailler ensemble ?