Sauter au contenu

Mathématiques discrètes Version préliminaire

Section 7.1 Introduction à la théorie des graphes

La théorie des graphes est une théorie qui a été utilisée pour la première fois par le mathématicien Leonhard Euler afin de traiter le problème des sept ponts de Königsberg. La ville de Königsberg est construite autour de deux îles reliées entre elles. Six autres ponts relient les rives de la rivière à l’une des deux îles.
🔗
Euler a représenté la situation à l’aide de sommets (représentant les îles et les rives) et d’arêtes (représentant les ponts). Le problème est alors de savoir s’il est possible d’effectuer une marche passant par chaque pont une seule fois.
🔗
Depuis, on a utilisé la théorie des graphes pour représenter de nombreuses situations. Par exemple, lorsqu’on veut vérifier qu’un circuit électronique est planaire (pour savoir s’il est possible de le construire sur une carte), représenter la connexion entre plusieurs ordinateurs sur un réseau informatique, ou encore pour représenter un réseau téléphonique.
🔗
Les algorithmes utilisés par les différents moteurs de recherche utilisent la théorie des graphes afin de représenter les différents sites et les liens qui existent entre ceux-ci. Finalement, on peut aussi penser aux applications permettant de trouver le chemin le plus rapide pour voyager en voiture, à pied ou à vélo.
🔗
On commence par introduire la définition de graphe simple et de graphe orienté ainsi que quelques définitions permettant de décrire les relations entre les sommets d’un graphe. Après l’étude de quelques propriétés, on introduit certains graphes particuliers, ainsi que la classe des graphes bipartis. Finalement, on montre comment on peut créer un graphe à partir de graphes déjà connus.
🔗

Sous-section 7.1.1 Les types de graphes

Tel que mentionnés plutôt, beaucoup de situations peuvent être représentées à l’aide de sommets reliés entre eux par des arêtes. Ces représentations sont des objets mathématiques appelés des graphes.
🔗
Il existe plusieurs types de graphes selon les situations qu’on veut représenter. Ici, on donne la définition de deux types de graphes différents. Ces définitions sont les définitions formelles et abstraites d’un graphe, mais il faut garder en tête qu’une des forces des graphes est qu’ils peuvent aider à visualiser les liens entre différents objets. Il est donc souvent plus utile de représenter un graphe par une figure que de travailler avec sa définition formelle.
🔗

Définition 7.1.1. Un graphe simple.

Un graphe simple \(G=(S,A)\) est défini à l’aide d’une paire d’ensembles \(S\) et \(A\text{.}\)
🔗
L’ensemble \(S\) est un ensemble non vide quelconque. On l’appelle l’ensemble des sommets de \(G\text{.}\)
🔗
Les éléments de l’ensemble \(A\) sont des ensembles formés de deux éléments de \(S\text{.}\) C’est-à-dire que les éléments de \(A\) sont de la forme \(a=\{s,t\}\text{,}\) où \(s\neq t\in\ S\) (\(s\) et \(t\) sont des sommets de \(G\)). On dit que \(A\) est l’ensemble des arêtes de \(G\text{.}\)
🔗
Soit \(a=\{s,t\}\in\,A,\) on dira que \(s\) et \(t\) sont les extrémités de \(a\text{.}\) On dira qu’une arête connecte ses deux extrémités ensemble.
🔗
🔗

Remarque 7.1.2. Sur la définition des graphes simples.

Soit \(G=(S,A)\) un graphe simple, par la définition de \(A\text{,}\) on sait que
  1. Les deux extrémités d’une même arête sont distinctes;
    🔗
  2. L’ordre dans lequel on écrit les sommets n’a pas d’importance, car \(\{s,t\}=\{t,s\}\text{.}\) On dit que le graphe est non orienté;
    🔗
  3. Deux arêtes distinctes ont au moins un sommet distinct (il n’y a pas deux arêtes différentes qui relient les deux mêmes sommets).
    🔗
🔗
Aussi, en général, il se peut que \(S\) et \(A\) soient des ensembles infinis. Cependant, nous allons principalement considérer des graphes dont l’ensemble des sommets est un ensemble fini. On dira alors que le graphe est fini.
🔗
Sauf indication contraire, un graphe sera un graphe fini.
🔗
🔗

Exemple 7.1.3. Deux graphes.

Voici deux graphes simples avec respectivement \(7\) et \(5\) sommets.
🔗
(a) Le graphe \(G\) à \(7\) sommets
🔗
(b) Le graphe \(H\) à \(5\) sommets
🔗
Figure 7.1.4. Deux graphes
🔗
Les arêtes du graphe \(G\) sont:
\begin{align*} \{a,b\}\amp;\{a,f\};\\ \{b,f\}\amp;\{b,e\};\{b,c\};\\ \{c,f\}\amp;\{c,e\};\{c,d\};\\ \{e,f\}\amp; \end{align*}
🔗
Les arêtes du graphe \(H\) sont:
\begin{align*} \{a,b\}\amp;\{a,d\};\{a,e\}\\ \{b,d\}\amp;\{b,c\}\\ \{d,e\}\amp; \end{align*}
🔗
🔗

Définition 7.1.5. Un graphe orienté.

Un graphe orienté \(G=(S,A)\) est défini à l’aide d’une paire d’ensembles \(S\) et \(A\text{.}\)
🔗
L’ensemble \(S\) est un ensemble non vide quelconque. On l’appelle l’ensemble des sommets de \(G\text{.}\)
🔗
L’ensemble \(A\) est un couple d’éléments de \(S\text{.}\) C’est-à-dire que les éléments de \(A\) sont de la forme \(a=(s,t)\text{,}\) où \(s\neq t\in\ S\) (\(s\) et \(t\) sont des sommets de \(G\)). On dit que \(A\) est l’ensemble des arêtes de \(G\text{.}\)
🔗
Soit \(a=(s,t)\in\,A,\) on dira que \(s\) et \(t\) sont les extrémités de \(a\text{.}\) On dira aussi que \(a\) est l’arête allant de \(s\) vers \(t\text{.}\) Finalement, on représentera \(a\) à l’aide d’une flèche partant de \(s\) et terminant à \(t\text{.}\)
🔗
🔗

Exemple 7.1.6. Un graphe orienté.

Voici un graphe orienté à \(4\) sommets.
🔗
Figure 7.1.7. Un graphe orienté
🔗
L’ensemble des sommets du graphe est \(S=\{1,2,3,4\}\text{,}\) et les arêtes sont:
\begin{gather*} (1,3);(1,4);\\ (2,1);(2,3);(2,4)\\ (3,1);(3,4);\\ (4,2) \end{gather*}
🔗
🔗

Remarque 7.1.8. Quelques différences entre graphes simples et graphes orientés.

Soit \(G=(S,A)\) un graphe orienté, par la définition de \(A\text{,}\) on sait que
  1. Les deux extrémités d’une même arête sont distinctes;
    🔗
  2. L’ordre dans lequel on écrit les sommets est important, car \((s,t)\neq (t,s)\text{;}\)
    🔗
  3. Deux arêtes distinctes peuvent avoir les mêmes sommets, mais pas dans le même ordre, il n’y a donc pas deux arêtes différentes qui partent finissent aux mêmes sommets.
    🔗
🔗
Comme pour les graphes simples, nous allons principalement considérer des graphes dont l’ensemble des sommets est un ensemble fini. On dira alors que le graphe est fini.
🔗
Sauf indication contraire, un graphe sera un graphe fini.
🔗
🔗
Une autre définition importante dans la théorie des graphes est celle d’un sous-graphe. Intuitivement, un graphe \(H\) est un sous-graphe d’un graphe \(G\) si l’on retrouve \(H\) dans \(G\text{.}\) Plus formellement, on a la définition suivante.
🔗

Définition 7.1.9. Sous-graphe.

Une graphe \(H=(S_H, A_H)\) est un sous-graphe du graphe \(G=(S_G,A_G)\) si
  • \(S_H\subseteq S_G\text{;}\)
    🔗
    🔗
  • \(A_H\subseteq A_G\text{;}\)
    🔗
    🔗
  • pour toute arrête \((x,y)\in A_H\text{,}\) on a \(x\in H\) et \(y\in H\text{.}\)
    🔗
    🔗
🔗
🔗
Voici un exemple d’un sous-graphe \(H\) dans un graphe \(G\text{.}\)
🔗
described in detail following the image
Le graphe de Petersen est illustré à gauche, avec au centre le sous-graphe central mis en évidence. À gauche, on retrouve une copie de ce sous-graphe, seule.
🔗
Figure 7.1.10. Un sous-graphe \(H\) dans un graphe \(G\)
🔗
Deux sous-graphes particulier s’obtiennent d’un graphe \(G\) en enlevant un sommet ou une arête de \(G\text{.}\) Soit \(G\) un graphe, \(s\in S_G\) et \(a\in A_G \text{.}\) On définit le sous-graphe \(G\ s\text{,}\) nommé \(G\) sans \(s\text{,}\) comme le sous-graphe obtenu de \(G\) en enlevant le sommet \(g\) et toute les arêtes qui lui sont incidentes (qui le contiennent). De plus, on définit le sous-graphe \(G\ a\text{,}\) nommé \(G\) sans \(a\text{,}\) comme le sous-graphe de \(G\) avec l’arête \(a\) effacée.
🔗
Finalement, dans les prochaines sections, nous allons étudier des graphes qu’on dira pondérés. Il s’agit simplement de graphes (simples ou orientés) pour lesquels on donne un poids (un nombre réel positif) à chacune des arêtes. C’est ce genre de graphes qui est utilisé pour trouver le chemin le plus court entre deux points sur une carte.
🔗
🔗

Sous-section 7.1.2 Terminologie de base

Pour faire l’étude de graphes, on aimerait faire ressortir certaines caractéristiques de ceux-ci. Par exemple, est-il possible de tracer le graphe sans qu’aucune arête n’en croise une autre? Ou encore, est-il possible de tracer un chemin passant par toutes les arêtes une seule fois?
🔗
D’un autre côté, on aimerait également être en mesure de différencier les graphes les un aux autres. En effet, il arrive souvent que deux graphes semblent à priori bien différents, alors qu’il s’agit en fait du même graphe.
🔗
On commence donc à regarder certaines des caractéristiques des graphes. Pour ce faire, on peut commencer par étudier individuellement chaque sommet d’un graphe. La propriété de base d’un sommet est l’ensemble des sommets avec lesquels il est relié par une arête. On peut également regarder le nombre de connexions partant de ce sommet.
🔗

Définition 7.1.11. Voisinage et degré.

Soit \(G=(S,A)\) un graphe simple, et soit \(s,\,t\in\,S:\)
  • On dira que \(s\) est adjacent à \(t\text{,}\) ou bien que \(s\) est un voisin de \(t\) dans \(G\) si \(s\) et \(t\) sont les extrémités d’une arête de \(G\text{,}\) c’est-à-dire si \(\{s,t\}\in A\text{.}\)
    🔗
  • Le voisinage de \(s,\) noté \(V(s)\) est l’ensemble de tous les voisins de \(s\text{.}\)
    🔗
  • Soit \(R\) un sous-ensemble des sommets de \(G\text{,}\) on note \(V(R)\) l’union de tous les voisinages \(V(s)\) avec \(s\in\, R \text{.}\)
    🔗
  • Le degré de \(s\) est le nombre de voisins de \(s\text{.}\)
    🔗
  • Le degré du sommet \(s\) sera noté \(\deg(s)\text{.}\)
    🔗
🔗
🔗

Exemple 7.1.12. Voisinage et degré.

Déterminer le voisinage et le degré de chaque sommet des graphes \(G\) et \(H\) de l’exercice 7.1.3. Calculer la somme des degrés de tous les sommets de chacun des graphes.
Solution 1.
Pour \(G \)
🔗
\begin{align*} V(a)\amp=\{b,f\} \amp \deg(a)\amp=2\\ V(b)\amp=\{a,c,e,f\} \amp \deg(b)\amp=4\\ V(c)\amp=\{b,d,e,f\} \amp \deg(c)\amp=4\\ V(d)\amp=\{c\} \amp \deg(d)\amp=1\\ V(e)\amp=\{b,c,f\} \amp \deg(e)\amp=3\\ V(f)\amp=\{a,b,c,e\} \amp \deg(f)\amp=4\\ V(g)\amp=\{\} \amp \deg(g)\amp=0 \end{align*}
🔗
De plus, on a
\begin{equation*} \deg(a)+\deg(b)+\deg(c)+\deg(d)+\deg(e)+\deg(f)+\deg(g)=2+4+4+1+3+4+0=18 \end{equation*}
🔗
🔗
Solution 2.
Pour \(H \)
🔗
\begin{align*} V(a)\amp=\{b,d,e\} \amp \deg(a)\amp=3\\ V(b)\amp=\{a,c,d\} \amp \deg(b)\amp=3\\ V(c)\amp=\{b\} \amp \deg(c)\amp=1\\ V(d)\amp=\{a,b,e\} \amp \deg(d)\amp=3\\ V(e)\amp=\{a,d\} \amp \deg(e)\amp=2 \end{align*}
🔗
De plus, on a
\begin{equation*} \deg(a)+\deg(b)+\deg(c)+\deg(d)+\deg(e)=3+3+1+3+2=12 \end{equation*}
🔗
🔗
🔗
En regardant l’exemple précédent, on remarque que, lorsqu’on prend la somme des degrés de tous les sommets d’un graphe, chaque arête est comptée deux fois. On peut généraliser pour obtenir le théorème suivant.
🔗

Démonstration.

La partie gauche de l’équation compte la somme des degrés de tous les sommets. On compte cette somme d’une autre manière, en regardant les arêtes. Chaque arête contribue au degré de deux sommets. La somme des degrés des sommets est donc égale à deux fois le nombre d’arêtes.
🔗
🔗

Exemple 7.1.14.

Combien d’arêtes y a-t-il dans un graphe de \(10\) sommets ayant chacun un degré \(6\text{?}\)
🔗
Réponse.
\(30\)
🔗
Solution.
Si \(m\) est le nombre d’arêtes, on a que \(2m=deg(s_1)+\cdots + \deg(s_2)=6+6+6+6+6+6+6+6+6+6=10\cdot 6\text{.}\) Ainsi, on a bien que \(m=\frac{10\cdot 6}{2}=30\text{.}\)
🔗
🔗
🔗

Démonstration.

Soit \(G=(S,A)\) un graphe, on pose \(S=S_1\cup S_2,\) où \(S_1=\left\{s\in\,S|\deg(s)\equiv 1 \mod 2\right\}\) et \(S_2=\left\{s\in\,S|\deg(s)\equiv 0 \mod 2\right\}\text{.}\)
🔗
On suppose que \(S_1=\left\{s_1,\,s_2,\dots,\,s_n\right\}\) et \(S_2=\left\{t_1,\,t_2,\dots,\,t_k\right\}\text{.}\) On veut montrer que \(n\) est pair.
🔗
Par la proposition 7.1.13, on sait que si \(m\) est le nombre d’arêtes de \(G\text{,}\) alors \(\deg(s_1)+\deg(s_2)+\cdots+\deg(s_n)+\deg(t_1)+\deg(t_2)+\cdots+\deg(t_k)=2m \equiv 0 \mod 2\text{.}\) Ainsi, on a
\begin{align*} 0\amp\equiv \deg(s_1)+\deg(s_2)+\cdots+\deg(s_n)+\deg(t_1)+\deg(t_2)+\cdots+\deg(t_k) \mod 2\\ 0\amp\equiv \underbrace{1+1+\cdots+1}_{n\text{ fois}}+\underbrace{0+0+\cdots+0}_{k\text{ fois}}\mod 2\\ 0\amp\equiv n\mod 2 \end{align*}
Ainsi, on a bien que \(n\) est pair.
🔗
🔗
Pour les graphes orientés, il faut adapter un peu la notion de degré.
🔗

Définition 7.1.16. Degré pour un graphe orienté.

Soit \(G=(S,A)\) un graphe orienté, et soit \(s,\,t\in\,S:\)
  • On dira que \(s\) est adjacent à \(t\text{,}\) ou bien que \(s\) est un voisin de \(t\) dans \(G\) si \(s\) et \(t\) sont les extrémités d’une arête de \(G\text{,}\) c’est-à-dire si \((s,t)\in A\) ou si \((t,s)\in A\text{.}\)
    🔗
  • Si \((s,t)\in A\text{,}\) on dira que \(s\) est l’extrémité initiale de \((s,t)\text{,}\) alors que \(t\) est l’extrémité terminale ou finale de \((s,t)\text{.}\)
    🔗
  • Le degré entrant de \(s\text{,}\) noté \(\deg^-(s)\text{,}\) est le nombre d’arêtes ayant \(s\) comme extrémité terminale.
    🔗
  • Le degré sortant de \(s\text{,}\) noté \(\deg^+(s)\text{,}\) est le nombre d’arêtes ayant \(s\) comme extrémité initiale.
    🔗
🔗
🔗

Exemple 7.1.17. Degré entrant et sortant.

Déterminer les degrés entrants et sortants de chaque sommet du graphe orienté de l’exercice 7.1.6.
Solution.
\begin{align*} \deg^-(1)\amp=2 \amp \deg^+(1)\amp=2\\ \deg^-(2) \amp=1 \amp \deg^+(2)\amp=3\\ \deg^-(3) \amp=2 \amp \deg^+(3)\amp=2\\ \deg^-(4)\amp=3 \amp \deg^+(4)\amp=1 \end{align*}
🔗
De plus, on remarque que
\begin{equation*} \deg^-(1)+\deg^-(2)+\deg^-(3)+\deg^-(4)=2+1+2+3=8\text{.} \end{equation*}
De même,
\begin{equation*} =\deg^+(1)+\deg^+(2)+\deg^+(3)+\deg^+(4)=2+3+2+1=8 \end{equation*}
🔗
🔗
🔗
En regardant l’exemple précédent, on remarque que, lorsqu’on prend la somme des degrés entrants de tous les sommets d’un graphe, chaque arête est comptée une fois. De même, lorsqu’on prend la somme des degrés sortants de tous les sommets d’un graphe, chaque arête est comptée une fois. On peut généraliser pour obtenir le théorème suivant.
🔗
🔗

Sous-section 7.1.3 Quelques graphes particuliers

Certains graphes simples ont des formes particulières qui se retrouve dans plusieurs applications. Voici quelques exemples de classes de graphes simples.
🔗

Définition 7.1.19.

Un graphe complet à \(n\) sommets, noté \(K_n,\) est un graphe qui contient une arête entre chaque paire de sommets distincts.
🔗
🔗

Exemple 7.1.20. Les premiers graphes complets \(K_n\).

Voici des représentations de \(K_n\) pour \(n=1,\,2,\,3,\,4,\,5 \text{ et } 6\text{.}\)
🔗
(a) \(K_1\)
🔗
(b) \(K_2\)
🔗
(c) \(K_3\)
🔗
(d) \(K_4\)
🔗
(e) \(K_5\)
🔗
(f) \(K_6\)
🔗
Figure 7.1.21. \(K_n\)
🔗
🔗

Définition 7.1.22.

Soit \(n\geq 3.\) Le graphe cyclique (ou le cycle) \(C_n\) à \(n\) sommets \(s_1,\,s_2,\,\dots,\,s_n\) est le graphe dont les arêtes sont \(\{s_1,s_2\},\,\{s_2,s_3\},\,\dots,\,\{s_{n-1},s_n\}\) et \(\{s_n,s_1\}\text{.}\)
🔗
🔗

Exemple 7.1.23. Les premiers graphes cycliques \(C_n\).

Voici des représentations de \(C_n\) pour \(n=3,\,4,\,5 \text{ et } 6\text{.}\)
🔗
(a) \(C_3\)
🔗
(b) \(C_4\)
🔗
(c) \(C_5\)
🔗
(d) \(C_6\)
🔗
Figure 7.1.24. \(C_n\)
🔗
🔗

Définition 7.1.25.

Soit \(n\geq 3.\) La roue \(W_n\) à \(n+1\) sommets est le graphe défini de la façon suivante.
🔗
On part du graphe \(C_n\text{,}\) on note ses sommets \(s_1,\,s_2,\,\dots,\,s_n\) et on lui ajoute un sommet \(s_{n+1}\text{.}\)
🔗
On ajoute ensuite les arêtes \(\{s_i,s_{n+1}\}\) pour \(i=1,\,2,\,\dots,\, n\text{.}\)
🔗
🔗

Exemple 7.1.26. Les premières roues \(W_n\).

Voici des représentations de \(W_n\) pour \(n=3,\,4,\,5 \text{ et } 6\text{.}\)
🔗
(a) \(W_3\)
🔗
(b) \(W_4\)
🔗
(c) \(W_5\)
🔗
(d) \(W_6\)
🔗
Figure 7.1.27. \(W_n\)
🔗
🔗
On termine avec les graphes appelés les hypercubes.
🔗

Définition 7.1.28. Les \(n\)-Cubes \(Q_n,\) version 1.

On construit \(Q_n\) par récurrence, c’est-à-dire qu’on définit \(Q_0,\text{,}\) et ensuite on donne une méthode pour définir \(Q_{n+1}\) à partir de \(Q_n\text{.}\)
🔗
Le graphe \(Q_0\) est l’unique graphe à \(1\) sommet.
🔗
À partir de \(Q_n,\) on définit \(Q_{n+1}\) de la façon suivante. On construit tout d’abord deux copies de \(Q_n\text{.}\)
🔗
Ensuite, on ajoute une arête entre chaque sommet de la première copie de \(Q_n\) vers le sommet correspondant dans la deuxième copie de \(Q_n\text{.}\)
🔗
🔗

Exemple 7.1.29. Les premiers \(n\)-cubes \(Q_n\).

Voici des représentations de \(Q_n\) pour \(n=0,\,1,\,3,\,4 \text{ et } 5\text{.}\)
🔗
(a) \(Q_0\)
🔗
(b) \(Q_1\)
🔗
(c) \(Q_3\)
🔗
(d) \(Q_4\)
🔗
(e) \(Q_5\)
🔗
Figure 7.1.30. \(Q_n\)
🔗
🔗
🔗

Sous-section 7.1.4 Graphes bipartis et coloration des graphes

L’une des applications récentes de la théorie des graphes est la représentation d’énormes réseaux d’informations tels que les réseaux sociaux. Dans ce cas, les usagers sont représentés par des sommets, et les liens entre les usagers sont représentés par des arêtes. L’étude de ces graphes fait l’objet de beaucoup de recherche présentement.
🔗
Dans plusieurs situations, il arrive qu’on puisse distinguer deux types de sommets différents. Par exemple, on pourrait construire un graphe où les sommets représentent les utilisateurs d’Amazon, ainsi que les produits vendus sur le site. Dans ce cas, il y a une arête entre un utilisateur et un produit si l’utilisateur a déjà acheté le produit. Il n’y a donc aucun lien possible entre deux utilisateurs ou entre deux produits. Les graphes de ce type sont appelés des graphes bipartis.
🔗
On considère ici un exemple plus simple d’utilisation d’un graphe biparti, pour ensuite en donner la définition.
🔗

Exemple 7.1.31.

On considère une petite compagnie de quatre employés qui travaillent sur un projet quelconque. Pour terminer le projet, les employés doivent accomplir six tâches différentes. De plus, chaque employé est seulement formé à l’accomplissement de certaines tâches.
🔗
On peut représenté la situation à l’aide d’un graphe \(G=(S,A)\text{,}\) où \(S\) est l’ensemble des employés et des tâches à accomplir. Il y aura une arête entre l’employé \(e\) et la tâche \(t\) si \(e\) est formé pour accomplir \(t\text{.}\)
🔗
Figure 7.1.32. Représentation du projet par le graphe \(G\)
🔗
🔗
🔗

Définition 7.1.33. Graphe biparti.

Un graphe \(G=(S,A)\) est appelé un graphe biparti si on peut écrire l’ensemble des sommets \(S\) comme l’union disjointe de deux sous-ensembles \(S_1\) et \(S_2\) telle que chaque arête de \(G\) a une extrémité dans \(S_1\) et une extrémité dans \(S_2\text{.}\)
🔗
Ainsi, \(G\) est biparti si \(S=S_1\cup S_2,\) avec \(S_1\cap S_2=\emptyset\text{,}\) et si pour tout \(a=\{s,t\}\in\,A,\text{,}\) on a que \(s\in\, S_1\) si et seulement si \(t\in\,S_2\text{.}\)
🔗
On dira que \(S_1\) et \(S_2\) sont les parties de \(G\text{.}\)
🔗
🔗

Exemple 7.1.34. Un graphe biparti.

Le graphe cyclique \(C_6\) est un graphe biparti. On peut le voir à l’aide de la représentation de \(C_6\) ci-dessous, en posant \(S_1=\{a,b,e\}\) et \(S_2=\{c,d,f\}\text{.}\)
🔗
Figure 7.1.35. Le graphe \(C_6\)
🔗
🔗
🔗

Exemple 7.1.36. Reconnaître un graphe biparti.

Pour déterminer si un graphe est biparti, on peut choisir aléatoirement un premier sommet \(s\) et décider de mettre \(s\) dans \(S_1\text{.}\)
🔗
Ensuite, on place tout le voisinage de \(s\) dans \(S_2\text{.}\) Pour chacun des sommets ajoutés dans \(S_2\text{,}\) on place leur voisinage dans \(S_1\text{.}\)
🔗
On poursuit cette procédure jusqu’à ce que chaque sommet soit dans un seul des \(S_i\) (et donc que le graphe est biparti), ou jusqu’à ce qu’un sommet soit dans \(S_1\) et \(S_2\) (et donc le graphe n’est pas biparti).
🔗
En procédant ainsi, on peut voir que le graphe \(G\) ci-dessous est biparti, mais pas le graphe \(H\text{.}\)
🔗
(a) Le graphe \(G\) est bipartie
🔗
(b) Le graphe \(H\) n’est pas biparti
🔗
Figure 7.1.37. Deux graphes bipartis?
🔗
🔗
Pour illustrer la procédure utilisée dans l’exemple précédent, on peut colorier les sommets d’un graphe, en s’assurant que tous les sommets qui sont voisins soient d’une couleur différente.
🔗
Un graphe sera alors biparti si et seulement si on peut faire une telle coloration en utilisant deux couleurs. De façon générale, on peut résoudre certains problèmes ou bien différentier certains graphes en déterminant le nombre de couleurs minimal qu’on doit utiliser pour colorier un graphe.
🔗

Définition 7.1.38. Coloration des sommets d’un graphe.

La coloration des sommets d’un graphe consiste à attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets adjacents soient d’une couleur différente.
🔗
Plus formellement, on peut définir une coloration des sommets d’un graphe \(G=(S,A)\) comme une fonction surjective \(f:S\rightarrow C,\) ou \(C\) est un ensemble de couleurs, tel que si \(\{s,t\}\) est une arête de \(G\text{,}\) alors \(f(s)\neq f(t)\text{.}\)
🔗
Finalement, on définit le nombre chromatique du graphe \(G\text{,}\) noté \(\chi(G)\text{,}\) le plus petit nombre de couleurs nécessaire pour colorer les sommets de \(G\text{.}\)
🔗
🔗

Exemple 7.1.39. Une coloration de \(C_6\).

Voici une coloration à deux couleurs de \(C_6\text{.}\)
Figure 7.1.40. Coloration à deux couleurs de \(C_6\)
🔗
🔗

Exemple 7.1.42. Coloration à deux couleurs et graphes bipartis.

En essayant de colorier les graphes de l’exemple 7.1.36 avec un minimum de couleur, on obtient les colorations suivantes.
🔗
(a) Le graphe \(G\) est bipartie
🔗
(b) Le graphe \(H\) n’est pas biparti
🔗
Figure 7.1.43. Deux graphes bipartis? Prise deux.
🔗
On voit donc que \(G\) est biparti, mais pas \(H\text{.}\)
🔗
🔗
Finalement, on définit une nouvelle famille de graphes, les graphes bipartis complets.
🔗

Définition 7.1.44.

Le graphe biparti complet \(K_{m,n}\) est un graphe dont l’ensemble des sommets est séparé en sous-ensembles, \(S_1\) et \(S_2\text{,}\) qui ont respectivement \(m\) et \(n\) sommets. De plus, \(\{s,t\}\) est une arête de \(K_{m,n}\) si et seulement si \(s\in S_1\) et \(t\in S_2\text{.}\)
🔗
🔗
Voici quelques graphes bipartis complets.
🔗

Exemple 7.1.45.

Les graphes \(K_{2,5}\text{,}\) \(K_{3,3}\) et \(K_{3,5}\text{.}\)
🔗
(a) \(K_{2,5}\)
🔗
(b) \(K_{3,3}\)
🔗
(c) \(K_{3,5}\)
🔗
Figure 7.1.46. Graphes bipartis complets
🔗
🔗
🔗
🔗

Sous-section 7.1.5 Constructions d’un graphe à partir d’autres graphes

Un peu comme avec les ensembles, il est possible de former de nouveaux graphes à partir de graphes existants. Tout d’abord, on peut considérer les sous-graphes d’un graphe \(G\text{.}\) Ensuite, on regarde comment on peut transformer un graphe en ajoutant ou en retirant des arêtes d’un graphe. Finalement, on considère l’union de deux graphes.
🔗

Définition 7.1.47.

Soit un graphe \(G=(S,A)\text{,}\) on dira que le graphe \(H=(T,B)\) est un sous-graphe de \(G\) si \(T\subseteq S\) et \(B\subseteq A\text{.}\)
🔗
🔗

Exemple 7.1.48.

Soit le graphe \(G\) ci-dessous, les graphes \(H_1\) et \(H_2\) suivants sont des sous-graphes de \(G\text{.}\)
🔗
(a) \(G\)
🔗
(b) \(H_1\)
🔗
(c) \(H_2\)
🔗
Figure 7.1.49. Un graphe et des sous-graphes
🔗
🔗
🔗
Étant donné un graphe \(G=(S,A)\) et un sous-ensemble de sommets \(T\subseteq S\text{,}\) on aimerait considérer le sous-graphe de \(G\) le plus complet possible formé à partir des sommets de \(T\text{.}\) C’est ce qu’on appelle le sous-graphe de \(G\) induit par \(T\text{.}\)
🔗

Définition 7.1.50.

Soit \(G=(S,A)\) un graphe et soit \(T\subseteq S\text{,}\) le sous-graphe induit par \(T\) est le sous-graphe \(H=(T,B)\text{,}\) où \(B\subseteq A\) et pour \(\{t_1,t_2\}\in A\text{,}\) on a que \(\{t_1,t_2\}\in B\) si et seulement si \(t_1,\ t_2\in T\text{.}\)
🔗
🔗

Exemple 7.1.51.

Soit \(G\) le graphe défini à l’exemple 7.1.48, déterminer le sous-graphe induit par \(T=\{a,b,c,e\}\text{.}\)
🔗
Réponse.
Figure 7.1.52. \(H\)
🔗
🔗
🔗
🔗
On regarde maintenant comment on peut ajouter ou retirer des arêtes d’un graphe.
🔗

Définition 7.1.53.

Soit \(G=(S,A)\) un graphe et \(a\in A\text{,}\) le sous graphe \(G-a\) est le graphe dont les sommets sont \(S\) et les arêtes sont \(A-\{a\}\text{.}\) C’est-à-dire que
\begin{equation*} G-a=(S,A-\{a\})\text{.} \end{equation*}
🔗
🔗

Exemple 7.1.54.

Soit \(G\) le graphe représenté ci-dessous, déterminer \(G-a\text{,}\) où \(a\) est l’arête \(\{s_1,s_4\}\)
🔗
Figure 7.1.55. Le graphe \(G\)
🔗
🔗
Réponse.
Figure 7.1.56. Le graphe \(G-a\)
🔗
🔗
🔗
🔗

Définition 7.1.57.

Soit \(G=(S,A)\) un graphe et \(a = \{s,t\}\text{,}\) où \(s\) et \(t\) sont des sommets de \(G\text{,}\) le graphe \(G+a\) est le graphe dont les sommets sont \(S\) et les arêtes sont \(A \cup \{a\}\text{.}\) C’est-à-dire que
\begin{equation*} G+a=(S,A\cup \{a\})\text{.} \end{equation*}
🔗
🔗

Exemple 7.1.58.

Soit \(G\) le graphe défini à l’exemple 7.1.54, déterminer \(G+a\text{,}\) où \(a\) est l’arête \(\{s_1,s_2\}\text{.}\)
🔗
Réponse.
Figure 7.1.59. Le graphe \(G+a\)
🔗
🔗
🔗
🔗

Définition 7.1.60.

L’union des graphes \(G_1=(S_1,A_1)\) et \(G_2=(S_2,A_2)\text{,}\) qu’on note \(G_1\cup G_2\text{,}\) est le graphe de sommets \(S_1\cup S_2\) et d’arêtes \(A_1\cup A_2\text{.}\)
🔗
🔗

Exemple 7.1.61.

Soit \(G\) et \(H\) les graphes représentés ci-dessous, déterminer \(G\cup H\text{.}\)
🔗
(a) \(G\)
🔗
(b) \(H\)
🔗
Figure 7.1.62. Deux graphes
🔗
🔗
Réponse.
Figure 7.1.63. \(G\)
🔗
🔗
🔗
🔗
🔗
Les points importants de cette section sont:
🔗

Exercices 7.1.6 Exercices

À faire en classe

Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
🔗
1.
Pour chacun des graphes ci-dessous, déterminer le degré de chaque sommet et calculer la somme des degrés de tous les sommets.
🔗
(a)
Figure 7.1.64. Le graphe \(G_1\)
🔗
🔗
Réponse.
Table 7.1.65. Degré des sommets de \(G_1\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(2\)
\(b\) \(2\)
\(c\) \(2\)
\(d\) \(2\)
\(e\) \(2\)
\(f\) \(2\)
Somme \(12\)
🔗
🔗
(b)
Figure 7.1.66. Le graphe \(G_2\)
🔗
🔗
Réponse.
Table 7.1.67. Degré des sommets de \(G_2\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(4\)
\(b\) \(3\)
\(c\) \(3\)
\(d\) \(4\)
\(e\) \(3\)
\(f\) \(3\)
\(g\) \(2\)
Somme \(22\)
🔗
🔗
(c)
Figure 7.1.68. Le graphe \(G_3\)
🔗
🔗
Réponse.
Table 7.1.69. Degré des sommets de \(G_3\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(3\)
\(b\) \(4\)
\(c\) \(3\)
\(d\) \(4\)
\(e\) \(3\)
\(f\) \(5\)
Somme \(22\)
🔗
🔗
(d)
Figure 7.1.70. Le graphe \(G_4\)
🔗
🔗
Réponse.
Table 7.1.71. Degré des sommets de \(G_4\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(3\)
\(b\) \(3\)
\(c\) \(4\)
\(d\) \(4\)
\(e\) \(2\)
Somme \(16\)
🔗
🔗
(e)
Figure 7.1.72. Le graphe \(G_5\)
🔗
🔗
Réponse.
Table 7.1.73. Degré des sommets de \(G_5\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(1\)
\(b\) \(3\)
\(c\) \(2\)
\(d\) \(2\)
Somme \(8\)
🔗
🔗
(f)
Figure 7.1.74. Le graphe \(G_6\)
🔗
🔗
Réponse.
Table 7.1.75. Degré des sommets de \(G_6\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(3\)
\(b\) \(3\)
\(c\) \(3\)
\(d\) \(3\)
\(e\) \(4\)
Somme \(16\)
🔗
🔗
(g)
Figure 7.1.76. Le graphe \(G_7\)
🔗
🔗
Réponse.
Table 7.1.77. Degré des sommets de \(G_7\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(a\) \(3\)
\(b\) \(2\)
\(c\) \(3\)
\(d\) \(3\)
\(e\) \(1\)
\(f\) \(1\)
\(g\) \(1\)
Somme \(14\)
🔗
🔗
(h)
Figure 7.1.78. Le graphe \(G_8\)
🔗
🔗
Réponse.
Le degré de chacun des sommets de \(G_8\) est \(2\text{.}\) Puisque \(G_8\) possède \(6\) sommets, on a que la somme des degrés de chaque sommet est \(12\text{.}\)
🔗
🔗
🔗
(i)
Figure 7.1.79. Le graphe \(G_9\)
🔗
🔗
Réponse.
Table 7.1.80. Degré des sommets de \(G_9\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(s_1\) \(3\)
\(s_2\) \(2\)
\(s_3\) \(3\)
\(s_4\) \(2\)
\(s_5\) \(2\)
Somme \(12\)
🔗
🔗
(j)
Figure 7.1.81. Le graphe \(G_{10}\)
🔗
🔗
Réponse.
Table 7.1.82. Degré des sommets de \(G_9\)
🔗
Sommet \(s\) degré \(\deg(s)\)
\(t_1\) \(3\)
\(t_2\) \(2\)
\(t_3\) \(2\)
\(t_4\) \(3\)
\(t_5\) \(2\)
Somme \(12\)
🔗
🔗
🔗
2.
Dans les prochaines sections, nous verrons la notion d’isomorphismes de graphes. Intuitivement, deux graphes sont isomorphes s’ils représentent essentiellement le même graphe, mais sous une forme différente.
🔗
Parmi les graphes de l’exercice 7.1.6.1, est-ce qu’un certaine paire semble être isomorphe? Donner une justification intuitive.
🔗
Réponse.
Intuitivement, on peut se convaincre que les graphes \(G_8\) et \(G_1\) sont essentiellement les mêmes graphes.
🔗
Aussi, les graphes \(G_9\) et \(G_{10}\) sont essentiellement les mêmes.
🔗
🔗
🔗
3.
On définit \(\tilde{Q}_n=(S_n,A_n)\) de la façon suivante.
🔗
L’ensemble \(S_n\) des sommets de \(\tilde{Q}_n\) est l’ensemble des chaînes binaires de longueur \(n\text{.}\)
🔗
Ensuite, l’ensemble des arêtes est l’ensemble \(A_n\) tel que pour deux sommets \(s\) et \(t\text{,}\) alors \(\{s,t\}\in\,A_n\) si et seulement si on peut obtenir la chaîne binaire \(s\) à partir de la chaîne \(t\) en changeant un \(0\) par un \(1,\) ou vise-versa.
🔗
Par exemple, dans \(\tilde{Q}_5\text{,}\) il y a une arête entre les sommets \(00011\) et \(10011\text{,}\) mais pas entre les sommets \(00011\) et \(11011\text{.}\)
🔗
(a)
Tracer \(\tilde{Q}_n\) pour \(1\leq n \leq 3\text{.}\)
🔗
Réponse.
À l’aide de Sage, on peut tracer ces graphes
🔗
🔗
🔗
(b)
À quel graphe est-ce que \(\tilde{Q}_n\) fait penser parmi les graphes définis dans la section 7.1.3 ?
🔗
🔗
🔗
4.
Soit \(A_1\text{,}\) \(A_2\text{,}\) \(\dots\text{,}\) \(A_n\) une collection d’ensembles. Le graphe d’intersection de ces ensembles est le graphe dont les sommets sont les ensembles \(A_i\text{,}\) et il y a une arête entre deux ensembles différents \(A_i\) et \(A_j\) si et seulement si \(A_i\cap A_j \neq \emptyset\text{.}\) Tracer le graphe d’intersection des ensembles ci-dessous.
🔗
(a)
\(A_1=\{0,2,4,6,8\}\text{,}\) \(A_2=\{0,1,2,3,4\}\text{,}\) \(A_3=\{1,3,5,7,9\}\text{,}\) \(A_4=\{5,6,7,8,9\}\) et \(A_5=\{0,1,8,9\}\text{.}\)
🔗
🔗
(b)
\begin{equation*} A_1=\{\dots,-4,-3,-2,-1,0\}\text{,} \end{equation*}
\begin{equation*} A_2=\{\dots ,-2,-1,0,1,2,\dots\}\text{,} \end{equation*}
\begin{equation*} A_3=\{\dots,-6,-4,-2,0,2,4,6,\dots\}\text{,} \end{equation*}
\begin{equation*} A_4=\{\dots,-5,-3,-1,1,3,5,\dots \}\text{,} \end{equation*}
\begin{equation*} A_5=\{\dots,-6,-3,0,3,6,\dots \}\text{.} \end{equation*}
🔗
🔗
🔗
5.
Pour quelles valeurs de \(n\) est-ce que les graphes \(C_n\) sont bipartis.
🔗
Réponse.
Le graphe cyclique \(C_n\) est biparti si et seulement si \(n\) est pair.
🔗
🔗
Solution.
On note les sommets et les arêtes de \(C_n\) comme dans la définition 7.1.22.
🔗
Si \(n\) est pair, on veut montrer que \(C_n=(S,A)\) est biparti. On pose alors \(S_1=\{s_i ~|~ i \equiv 1 \mod 2\}\) et \(S_2=\{s_i ~|~ i \equiv 0 \mod 2\}\text{.}\) Les arêtes de \(C_n\) sont soit de la forme \(\{s_i, s_{i+1}\}\) pour \(i=1, 2, \dots n-1\text{,}\) ou bien \(\{s_n, s_1\}\text{.}\) Dans le premier cas, \(s_i \in S_1\) si et seulement si \(s_{i+1}\text{,}\) car \(i\equiv 1 \mod 2\) si et seulement si \(i+1\equiv 0 \mod 2\text{.}\) Dans le deuxième cas, on a bien que \(s_1\in S_1\text{,}\) alors qu \(s_n\in S_2,\) car \(n\) est pair. On a bien montré que \(C_n\) est biparti, puisqu’on a montré que pour \(\{s_i,s_j\}\in A\text{,}\) alors \(s_i\in S_1\) si et seulement si \(s_j\in S_2\text{.}\)
🔗
Supposons maintenant \(C_n\) soit biparti. On veut montrer que \(n\) est pair. Supposons que \(n\) soit impair, et cherchons une contradiction.
🔗
Puisque \(C_n\) est biparti, on peut écrire \(S=S_1\cup S_2\) de sorte que pour \(\{s_i, s_j\}\in A\text{,}\) alors \(s_i\in S_1\) si et seulement si \(s_j\in S_2\text{.}\) Sans perdre de généralité, on peut supposer que \(s_1\in S_1\text{.}\) Ainsi, \(s_2\in S_2, s_3\in S_1, s_4\in S_2\) et ainsi de suite. On remarque alors que \(s_{1+i}\in S_1\) si \(i\) est pair, alors que \(s_{1+i} \in S_2\) si \(i\) est impair. Autrement dit, si \(k\in N\text{,}\) alors \(s_{2k+1}\in S_1\) et \(s_{2k}\in S_2\text{.}\) Cependant, on sait que \(n\) est impair, c’est-à-dire que \(s_{n}=s_{2k+1}\in S_1\text{.}\) Ceci est une contradiction, car on sait également que \(s_1\) est voisin à \(s_n\text{,}\) ce qui contredit le fait que \(C_n\) soit biparti. L’entier \(n\) doit donc être pair.
🔗
🔗
🔗
6.
Est-ce que les graphes ci-dessous sont bipartis? Si oui, justifier.
🔗
(a)
Figure 7.1.83. \(G\)
🔗
Réponse.
Oui.
🔗
🔗
Solution.
On utilise la coloration \(f:S\rightarrow \{vert,bleu\}\) définie par \(f(a)=f(b)=f(c)=f(d)=vert\) alors que \(f(e)=bleu\text{.}\) On a alors
🔗
Figure 7.1.84. \(G\)
🔗
🔗
🔗
(b)
Figure 7.1.85. \(G\)
🔗
🔗
Réponse.
Non, ce graphe n’est pas biparti.
🔗
🔗
Solution.
Si on tente de colorer les sommets du graphe à l’aide d’un minimum de couleurs, on doit nécessairement utiliser trois couleurs pour y arriver. On obtient par exemple la coloration ci-dessous.
🔗
Figure 7.1.86. \(G\)
🔗
🔗
🔗
🔗
🔗
7.
Combien existe-t-il de sous-graphes de \(K_3\text{?}\)
🔗
🔗
🔗

Exercices supplémentaires

9.
Montrer par récurrence que le graphe \(K_n\) possèdent \(\frac{n^2-n}{2}\) arêtes, pour \(n\in \N^\ast\)
🔗
🔗
10.
Démonter que si \(G\) est un graphe biparti avec \(v\) sommets et \(e\) arêtes, alors \(e\leq \frac{v^2}{4}\)
🔗
🔗
11.
Soit \(G=(S,A)\) un graphe simple, on défini le graphe complémentaire à \(G\text{,}\) qu’on note \(\overline{G}\text{,}\) comme étant le graphe ayant les mêmes sommets que \(G\text{,}\) et où deux sommets sont adjacents dans \(\overline{G}\) si et seulement si ils ne le sont pas dans \(G\text{.}\) Représenter ou décrire les graphes ci-dessous.
🔗
(e)
\(\overline{K_n}\text{,}\) où \(n\in \N^\ast\) est quelconque.
🔗
🔗
(f)
\(\overline{K_{m,n}}\text{,}\) où \(m,n\in \N^\ast\) sont quelconques.
🔗
🔗
🔗
12.
Si \(G\) est un graphe simple avec \(15\) arêtes et \(\overline{G}\) a \(13\) arêtes, combien de sommets y a-t-il dans \(G\text{?}\)
🔗
🔗
13.
Si \(G\) est un graphe simple avec \(e\) arêtes et \(v\) sommets, combien y a-t-il d’arêtes dans le graphe \(\overline{G}\text{?}\)
🔗
🔗
14.
Démontrer que si \(G\) est un graphe simple avec \(n\) sommets, alors \(G\cup \overline{G}\) est le graphe \(K_n\text{.}\)
🔗
🔗
15.
On dit que le graphe \(G\) est régulier si tous ses sommets ont le même degré. Pour quelles valeurs de \(m\) et \(n\) les graphes suivants sont-ils réguliers?
🔗
🔗
🔗
🔗
🔗
PrécédentTopSuivant