Une île imaginaire dont la carte est représentée ci-dessous, est composée de six provinces, notées A, B, C, D, E et F.
On s'intéresse aux frontières séparant ces provinces. On traduit cette situation par un graphe dont les sommets sont les provinces et où chaque arête représente une frontière entre deux provinces.
On admet que le graphe G ci-dessous représente cette situation :
Donner l'ordre du graphe G, puis le degré de chacun de ses sommets.
Le graphe G a 6 sommets donc G est d'ordre 6.
Les degrés des différents sommets sont donnés dans le tableau ci-dessous:
| Sommets | A | B | C | D | E | F |
| Degré | 3 | 4 | 2 | 4 | 4 | 3 |
Peut-on visiter cette île en franchissant une et une seule fois chacune des dix frontières ? Justifier. Si oui, proposer un parcours possible.
Visiter cette île en franchissant une et une seule fois chacune des dix frontières revient à chercher une chaîne eulérienne.
Avec les sommets classés dans l'ordre alphabétique, la matrice M associée au graphe G est
D'où
Aucun des termes de la matrice n'est nul, il existe donc au moins une chaîne de longueur 2 reliant deux sommets quelconques de ce graphe. Donc, le graphe G est connexe.
Le graphe G est connexe et a deux sommets de degré impair les sommets A et F, alors d'après le théorème d'Euler, Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2. il existe une chaîne eulérienne.
Il est donc possible de visiter cette île en franchissant une et une seule fois chacune des dix frontières. Un parcours possible commençant par A et finissant par F est ADBCEDFAEBF.
Le graphe G possède-t-il un sous-graphe complet d'ordre 3 ? Si oui, en citer un.
Préciser, sans justification, si le graphe G possède un sous graphe complet d'ordre 4.
Quelle conséquence cela a-t-il sur le nombre chromatique c du graphe G ?
Le graphe G possède plusieurs sous-graphe complet d'ordre 3 on peut citer au choix ADE, ADF, BCE, BDE ou BDF.
Le graphe G ne possède aucun sous-graphe complet d'ordre 4.
Le graphe G possède un sous-graphe complet d'ordre 3 donc le nombre chromatique .
D'autre part, le plus haut degré des sommets est 4 donc le nombre chromatique .
L'encadrement du nombre chromatique du graphe G est .
Attention, ce n'est pas parce que le graphe G n'a pas de sous graphe complet d'ordre 4 que l'on peut conclure que .
Proposer une coloration de la carte (ou du graphe) avec le minimum de couleurs afin que deux provinces qui ont une frontière commune aient des couleurs différentes (on peut remplacer les couleurs par différents hachurages).
Une coloration du graphe à l'aide de trois couleurs est possible, comme on peut le voir dans l'exemple ci-dessous. Le nombre chromatique de graphe G est donc .
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.