Shortlist 2019, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Croatia
Concepts : Graphes : degrés, chemins, arbres · Invariants et monovariants · Principe extrémal
Solution officielle : Shortlist officielle 2019 (avec solutions), section C5 (livret PDF)
Problème 3 de l'OIM 2019
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2019, où il était le problème 3 (jour 1).
Énoncé¶
On a certain social network, there are \(2019\) users, some pairs of which are friends, where friendship is a symmetric relation. Initially, there are \(1010\) people with \(1009\) friends each and \(1009\) people with \(1010\) friends each. However, the friendships are rather unstable, so events of the following kind may happen repeatedly, one at a time:
Let \(A\), \(B\), and \(C\) be people such that \(A\) is friends with both \(B\) and \(C\), but \(B\) and \(C\) are not friends; then \(B\) and \(C\) become friends, but \(A\) is no longer friends with them.
Prove that, regardless of the initial friendships, there exists a sequence of such events after which each user is friends with at most one other user.
Indices : les idées clés
- Graphes : reformuler en termes de graphe ; le nombre de sommets de degré impair est toujours pair ; un arbre ne contient pas de cycle.
- Invariants et monovariants : chaque opération fait baisser le nombre d'arêtes de \(1\) et conserve la parité des degrés ; il suffit donc de trouver une opération qui préserve une bonne propriété (condition (1) dans la solution 1, connexité puis absence de cycle dans la solution 2).
- Principe extrémal : prendre un sous-graphe complet maximal, ou un plus petit cycle (solution 2).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions et une remarque).
Remarque commune. Le problème se reformule en termes de graphes. On a un graphe \(G\) à \(2019\) sommets, dont \(1010\) de degré \(1009\) et \(1009\) de degré \(1010\). On peut effectuer l'opération suivante : si un sommet \(A\) est adjacent à deux sommets distincts \(B\) et \(C\) non adjacents entre eux, on retire les arêtes \(AB\) et \(AC\) et on ajoute l'arête \(BC\). Appelons cela un rechangement d'amis. Il s'agit de montrer qu'une suite de tels rechangements mène à un graphe qui est une réunion disjointe d'arêtes isolées et de sommets isolés. Toutes les solutions utilisent cette reformulation.
Solution 1¶
Le graphe donné est connexe : la somme des degrés de deux sommets quelconques est au moins \(2018\), donc ils sont adjacents ou ont un voisin commun. Il vérifie donc la condition suivante :
Toute composante connexe de \(G\) ayant au moins trois sommets n'est pas complète et possède un sommet de degré impair. \(\quad (1)\)
(Le graphe initial n'est pas complet car les degrés sont au plus \(1010 < 2018\), et il a des sommets de degré impair \(1009\).)
Montrons que si \(G\) vérifie \((1)\) et possède un sommet de degré au moins \(2\), alors il existe un rechangement qui préserve \((1)\). Comme chaque rechangement diminue le nombre d'arêtes, une suite de tels rechangements aboutit forcément à un graphe de degré maximal au plus \(1\), ce qui conclut.
Soit \(A\) un sommet de degré au moins \(2\) dans une composante connexe \(G'\) de \(G\). Comme aucune composante d'au moins trois sommets n'est complète, on peut supposer que les voisins de \(A\) ne sont pas tous adjacents entre eux. (Par exemple, prenons un sous-graphe complet maximal \(K\) de \(G'\) ; un sommet \(A\) de \(K\) a un voisin hors de \(K\), et ce voisin n'est pas adjacent à tous les sommets de \(K\) par maximalité.) Retirer \(A\) découpe \(G'\) en composantes connexes plus petites \(G_1, \ldots, G_k\) (éventuellement \(k = 1\)), chacune reliée à \(A\) par au moins une arête. On distingue plusieurs cas.
Cas 1 : \(k \geq 2\) et \(A\) est relié à un certain \(G_i\) par au moins deux arêtes. Choisissons un voisin \(B\) de \(A\) dans \(G_i\) et un voisin \(C\) de \(A\) dans une autre composante \(G_j\). Les sommets \(B\) et \(C\) ne sont pas adjacents ; retirer \(AB\) et \(AC\) et ajouter \(BC\) ne déconnecte pas \(G'\) (\(A\) reste relié à \(G_i\)). La condition est préservée, car le rechangement ne change pas la parité des degrés des sommets (et la composante n'est pas complète puisque \(A\) et \(B\) ne sont plus adjacents).
Cas 2 : \(k \geq 2\) et \(A\) est relié à chaque \(G_i\) par exactement une arête. Considérons le sous-graphe induit sur \(G_i\) et \(A\). Le sommet \(A\) y est de degré \(1\) ; comme le nombre de sommets de degré impair d'un graphe est toujours pair, \(G_i\) contient un sommet de degré impair (dans \(G\)). Si \(B\) et \(C\) sont deux voisins distincts de \(A\), retirer \(AB\) et \(AC\) et ajouter \(BC\) préserve la condition : le rechangement crée deux nouvelles composantes, et si l'une d'elles a au moins trois sommets, elle n'est pas complète et contient un sommet de degré impair (puisque chaque \(G_i\) en contient un).
Cas 3 : \(k = 1\) et \(A\) est relié à \(G_1\) par au moins trois arêtes. Par hypothèse, \(A\) a deux voisins \(B\) et \(C\) non adjacents. Retirer \(AB\) et \(AC\) et ajouter \(BC\) ne déconnecte pas \(G'\). On conclut comme dans le cas 1.
Cas 4 : \(k = 1\) et \(A\) est relié à \(G_1\) par exactement deux arêtes. Soient \(B\) et \(C\) les deux voisins de \(A\), non adjacents. Retirer \(AB\) et \(AC\) et ajouter \(BC\) donne deux nouvelles composantes : l'une réduite au sommet \(A\), l'autre contenant un sommet de degré impair. C'est bon, sauf si cette seconde composante est un graphe complet à au moins \(3\) sommets. Mais dans ce cas, \(G_1\) serait un graphe complet privé de la seule arête \(BC\), et il aurait au moins \(4\) sommets, car \(G'\) n'est pas un cycle de longueur \(4\) (qui n'a que des sommets de degré pair). Soit \(D\) un troisième sommet de \(G_1\) ; alors retirer \(BA\) et \(BD\) et ajouter \(AD\) ne déconnecte pas \(G'\) (voir la figure du livret officiel), et on conclut comme dans le cas 1. \(\blacksquare\)
Solution 2¶
Comme dans la solution précédente, un rechangement préserve la propriété d'avoir un sommet de degré impair et (trivialement) celle de ne pas être complet ; de plus le graphe initial est connexe. On décrit un algorithme en deux étapes qui mène à un graphe de degré maximal au plus \(1\).
Étape 1 : une suite de rechangements mène à un arbre.
Preuve. Comme le nombre d'arêtes diminue à chaque rechangement, il suffit de montrer que, tant que le graphe contient un cycle, il existe un rechangement après lequel il reste connexe. Montrons qu'il existe un cycle \(Z\) et des sommets \(A\), \(B\), \(C\) tels que \(A\) et \(B\) soient voisins sur \(Z\), \(C\) ne soit pas sur \(Z\), et \(C\) soit adjacent à \(A\) mais pas à \(B\). Retirer \(AB\) et \(AC\) et ajouter \(BC\) laisse alors le graphe connexe (\(A\) et \(B\) restent reliés par le reste du cycle \(Z\)).
Pour trouver \(Z\), \(A\), \(B\), \(C\), deux stratégies. Si le graphe contient un triangle, on considère un plus grand sous-graphe complet \(K\), qui a donc au moins trois sommets. Comme le graphe n'est pas complet (et est connexe), il existe un sommet \(C\) hors de \(K\) relié à un sommet \(A\) de \(K\). Par maximalité de \(K\), il existe un sommet \(B\) de \(K\) non relié à \(C\), et on choisit un cycle \(Z\) dans \(K\) passant par l'arête \(AB\).
Si le graphe est sans triangle, on considère un plus petit cycle \(Z\). Ce cycle ne peut pas être hamiltonien (passer par tous les sommets) : sinon, par minimalité, le graphe n'aurait pas d'autres arêtes et tous ses degrés seraient pairs. On peut donc choisir un sommet \(C\) hors de \(Z\) adjacent à un sommet \(A\) de \(Z\). Le graphe étant sans triangle, \(C\) n'est adjacent à aucun voisin \(B\) de \(A\) sur \(Z\), et c'est fini. \(\square\)
Étape 2 : tout arbre se ramène, par rechangements, à une réunion disjointe d'arêtes et de sommets isolés.
Preuve. Un rechangement préserve l'absence de cycle. Après une suite de rechangements, on aboutit donc à un graphe acyclique sur lequel aucun rechangement n'est possible. Un tel graphe est de degré maximal au plus \(1\) : s'il avait un sommet \(A\) avec deux voisins \(B\) et \(C\), ceux-ci ne seraient pas adjacents (le graphe est sans cycle), et un rechangement serait possible. \(\blacksquare\)
Remarques¶
Remarque. En fait, la condition \((1)\) caractérise exactement les graphes que l'on peut ramener, par une suite de rechangements, à un graphe de degré maximal au plus \(1\).