Home
About

Graphes biparti

Cours/Théorie des graphes/Graphes biparti

Les graphes biparti font parti de ces classes de graphes assez généraux pour être présent partout et assez spécifique pour que tous se passe bien (les principaux problèmes NP-complets dans le cas général deviennent polynomiaux voir triviaux).

C'est une classe de graphe importante à connaître car, parfois curieusement, ils apparaissent dans nombre de problèmes de graphes. Parfois comme sous-cas facilement solvable, parfois comme fondement d'une preuve. Nous allons voir quelques définitions et caractérisation des graphes bi-parti ainsi que quelques exercices classiques (et élégants).

Définitions

Bi-parti

Définition

Un graphe $G=(V, E)$ est biparti s'il existe une bipartition $V_1$ et $V_2$ de $V$ ($V_1 \cap V_2 = \varnothing$ et $V_1 \cup V_2 = V$) en deux stables.

Par exemple le graphe suivant :

exemple biparti

Les graphes bipartis sont une famille héréditaire, il est en effet clair que :

Proposition

Tous sous-graphe d'un graphe biparti est biparti.

On a déjà vu ce genre de graphe sans le savoir lors de l'étude du transport amoureux : le problème du mariage entre 2 populations distinctes se modélise comme un graphe bi-parti où chaque population est un stable.

Montrez que si un graphe bi-parti est connexe, sa bi-partition en deux stables est unique.

solution

Si le graphe est connexe, on peut parcourir celui-ci (en largeur ou en profondeur) à partir d'une racine pour créer un arbre planté.

Chaque élément sera forcément dans le stable différent de son parent : l'affectation de chaque élément dépend uniquement de l'affectation de la racine.

La propriété précédente n'est bien sur plus vraie si le graphe n'est pas connexe :

Montrez que le graphe discret (sans arêtes) à $n$ sommets possède $2^{n-1}-1$ bi-partitions possibles.

solution 1

Par récurrence. Un graphe discret à 2 sommets possède bien $2^{2-1}-1 = 1$ bipartition.

On suppose la propriété vrai pour les ensembles à $n$ éléments et soit le graphe discret $G=(V, \varnothing)$ à $n+1$ sommets et soit $x$ un de ces éléments. Pour toute les bipartitions $x$ est dans une des deux partitions et, à part celle où $x$ est tout seul dans une classes, si on supprime $x$ on a une bipartition d'un ensemble à $n$ éléments : une bipartition à $n+1$ élément est donc soit :

  • $\{\{x\}, V\backslash \{x\}\}$
  • $\{U\cup \{x\}, V\}$ ou $\{U, V\cup \{x\}\}$ avec $\{U, V\}$ une bipartition de $V\backslash \{x\}$

Il y a donc $2\cdot (2^{n-1}-1) + 1 = 2^n-1$ bipartitions à $n+1$ éléments (il y en a $2^{n-1}-1$ pour un ensemble à $n$ éléments par hypothèse de récurrence), ce qui conclut la preuve.

solution 2

TBD plus simple :

mot binaire/complémentaire = 2^n/2 mais on supprime 0000/11111 car pas bi-partition.

Le nombre de partitions d'un ensemble à $n$ éléments en $k$ sous-ensembles est appelé nombre de Stirling de second espèce

En conclure :

Montrez qu'un graphe biparti à $p$ composantes connexes possède $2^{p-1}$ bipartitions possibles.

solution

Soient $\{X_i, Y_i\}$, $1\leq i \leq p$, les $p$ bipartitions associées au stables des $p$ composantes connexes de $G$. Un des deux stables de $G$ sera alors :

  • soit l'union de tous les $X_i$
  • soit une partie des $X_i$, ce qui correspond à ue bipartition des $X_i$, $1\leq i \leq p$.

Il y a donc autant de de façon de faire que de bipartition à $p$ élément plus 1.

Terminons cette série d'exercices par une propriété sur la cardinalité :

Soit $G$ un graphe biparti tel que $\delta(x) = k > 0$ pour tout sommet $x$. Montrez que les deux stables ont même cardinal.

solution

Soient $U$ et $V$ une bipartition en deux stables de $G$. On a : $\sum_{u\in U} \delta(u) = \sum_{v\in V} \delta(v)$

Or $\sum_{u\in U} \delta(u) = k\cdot \vert U\vert$ et $\sum_{v\in V} \delta(u) = k\cdot \vert V\vert$ ce qui conclue la preuve.

Biparti complets

Définition

Un graphe biparti complet est le graphe $K_{p,q} = (V_p \cup V_q, V_p \times V_q)$, avec $\vert V_p \vert = p$ et $\vert V_q \vert = q$

Le graphe $K_{2, 3}$ est par exemple :

$K_{2, 3}$

Les graphes bipartis complets sont aussi parfois appelé une biclique

On retrouve les graphes bi-partis complets dans plein de champs de la théorie des graphes car ils ont plein de chouettes propriétés. Par exemple :

Montrez que si un graphe biparti est hamiltonien, alors la taille des 2 stables est identique.

solution

Si le graphe biparti admet un cycle hamiltonien il est connexe et donc n'admet qu'un 2 stables. Soit $x_1x_2\dots x_nx_1$ un cycle hamiltonien. Comme un graphe biparti ne peut avoir de cycle de longueur impaire $n$ est forcément paire.

On conclue la preuve en remarquant que les $x_i$ paires et les $x_i$ impairs sont forcément dans des stables différents.

Déduire de l'exercice précédent qu'un graphe bipartis complets $K_{p, q}$ est hamiltonien si et seulement si $p=q \geq 1$.

solution

Si le graphe biparti complet $K_{p, p}$ est composé des stables $\{x_1,\dots x_n\}$ et $\{y_1,\dots y_n\}$, le cycle $x_1y_1\dots x_iy_i\dots x_ny_nx_1$ est hamiltonien : tous les graphes $K_{p, p}$ sont hamiltoniens.

Graphes $k$-partis

On en a parfois besoin, donc autant les définir ici :

Définition

On appelle graphe $k$-parti tout graphe admettant une partition de ses sommets en $k$ stables.

Définition

On appelle graphe $k$-parti complet le graphe Le graphe $K_{p_1,\dots, p_k} = (\cup_{i} V_{p_i}, \{uv \vert u\in V_{p_i}, v\in V_{p_j}, i\neq j\})$

Pour voir quelques graphes tri-partis complets, vous pouvez jeter un coup d'œil à la page suivante :

https://mathworld.wolfram.com/CompleteTripartiteGraph.html

Terminons par un petit exercice pour appliquer tout ça :

Trouver toutes les valeurs entières de a, b, c telles que $0 < a ≤ b ≤ c$ et que le graphe 3-parti complet $K_{a,b,c}$ possède :

solution

Soient $A$, $B$ et $C$ les 3 stables tels que $\vert A\vert = a$, $\vert B\vert = b$ et $\vert C\vert = c$. On a :

  • les a sommets de $A$ ont pour degré $b+c$,
  • les b sommets de $B$ ont pour degré $a+c$,
  • les c sommets de $C$ ont pour degré $a+b$.

Pour que le graphe admette un cycle eulérien, il faut que tout sommet soit de degré pair, ce qui n'est possible que si $a$, $b$ et $c$ sont soit tous pair soit tous impairs.

Pour que le graphe admette un chemin eulérien, il faut que tous les sommets soient de degré paires sauf 2. Comme tous les sommets d'un même stable ont même degré, on a deux cas : soit $a=b=1$ et $c$ pair, soit $a=2$ et il faut alors que :

  • $b+c$ soit impair,
  • $2+c$ soit pair,
  • $2+b$ soit pair.

Ce qui est impossible.

Les seuls graphes tripartis complets admettant un chemin eulériens sont donc les graphes $K_{1,1,2p}$

Reconnaissance

Savoir si un graphe est biparti est "facile" en utilisant un algorithme de marquage qui associe une couleur à chaque sommet.

On considère que le graphe est connexe dans l'algorithme suivant. S'il ne l'est pas on le relance sur chacune des parties connexes.

On retrouve un algorithme de marquage puis examen de sommets, comme l'algorithme de recherche de chaîne augmentante de Ford et Fulkerson. Ce principe général permet de résoudre efficacement beaucoup de problèmes en théorie des graphes.

Initialisation :

    On possède deux couleurs.
    Soit x un sommet du graphe que l'on marque avec une couleur

Boucle principale :

    tant qu'il existe x, un sommet marqué non examiné:

        examiner x
        pour chaque voisin y de x :
            si y est marqué avec la couleur de x:
                FIN : le graphe n'est pas biparti
            sinon si y n'est pas marqué:
                marquer y avec la couleur différente de celle de x
    
    FIN : le graphe est biparti et la couleur des sommets determine les 2 stables

TBD à écrire propre

  1. on voit bien tous les sommets car connexe : on le fait par récurrence sur la longueur du chemin entre $x$ et $y$
  2. chaque couleur est obligatoire
  3. linéaire n+m si on utilise un parcours en profondeur (les éléments marqués sont dans une pile).

L'algorithme fonctionne clairement si le graphe est bi-parti puisque par composante connexe il n'y a qu'une seule possibilité de bi-partition une fois 1 élément assigné :

Proposition

Si le graphe est bi-parti, alors l'algorithme s'arrête en donnant une bipartition du graphe

La réciproque est également vraie :

Proposition

Si l'algorithme donne une bipartition, le graphe est bi-parti.

preuve

Si le graphe est connexe, chaque sommet sera marqué et examiné. Comme les couleurs ne sont jamais remise en cause et que l'on vérifie tous les voisins d'un sommet examiné on explorera toutes les arêtes du graphes et les sommets chacune d'elles seront de couleurs différentes.

Si l'algorithme s'arrête en répondant NON, c'est qu'il existe un voisin $y$ du sommet examiné $x$ marqué avec la même couleur. Il existe donc un chemin entre le premier élément marqué de l'algorithme, disons $x_0$, et $x$ alternant de couleur en couleur :

reconnaissance fail

Si $y$ est marqué c'est qu'on la déjà vu, disons en examinant le sommet $x' \neq x$. Il existe donc aussi un chemin alternant de couleurs entre $x_0$ et $x'$ qui est de couleur différente de $x$ :

reconnaissance fail

On se trouve donc globalement dans une situation où il existe un chemin alternant les couleurs entre $x_0$ et un chemin alternant les couleurs entre $x$ et entre $x_0$ et $x'$. Ces deux chemins sont de parité différente puisque $x$ et $x'$ sont de couleurs différentes :

reconnaissance fail

En remontant ces deux chemins jusqu'au premier élément en commun (il existe puisque $x_0$ fait parti des deux chemins) on obtiendra alors forcément un cycle de longueur impaire :

reconnaissance fail

On en conclut :

Proposition

Si l'algorithme s'arrête en répondant NON, alors le graphe possède un cycle de longueur impair.

Corollaire

Si un graphe n'est pas bi-parti, alors il existe un cycle de longueur impair.

Caractérisation

Notre algorithme nous donne quasiment sans rien faire une caractérisation des graphes bi-parti :

Proposition

Un graphe est biparti si et seulement si il ne contient pas de cycle de longueur impaire.

preuve
  • Si un graphe est biparti alors il ne contient pas de cycle de longueur impaire puisque les arêtes d'un cycle doivent passer d'un stable à l'autre un nombre pair de fois.
  • Si un graphe n'est pas biparti alors l'algorithme de reconnaissance va répondre NON, ce qui implique l'existence d'un cycle de longueur impaire.

On le verra tout au long de ce cours l'existence de cycles de longueurs impairs pose de nombreux problèmes algorithmiques. Se restreindre aux graphes bi=parti va souvent accélérer et rendre optimal des algorithmes autrement plus compliqués sinon.

Partition en graphes Biparti

Le problème de partition d'un graphe en graphes bipartis est un problème de communication réseau initialement posé (et résolu) par les deux chercheurs Graham et Pollak des laboratoires Bell dans les années 1970.

Problème de Graham-Pollak

Des ordinateurs liés entre eux deux à deux par un graphe complet doivent tous communiquer entre eux. La contrainte est que chaque ordinateur ne peut être que dans 3 états :

Si à un instant donné un note les arêtes en communication de ce graphe, elles formeront un graphe bi parti puisque l'on pourra séparer les ordinateurs en émission (qui peuvent envoyer des donnés à plus d'un ordinateur) et les ordinateurs en réception qui peuvent recevoir des données de plus d'un ordinateur.

Si chaque couple d'ordinateur doit s'échanger exactement une donnée (en émission ou en réception). Combien d'étapes au minimum sont-elles nécessaires pour tout couple d'ordinateurs aient communiqué (que chaque arête du graphe ait été utilisée 1 fois) ?

Ce problème peux se décrire comme un problème de graphe. Commençons par définir une partition d'un graphe.

Définition

Une partition d'un graphe $G=(V, E)$ est une suite $G_i=(V, E_i)$, avec $1\leq i \leq m$ telle que :

  • $\cup_{1\leq i \leq m} E_i = E$
  • $E_i \cap E_j = \varnothing$ pour tout $1\leq i \neq j \leq m$

La définition explicite le fait que l'on partitionne l'ensemble des arêtes d'un graphe. On spécifie souvent la famille de graphe à laquelle la partition doit appartenir (pour nous des graphes bipartis) et comme tout graphe à $n$ sommet est inclut dans $K_n$ la clique à $n$ sommet, c'est lui que l'on va chercher à partitionner.

Notre problème de partition est :

Définition

Combien faut-il au minimum de graphes bipartis (complets) pour partitionner $K_n$ ?

Comme il faut minimiser le nombre d'éléments de la partition et que chaque arête du graphe complet doit être utilisé, les graphes bi-partis sont forcément complets.

Remarquons tout de suite que ce problème admet une solution, il en faut moins de $n(n-1)/2$ puisque les graphes G_{i,j} = (\{i, j\}, \{ij\})$ sont tous bipartis.

On peut bien sur faire mieux, comme le montre l'exemple suivant qui partitionne $K_6$ en 6 graphes bi-partis complets :

exemple biparti

Vous avez peut-être remarqué, mais la partition ci-dessus n'est pas minimale, on peut faire mieux grace aux étoiles :

Définition

Une étoile est un graphe $G = (V, E)$ tel qu'il existe $x\in V$ avec $E = \{xy | y \in V\backslash \{x\}\}$

On peut toujours décomposer $K_n$ en $n-1$ étoiles $G_i = (V_i, E_i)$ avec $1\leq i < n$ :

Le partitionnement en étoile n'est pas unique, par exemple avec $K_6$ :

exemple biparti min

En revanche, $n-1$ est bien le minimum :

Proposition

On ne peut décomposer $K_n$ en moins de $n-1$ graphes bipartis complets.

preuve

La preuve est atypique et ne parlera pas de graphes. De plus, on ne connaît pas de preuve combinatoire. J'ai repris la preuve de Proofs from the book (chapitre 11, théorème 4 de la sixième édition) qui comme chacune des preuves du livre est extrêmement élégante.

Soit $K_n$ le graphe complet avec comme ensemble de sommets $V = \{1, \dots, n\}$. Soit $(B_k)_{1\leq k \leq m}$ une de ses décompositions en en $m$ graphes bipartis complets, et on note également $\{U_k, V_k\}$ les deux stables de $B_k$.

Soient $x_1, \dots, x_n$, $n$ variables réelles. On considère alors Le système d'équations linéaires formé des $m+1$ équations suivantes :

  • $\sum_{1\leq i \leq n}x_i = 0$
  • $\sum_{i \in U_k}x_i = 0$ pour tout $1\leq k \leq m$

Si $m + 1 < n$ ce système va posséder une solution non nulle $(c_1, \dots, c_n)$ (il existe $i$ tel que $c_i \neq 0$). Nous allons montrer que ceci est impossible.

Comme pour tout $i \neq j$, il n'existe qu'un unique $k$ tel que $x_i \in U_k$ et $x_j \in V_k$, on a l'égalité :

$$ \begin{array}{lcl} \sum\limits_{i < j}x_ix_j &=& \sum\limits_{1\leq k \leq m}(\sum\limits_{(i, j) \in U_k\times V_k} x_i \cdot x_j)\\ &=& \sum\limits_{1\leq k \leq m}(\sum\limits_{i \in U_k} (x_i \cdot (\sum\limits_{j \in V_k} x_j))\\ &=& \sum\limits_{1\leq k \leq m}((\sum\limits_{i \in U_k} x_i)\cdot (\sum\limits_{j \in V_k} x_j)) \end{array} $$

Comme $\sum_{1\leq i\leq n}c_i = 0$ on a aussi :

$$ \begin{array}{lcl} 0 &=& (\sum\limits_{1\leq i\leq n}c_i)^2\\ &=&\sum\limits_{1\leq i\leq n}c_i^2 + \sum\limits_{i < j}c_ic_j\\ &=&\sum\limits_{1\leq i\leq n}c_i^2 + \sum\limits_{1\leq k \leq m}((\sum\limits_{i \in U_k} c_i)\cdot (\sum\limits_{j \in V_k} c_j))\\ \end{array} $$

Or $\sum_{i \in U_k}c_i = 0$ pour tout $1\leq k \leq m$, ce qui implique :

$$ \begin{array}{lcl} 0 &=& \sum\limits_{1\leq i\leq n}c_i^2\\ \end{array} $$

Ce qui n'est possible que si $c_i = 0$ pour tout $1\leq i \leq n$ : contradiction. Notre hypothèse était donc fausse, on a $m + 1 = n$.

Sous-graphes bi-partis

Nous allons montrer des encadrements sur les graphe possédant, ou pas, des sous-graphes bi-partis.

Sous-graphe bi-parti inclus

Le grand retour de la méthode probabiliste pour résoudre un problème à priori très compliqué.

Proposition

Dans tout graphe $G=(V, E)$ à $m$ arêtes, il existe un sous-graphe bi-parti $G'$ à au moins $\frac{m}{2}$ arêtes.

preuve

On va associer à chaque sommet du graphe $G$ une couleur parmi 2 choix possibles (disons rouge et noir) de façon uniforme et indépendante.

On considère ensuite le sous-graphe couvrant $G'$ où l'on a supprimé de graphe toutes les arêtes dont les sommets de sont de couleurs différentes. La probabilité pour une arête $xy$ d'être dans $G'$ est $\frac{1}{2}$. Il y a en effet 4 possibilité pour chaque arêtes, chacune de probabilité $\frac{1}{4}$ :

  • soit $x$ et $y$ sont rouges
  • soit $x$ est rouge et $y$ est noir
  • soit $x$ est noir et $y$ est rouge
  • soit $x$ et $y$ sont noires

De là, en notant $\mathcal{G}'$ l'ensemble de tout ces sous-graphes possibles, l'espérance du nombre d'arêtes dans $G'$ est :

$$ \begin{array}{lcl} \mathbb{E}(E') &=& \frac{1}{\vert \mathcal{G}' \vert}\sum_{G'=(V, E') \in \mathcal{G}'}\vert E'\vert\\ & =& \frac{1}{\vert \mathcal{G}' \vert}\sum_{xy \in E} \vert \{G' \vert G'=(V, E') \in \mathcal{G}', xy \in E' \}\vert\\ & = &\frac{\sum_{xy \in E} \vert \{G' \vert G'=(V, E') \in \mathcal{G}', xy \in E' \}\vert}{\vert \mathcal{G}' \vert} \\ &= &\sum_{xy \in E}{\text{probabilité que } xy \text{ soit une arête}}\\ &= &\sum_{xy \in E}{\text{probabilité que les deux sommets de } xy \text{ soient de même couleur}}\\ &= &\sum_{xy \in E}\frac{1}{2}\\ &= &\frac{m}{2}\\ \end{array} $$

On termine la preuve en remarquant que si le nombre moyen d'arête est $\frac{m}{2}$, il est indispensable qu'il existe au moins un sous-graphe $G^\star$ de $G$ l'atteignant.

Notez comment la preuve est élégante ! C'est souvent le cas lorsque l'on utilise la méthode probabiliste. Cependant, ces preuves sont non constructives et dans notre cas trouver ce graphe bi-parti, ou tout du moins le plus grand n'est pas facile du tout. C'est en effet un effet un problème algorithmique classique :

Problème

  • nom : MAX-CUT
  • Entrée :
    • un graphe
    • un entier $K$
  • Question : le graphe contient-il une bipartition $V_1$ et $V_2$ de ses sommets tels que $\vert \{xy \vert xy \in V(G), x \in V_1, y in V_2 \} \geq K$ ?

Une coupe dans un graphe est soit une bi-partition de ses sommets, soit l'ensemble des arêtes dont les extrémités sont dans des classes différentes.

Qui est NP-complet :

Proposition

Le problème MAX-CUT est NP-complet.

preuve

On montre que STABLE ≤ MAX-cut

Soit $(G, K)$ une instance du problème stable. On construit une instance de MAX-CUT en construisant le graphe $G'=(V', E')$ tel que :

  • $V' = V(G) \cup \{x \} \cup (\cup_{e\in E(G)} \{ e_u, e_v \})$
  • $E' = (\cup_{u\in V(G)} \{xu \}) \cup (\cup_{uv\in E(G)} \{ u_{uv}v_{uv}, uu_{uv}, vv_{uv}, xu_{uv}, xv_{uv} \})$

La figure ci-dessous montre un graphe $G$ (à gauche) instance de STABLE et le graphe $G'$ associé (à droite), instance de MAX-CUT :

le graphe $G'$

Montrons la réduction.

Si $G$ admet un stable $I$ de taille $K$, on construit l'ensemble $I'$ de sommets de $G'$ contenant $I$ et tous les sommets $uv_u$ tel que que $v \in I$ (resp. $uv_v$ tel que que $u \in I$). Notez que pour toute arête $uv$ de $G$ :

  1. comme $I$ est un stable ($u$ et $v$ ne peuvent être dans $I$ si $uv \in E(G)$), au moins un des deux sommets $uv_u$ ou $uv_v$ est dans $I'$.
  2. si $uv_u$ est dans $I'$ mais pas $uv_v$, la bipartition $(I', V'\backslash \{ I' \})$ coupe 4 des 5 arêtes $\{u_{uv}v_{uv}, uu_{uv}, vv_{uv}, xu_{uv}, xv_{uv} \}$
  3. si $uv_u$ et $uv_v$ sont dans $I'$, la bipartition $(I', V'\backslash \{ I' \})$ coupe 4 des 5 arêtes $\{u_{uv}v_{uv}, uu_{uv}, vv_{uv}, xu_{uv}, xv_{uv} \}$

Au final si $I$ est un stable de taille $K$ pour $G$, alors $(I', V'\backslash \{ I' \})$ est une coupe de taille $K + 4\cdot e(G)$ pour $G'$.

Réciproquement soit $(I', V'\backslash \{ I' \})$ une coupe de taille $K' \geq K + 4\cdot e(G)$ pour $G'$. On peut supposer sans perte de généralité que $x\notin I'$ (sinon on échange les deux ensemble formant la bipartition) et on considère $I = I' \cap V(G)$.

Soit $F$ l'ensemble des arêtes $uv$ de $G$ telles que $u$ et $v$ soient dans $I$. On a que :

  • si $uv \in F$, la bipartition $(I', V'\backslash \{ I' \})$ ne peut couper au maximum que 3 des 5 arêtes $\{u_{uv}v_{uv}, uu_{uv}, vv_{uv}, xu_{uv}, xv_{uv} \}$,
  • si $uv \in E(G) \backslash F$, la bipartition $(I', V'\backslash \{ I' \})$ ne peut couper au maximum que 4 des 5 arêtes $\{u_{uv}v_{uv}, uu_{uv}, vv_{uv}, xu_{uv}, xv_{uv} \}$

On en déduit que $K' \leq \vert I\vert + 3 \cdot \vert F\vert + 4 \cdot (e(G) - \vert F \vert) = \vert I\vert + 4 \cdot e(G) - \vert F \vert$. Comme $K + 4 \cdot e(G) \leq K'$ on a $\vert I\vert \geq K + \vert F \vert$ et on peut extraire de $I$ un stable de taille $K$ pour $G$ en supprimant une des extrémité de chaque arête.

Notez cependant que notre problème initial n'est pas exactement le même puisque l'on ne cherche pas forcément le plus grand, mais juste un graphe bi-parti à $e(G)/2$ arêtes que l'on sait exister.

Sous-graphe bi-parti exclus

On cherche des graphes à $n$ sommets ne possédant pas de sous-graphes bi-partis complets. On sait peut de choses sur ces graphes, mais on peut montrer que :

Théorème (Kővári, Sós, Turán)

Pour tout $s\leq t$, il existe ue constante $C$ telle que tout graphe à $n$ sommet ne possédant pas $K_{s, t}$ à moins de $C\cdot n^{2-{1}/{s}}$ arêtes.

preuve

TBD écrire la preuve.

Remarquez que la borne ne dépend pas de $t$.

Une application surprenante de ce théorème est une borne pour le problème consistant à trouver une configuration de $n$ points dans le plan maximisant le nombre de distance unité entre ces points.

Par exemple dans l'exemple suivant $n=2$ et on a 1 distance valant 1 unité :

distance unité 1

On peut bien sur généraliser (ci-dessous 5 points et 4 distances unités) :

distance unité 2

On est à $n$ points et $n-1$ distances unités. On peut bien sur faire mieux avec une échelle :

distance unité 3

Pour $n$ points et $2n-3$ distances unités.

On peut cependant faire mieux que le linéaire en dupliquant une solution, liant chaque point avec son pendant et en translatant le tout d'une unité :

distance unité 4

On passe d'une solution à $n_i$ sommets et $m_i$ distances à une solutions à $n_{i+1} = 2\cdot n_i$ sommets et $m_{i+1} = 2\cdot m_i + n_i$ distances. Ce qui donne l'équation :

$$ \frac{m_i}{n_i} = \frac{m_{i-1}}{n_{i-1}} + 1 = \dots = \frac{0}{1} + i = \log_2(n_i) $$

Ce qui donne une solution en $\mathcal{O}(n\log(n))$.

On peut borner le nombre de solution en remarquant que le graphe dont les sommets représentent les points et les arêtes les distances unités ne contient par le graphe $K_{2, 3}$. En effet la figure suivante le montre, l'intersection de 2 cercles de rayon unités est uniquement 2 points, deux sommets ne peuvent avoir 3 voisins à distance unité :

distance unité 5

Le théorème précédent nous donne donc une borne max du nombre d'arêtes : $\mathcal{O}(n^{2-1/2}) = \mathcal{O}(n^{3/2}) = \mathcal{O}(n\sqrt{n})$.

Les meilleurs bornes connues sont :

Nous allons montrer maintenant une borne min pour des graphes sans sous-graphes bi-parti complets.

Théorème

Pour tout $s\leq t$, il existe des graphes à $n$ sommets ayant plus de $\frac{1}{16}\cdot n^{2-\frac{s + t -2}{s\cdot t -1}}$ arêtes n'admettant pas $K_{s, t}$ comme sous-graphe.

preuve

Conséquence directe du théorème suivant.

La preuve du théorème suivant utilise la méthode probabiliste avec altération. Ce raffinement de la méthode probabiliste commence par construire un graphe aléatoire puis on le modifie pour qu'il satisfasse nos hypothèse. Encore une fois la preuve est (extrêmement) élégante mais non constructive :

Théorème

Soit $H$ un graphe à $v(H) \geq 2$ sommets et $e(H) \geq 3$ arêtes, il existe $s\leq t$, il existe des graphes à $n$ sommets ayant plus de $\frac{1}{16}\cdot n^{2-\frac{v(H) -2}{e(H) -1}}$ arêtes n'admettant pas $H$ comme sous-graphe.

preuve

La preuve va consister à construire un graphe aléatoirement, puis à supprimer toutes les copies de $H$ qu'il contient.

Soit $G$ à $n$ sommets construit tel que la probabilité d'avoir l'arête $xy$ vaut $p$ quelque soit l'arête (ces graphes sont appelés graphes aléatoire de Erdős-Rényi, on y revient plus tard dans ce cours). On choisira $p$ plus tard pour maximiser le nombre d'arêtes tout en conservant peux de copies de $H$ dans $G$.

En notant $\sharp H$ le nombre de sous-graphes valant $H$ de $G$ on va calculer son espérance $\mathbb{E}(\sharp H)$.

Pour cela il nous faut une autre donnée qui est le nombre d'automorphisme de $H$ (les permutation de sommets conservant $H$), appelons le $\text{aut}(H)$, pour pouvoir écrire :

$$ \begin{array}{lcl} \mathbb{E}(\sharp H) &=& \frac{n\cdot(n-1)\cdot \dots \cdot (n-v(H))}{\text{aut}(H)}\cdot p^{e(H)}\\ \end{array} $$

Puisque l'on compte pour tout ensemble de $v(H)$ sommets la probabilité de fabriquer $H$ en sachant que :

  • on choisit $v(H)$ sommets
  • chaque arête a une probabilité $p$ d'exister, indépendante des autres, et qu'il en faut $e(H)$ (d'où la multiplication $p \cdot \dots \cdot p = p^{e(H)}$).
  • on divise par le nombre de possibilités de fabriquer le même $H$ avec une permutation des sommets choisis qui correspond à son nombres d'automorphismes (si $H$ est un cycle de longueur 4, les choisir les 4 sommets $(1, 2, 3, 4)$ va produire le cycle 1-2-3-4, il sera identique au cycle produit avec les sommets $(2, 3, 4, 1)$ (le cycle 2-3-4-1), $(3, 4, 1, 2)$ (le cycle 3-4-1-2) et $(4, 3, 2, 1)$ (le cycle 4-1-2-3). Mais il sera différent du cycle produit par les sommets $(2, 1, 3, 4)$ qui produit le cycle 2-1-3-4 où le sommet 1 est voisin de 2 et 3 alors qu'il est voisin de 4 et 1 dans l'autre cycle) et est une constante dépendant de $H$.

On en déduit l'inégalité :

$$ \begin{array}{lcl} \mathbb{E}(\sharp H) &\leq& n^{v(H)}\cdot p^{e(H)}\\ \end{array} $$

D'un autre côté l'espérance du nombre d'arête de $G$ vaut :

$$ \mathbb{E}(e(G)) = p \cdot \binom{n}{2} $$

On veut que le nombre d'arête de $G$ soit le plus grand possible tout en minimisant le nombre de sous-graphes valant $H$ : on cherche à maximiser $\mathbb{E}(e(G) - \sharp H) = \mathbb{E}(e(G)) - \mathbb{E}(\sharp H)$.

$$ \begin{array}{lcl} \mathbb{E}(e(G) - \sharp H) &\geq& p \cdot \binom{n}{2}[1-2p^{e(H)-1}\cdot \frac{n^{v(H)-1}}{n-1}]\\ &\geq& p \cdot \binom{n}{2}[1-2p^{e(H)-1}\cdot {n^{v(H)-2}}]\\ \end{array} $$

On peut maintenant trouver un $p$ qui va simplifier tout ça, par exemple $p = \frac{1}{2}\cdot n^{-\frac{v(H) -2}{e(H) -1}}$ puisqu'on a alors :

$$ \begin{array}{lclr} \mathbb{E}(e(G) - \sharp H) &\geq& p \cdot \binom{n}{2}[1-2(\frac{1}{2}\cdot n^{-\frac{v(H) -2}{e(H) -1}})^{e(H)-1}\cdot {n^{v(H)-2}}]\\ &\geq& p \cdot \binom{n}{2}[1-\frac{1}{2^{e(H)-2}}]\\ &\geq& p\cdot \binom{n}{2}\cdot \frac{1}{2} &\text{ puisque }e(H)\geq 3\\ &\geq& \frac{1}{4} p\cdot (n(n-1))\\ &\geq& \frac{1}{8} \cdot n^{-\frac{v(H) -2}{e(H) -1}}\cdot (n(n-1))\\ &\geq& \frac{1}{8} \cdot n^{-\frac{v(H) -2}{e(H) -1}}\cdot (n(\frac{n}{2}))& \text{ puisque }v(H)\geq 2\\ &\geq& \frac{1}{16}\cdot n^{2-\frac{v(H) -2}{e(H) -1}}\\ \end{array} $$

On peut maintenant utiliser l'argument classique de la méthode probabiliste : il existe forcément un graphe $G^\star$ tel que $e(G) - \sharp H \geq \frac{1}{16}\cdot n^{2-\frac{v(H) -2}{e(H) -1}}$.

Il suffit maintenant d'enlever une arête de $G^\star$ pour toute copie de $H$ en lui (on énumère tous les sous-graphe de $G^\star$ et on supprime si nécessaire une de ses arête si c'est $H$). On obtient alors un nouveau graphe ${G^\star}'$ sans sous-graphe valant $H$ et ayant au moins $e(G^\star) - \sharp H \geq \frac{1}{16}\cdot n^{2-\frac{v(H) -2}{e(H) -1}}$ arêtes.

On peut faire mieux en utilisant d'autres méthodes, en particulier algébrique. Regardez le lien si vous voulez plus d'infos.

Pour le graphe bi-parti complet $K_{s, t}$ cela nous donne l'encadrement suivant pour un graphe $G$ à $n$ sommets ne possédant pas $K_{s, t}$ comme sous-graphe :

$$ \frac{1}{16}\cdot n^{2-\frac{s + t -2}{s\cdot t -1}} \leq e(G) \leq C_n \cdot n^{2-{1}/{s}} $$

Notez que lorsque $t$ tend vers l'infini les deux bornes vont se rejoindre.

Pour des graphes bi-partis $K_{s, s}$ on obtient :

$$ \frac{1}{16}\cdot n^{2-\frac{2}{s + 1}} \leq e(G) \leq C_n \cdot n^{2-{1}/{s}} $$

En particulier pour le graphe sans cycle de longueur 4, c'est à dire des graphes sans $K_{2, 2}$ on a la l'encadrement :

$$ \Theta(n^{4/3}) \leq e(G) \leq \mathcal{O}(n^{3/2}) $$

On peut trouver des encadrement plus fin en utilisant des méthodes plus sophistiquée, si cela vous intéresse, regardez la vidéo en lien.

https://www.youtube.com/watch?v=crMyNv2fdkc&list=PLUl4u3cNGP61cYB5ymvFiEbIb-wWHfaqO&index=1