Camille dessine quatre tables nommées A, B, C et D pour un dîner entièrement inventé. Elle souhaite choisir des liaisons qui permettent de passer de chaque table à toutes les autres. Chaque liaison retenue possède un score, payé une seule fois dans leur catalogue. Paul voudrait commencer par les trajets les plus courts depuis A. Leurs deux demandes semblent proches, mais elles ne choisissent pas nécessairement le même dessin. Nous allons remplir leurs propositions, puis examiner les corrections qu'un changement de score ou une liaison imposée demanderait réellement.
draw.io présente un outil de diagrammes.
Lucidchart présente un outil de diagrammes.
Cacoo présente un outil de diagrammes.
Ces présentations ont été lues pour identifier des outils. Aucun logiciel n'a été essayé ; nos scores et nos règles ne viennent pas de leurs pages.
Les traits et les scores sont stipulés sur papier. Ils ne décrivent ni un passage réel, ni des câbles, ni une installation à acheter. Les liaisons peuvent être parcourues dans les deux sens. Camille demande d'abord un réseau connecté sans cycle : il doit relier les quatre tables, sans boucle de traits distincts. Les calculs classiques utilisés ici ne sont pas revendiqués comme une invention. Une possibilité de notre catalogue n'établit aucune accessibilité ni sécurité dans une salle réelle.
Six traits possibles, trois traits à choisir
| Liaison | Score |
|---|---|
| AB | 1 |
| BC | 2 |
| AC | 3 |
| CD | 4 |
| BD | 5 |
| AD | 6 |
Un réseau connecté sans cycle sur ces quatre tables possède trois liaisons. Camille additionne les scores des traits choisis, pas ceux des parcours que Paul pourrait effectuer ensuite. Passer plusieurs fois par AB ne crée donc pas plusieurs exemplaires d'AB dans la sélection. Inversement, un trait présent dans le dessin doit être compté même si aucun déplacement particulier n'a encore été raconté. Cette règle définit l'objet du choix : un ensemble de trois liaisons qui joint les quatre noms.
Camille prend AB, de score un, puis BC, de score deux. Elle possède alors un groupe A, B, C et une table D encore séparée. Le trait suivant dans l'ordre des scores est AC, trois. Elle l'écarte : A et C sont déjà reliés par AB puis BC, et ajouter AC fermerait un triangle sans rejoindre D. Elle prend ensuite CD, quatre. Son dessin final relie A à D par B et C, avec un score total de sept. Elle remet ces trois traits à Paul, au lieu de sélectionner les trois scores les plus bas puis de découvrir que leur triangle laisse D seule.
Paul avait préparé AB, AC et AD. Depuis A, il peut atteindre B avec un, C avec trois et D avec six. Ces scores sont les meilleurs possibles dans le catalogue initial : le détour par B donne également trois pour C, et aucun passage indirect ne donne moins de six pour D. Son réseau de trois traits coûte pourtant dix. Dans celui de Camille, le trajet de A à D vaut sept, donc davantage, alors que le réseau entier coûte seulement sept. Elle accepte ce trajet plus long parce que sa demande porte sur la sélection commune. Paul retire de sa fiche « meilleurs trajets depuis A, donc meilleur réseau » ; ses deux constructions ont rempli des objectifs différents.
Il choisit ensuite de conserver le dessin de Camille pour le chapitre du dîner, mais refuse de le décrire comme le meilleur pour chaque convive partant d'A. La fiche garde le total sept auprès de la liste AB, BC, CD. Paul place le trajet A, B, C, D dans une autre ligne, avec son propre score sept. Les deux nombres coïncident ici parce que ce trajet utilise tous les traits du réseau une fois ; la fiche n'en fait pas une définition générale du coût commun. Camille ne demande pas que tous les convives répètent ce trajet, et aucun nombre de déplacements n'est ajouté au catalogue pour justifier son choix.
Une séparation permet de justifier le trait retenu
Après AB et BC, Camille considère le groupe A, B, C d'un côté et D de l'autre. Une réalisation qui les relie doit prendre au moins un des traits CD, BD ou AD. Leurs scores sont quatre, cinq et six. Elle choisit CD, quatre. Si Paul remet BD à sa place tout en gardant AB et BC, son réseau vaut huit ; avec AD, il vaut neuf. Le choix de CD ne repose donc pas sur une proximité dessinée entre les tables. Il repose sur les traits effectivement autorisés à franchir cette séparation et sur leurs scores, renseignés dans la même demande.
Camille revient ensuite sur le premier choix, AB. La séparation A d'un côté et B, C, D de l'autre offre AB, AC et AD. AB est le moins coûteux, avec un contre trois et six. Pour leur autre réseau AB, AC, AD, Paul peut remplacer AD par CD : les quatre tables restent reliées, et le score passe de dix à huit. Il peut ensuite remplacer AC par BC, ce qui le ramène à sept. Camille lui montre les deux étapes sur ses listes. Elle ne lui demande pas d'enlever au hasard son trait le plus cher avant de vérifier que la table libérée serait encore jointe au reste.
Pour garder AB dans une réalisation optimale, il suffit aussi d'examiner une réalisation qui l'aurait omis. Ajouter AB à un réseau sans cycle crée une boucle unique entre A et B. Le chemin ancien de A à B traverse la séparation A d'un côté, les autres tables de l'autre. Il contient donc AC ou AD, plus cher qu'AB. Enlever ce trait après l'ajout laisse toutes les tables reliées et réduit le score. Paul renonce ainsi à chercher un minimum qui omettrait AB. Leur argument a identifié le trait à retirer et le raccord à préserver, plutôt que se contenter de dire que le trait le moins cher serait toujours agréable à garder.
Une fois AB retenu, Camille veut joindre son groupe A, B à C ou D. Les traits qui sortent de ce groupe sont BC, AC, BD et AD. BC, deux, est le moins cher. Elle le retient sans comparer CD, qui ne touche pas encore son groupe. Paul avait proposé CD avant BC parce qu'il voit un autre petit groupe C, D possible. Cette proposition n'est pas interdite ; elle peut conduire au même dessin final. Camille garde néanmoins son contrôle de séparation pour expliquer pourquoi BC peut rejoindre AB sans perdre une meilleure solution. Le trait choisi doit traverser la séparation qu'elle examine réellement, pas une séparation différente dessinée après coup.
Contrôler un dessin entier par ses traits absents
Sur le dessin AB, BC, CD, ajouter AC crée la boucle A, B, C, A. Son score trois dépasse les deux scores déjà présents, un et deux. Enlever BC pour garder AC ferait passer le total de sept à huit ; enlever AB le ferait monter à neuf. Camille refuse donc ces deux remplacements. Elle procède de même pour BD : le chemin de B à D contient BC et CD, dont le plus grand score est quatre. BD vaut cinq. Pour AD, le chemin existant possède les scores un, deux, quatre, tandis qu'AD vaut six. Aucun des trois traits absents ne remplace un trait plus cher sur la boucle qu'il créerait.
Paul souhaite transformer ces trois comparaisons en contrôle du minimum global, pas seulement en rejet de trois dessins voisins. Camille prend un autre réseau possible et y ajoute un trait du dessin retenu qui lui manque. La boucle ainsi créée contient un trait absent du dessin retenu. Les comparaisons de chemins permettent de choisir un retrait qui ne rend pas le réseau plus coûteux ; en répétant les échanges, elle retrouve AB, BC, CD. Le certificat porte donc sur chaque trait absent et sur le maximum du chemin qui joint ses extrémités. Elle garde ces chemins dans sa fiche, afin que l'annonce « aucun échange améliorant » puisse être contrôlée sur les données exactes.
Une égalité change le nombre de choix, pas le meilleur score
Une branche réduit seulement AC de trois à deux. AB reste un, BC deux et CD quatre. Camille peut garder AB, BC, CD, toujours de total sept. Paul peut aussi prendre AB, AC, CD, de même total. Chacun relie les quatre tables sans cycle. L'échange entre BC et AC conserve le meilleur score au lieu de l'améliorer. Ils préparent donc deux listes minimales dans cette branche. Camille choisit la première pour la scène suivante, tout en retirant le mot « unique » de sa note : le choix qu'elle effectue entre les deux listes n'est pas une préférence que les scores auraient déjà imposée.
Cette égalité ne permet pas de garder les deux traits BC et AC avec AB dans le réseau sans cycle. Leur triangle relie seulement A, B et C ; D reste séparée. Il faudrait encore ajouter CD, ce qui donnerait quatre traits et sortirait de la demande. Paul avait essayé de présenter ce triangle comme la réunion des deux solutions de total sept. Camille lui fait comparer les ensembles complets : leurs deux réalisations ont AB et CD en commun, puis un seul des deux traits AC ou BC. Leur union n'est pas une troisième réalisation minimale. Il choisit donc réellement l'un des deux traits avant de remettre le réseau retenu.
Dans les scores initiaux, chacun des trois traits absents dépassait strictement le maximum du chemin correspondant. Camille peut alors exclure tout autre réseau de même coût. Au premier ajout d'un trait absent, le retrait possible sur sa boucle remplace un trait moins cher par un plus cher. Les échanges vers leur dessin améliorent strictement la réalisation qui diffère. Dans la branche AC égal à deux, cette stricte différence disparaît sur le triangle A, B, C et les deux listes deviennent possibles. Paul conserve les scores des comparaisons, au lieu d'expliquer l'unicité par la seule règle « trois traits pour quatre tables », que les deux réalisations respectent également.
Réparer le réseau après un changement local de score
Une nouvelle branche repart du catalogue initial, puis fait monter BC à dix. AB, BC, CD coûterait maintenant quinze. Camille enlève BC de ce dessin et obtient les groupes A, B d'une part, C, D d'autre part. Elle compare les traits qui pourraient les réunir : AC vaut trois, BD cinq, AD six et BC dix. Elle prend AC. Le réseau réparé AB, AC, CD vaut huit. Aucun autre trait n'a changé, et CD est resté dans la sélection. Paul reçoit la correction précise « remplacer BC par AC », plutôt qu'une proposition de recommencer en choisissant toutes les petites valeurs sans montrer quel groupe aurait été séparé.
Paul remarque que BD reste moins cher que le nouveau BC et propose AB, BD, CD. Ce réseau est effectivement admissible, mais vaut dix. Camille ne l'écarte pas comme un dessin mal connecté ; elle l'écarte parce qu'AC relie les mêmes deux groupes pour trois au lieu de cinq. Sa réparation a donc un témoin concurrent rempli, avec le bon motif de refus. L'ancienne réalisation de total sept reste dans la branche aux anciens scores. La nouvelle note donne huit sous BC égal à dix, sans prétendre que l'amélioration de quinze à huit aurait révélé une erreur dans le premier catalogue.
Une branche différente baisse BD de cinq à un, sans toucher BC. Camille l'ajoute au dessin initial et voit la boucle B, C, D, B. Pour revenir à un réseau sans cycle, elle doit enlever un trait de cette boucle : BC vaut deux et CD quatre. Elle enlève CD, puis remet AB, BC, BD, de total quatre. Enlever AB, qui ne figure pas dans cette boucle, isolerait A tout en gardant le triangle. Paul corrige donc sa proposition d'enlever « un ancien trait quelconque ». La baisse du score d'un trait absent demande un contrôle de boucle, tandis que la hausse précédente d'un trait présent demandait un contrôle de séparation.
Une liaison imposée définit un autre minimum
Paul impose maintenant AD dans une branche aux scores initiaux. Camille ne peut plus choisir AB, BC, CD, qui l'omet. Elle commence par AD, puis traite A et D comme un groupe déjà joint. Parmi les traits encore disponibles, AB vaut un, BC deux, AC trois, CD quatre et BD cinq. AB ajoute B au groupe ; BC ajoute C. Elle remet donc AD, AB, BC, de total neuf. Le trait imposé vaut bien six dans ce total. Leur nouvelle demande ne disait pas qu'il serait gratuit, seulement qu'il devrait être présent. Un réseau coûtant sept demeure le minimum de l'ancienne demande, pas une réponse à celle-ci.
Pour vérifier neuf, Camille examine les deux traits supplémentaires possibles. Les deux moins chers, AB et BC, valent ensemble trois et permettent effectivement de joindre B et C au groupe A, D. Aucun couple de traits disponibles ne peut coûter moins de trois. La borne et la construction coïncident. Paul voulait pourtant ajouter CD pour maintenir la liaison de son ancien dessin. Camille l'écarte : AD, AB, BC relie déjà toutes les tables, et CD fermerait une boucle. Il retire donc la promesse de conserver chaque ancien trait. L'ajout obligatoire d'AD exigeait ici une autre sélection, pas l'empilement du trait nouveau sur l'ancienne liste.
La fiche de cette branche garde séparément le coût total neuf et le coût des deux traits ajoutés trois. Paul peut parler de trois seulement lorsqu'il nomme ce complément. Il refuse désormais une phrase annonçant « le réseau coûte trois », qui omettrait AD. Camille lui donne les deux lignes et la liste entière. Cette remise ne modifie pas le catalogue pour économiser les six d'AD : elle indique quel nombre répond à quelle question. La demande d'avoir AD présent et celle de compter toutes les liaisons du réseau sont satisfaites ensemble dans la sélection choisie.
Des scores négatifs ne changent pas seulement l'ordre des traits
Une dernière branche donne moins trois à AB, moins deux à BC et moins un à AC ; CD reste quatre, BD cinq et AD six. Sous la demande d'un réseau connecté sans cycle, Camille prend AB et BC, puis CD. Le total vaut moins un. Elle écarte AC parce qu'il fermerait le triangle, même si son score est négatif. Paul propose de garder également AC, ce qui ferait baisser le total à moins deux. Camille reconnaît le calcul, puis refuse cette proposition sous la règle sans cycle. Un trait avantageux pour l'addition peut encore être interdit par la forme effectivement demandée.
Paul change alors expressément la demande : le réseau doit rester connecté, mais les cycles sont maintenant permis. Camille prend AB, BC, AC et CD. Les trois traits négatifs sont tous présents et leur triangle est admis ; CD rejoint D pour quatre. Le total moins deux est le minimum de cette nouvelle demande. Pour joindre D, aucun de BD ou AD n'offre moins que quatre ; les trois traits négatifs peuvent tous être conservés sans autre obligation. Camille remet cette liste de quatre traits, distincte de la liste de trois. Le changement de minimum vient de la permission sur les cycles, pas d'une règle oubliée dans l'ancien calcul.
Ce minimum reste un nombre fini. Un trait est compté une seule fois dans la sélection, même si Paul raconte ensuite plusieurs passages dessus. Le catalogue comporte six traits et donc seulement soixante-quatre sous-ensembles à examiner. Camille ne retire pas trois à chaque tour du triangle pour annoncer un réseau sans limite de score. Ce serait compter un parcours répété au lieu de sélectionner un ensemble. Elle garde la liste AB, BC, AC, CD avec moins deux et le trajet éventuellement raconté dans une autre rubrique. Les deux rubriques peuvent partager des noms de tables sans partager leur objet d'optimisation.
Garder les quatre tables reliées après le retrait d'un trait
Paul formule enfin une autre demande, sous les scores initiaux : après le retrait de n'importe quelle liaison choisie, les quatre tables doivent encore rester reliées. Les cycles sont permis et même nécessaires dans cette branche. Le retrait porte sur un trait, pas sur une table ni sur deux traits simultanés. Camille examine donc chaque liaison de la sélection, en conservant les autres. La nouvelle règle n'affirme aucune fiabilité de matériel ; elle définit seulement les dessins qu'ils vont accepter sous cette permission de retrait.
Dans AB, BC, CD, enlever BC sépare A, B de C, D. Ajouter seulement AC ne répare pas toute la nouvelle demande : AB, BC, AC, CD possède un triangle, mais enlever CD laisse encore D seule. Camille retient plutôt AB, BC, CD, AD, de score treize. Enlever AB laisse le chemin A, D, C, B ; enlever BC laisse B, A, D, C ; enlever CD laisse C, B, A, D ; enlever AD laisse A, B, C, D. Chaque retrait possède donc son propre témoin. Paul renonce à sa proposition « un triangle quelque part suffit » : la table D y restait attachée par un seul trait. La liste de quatre retenue protège toutes les liaisons choisies contre le retrait stipulé, pas seulement celles du triangle.
Pour contrôler le minimum treize, Camille remarque que chaque table doit toucher au moins deux traits : avec un seul, leur retrait isolerait cette table. Quatre traits sur quatre tables, tous reliés, doivent donc former un cycle passant par les quatre noms. Le catalogue donne trois cycles distincts, sans compter deux fois leurs sens : AB, BC, CD, AD vaut treize ; AB, BD, CD, AC vaut aussi treize ; AC, BC, BD, AD vaut seize. Avec cinq traits, le total minimal possible est quinze, obtenu en omettant AD du catalogue de total vingt et un ; avec six, il vaut vingt et un. Camille choisit le premier cycle de treize et conserve le second comme alternative minimale. Paul reçoit quatre tests de retrait et cette comparaison des tailles, au lieu d'une promesse de continuité que leur ancien minimum de sept n'avait pas remplie.
La préparation retenue pour la première scène reste AB, BC, CD sous les scores initiaux, avec un total de sept. Les branches aux autres scores, à AD imposé et au retrait d'un trait portent leurs propres listes. Camille peut montrer un réseau précis sans annoncer qu'il raccourcit chaque trajet, puis corriger une liaison sans inventer un nouveau dîner. Ses traits choisis donnent au chapitre les résultats qu'il décrit. Les dessins restent des données de papier, et leur contrôle ne se substitue à aucune étude de circulation ou d'installation réelle.