Bafouille !

Salut Clydevil,

pour le premier problème, j'ai trouvé en quelques minutes un graphe qui convenait, que j'ai identifié après moteur de recherche comme le graphe de Petersen (ce qui m'évite d'avoir à le dessiner).

Pour le second, j'ai cherché une petite heure, j'ai notamment essayé avec un cuboctaèdre, mais je pense pouvoir prouver que c'est impossible avec ce graphe-ci. Quand j'aurai un moment, j'essaierai avec d'autres graphes.

Bonjour Clydevil.

J'ai trouvé un moment pour Jacasser.
En partant du principe que je ne vois pas de raisonnement logique sur les graphes qui m'amène une solution par l'intelligence, je cherche une solution par la force (quand on n'a pas de tête...)
Du coup, un xls avec quelques formules qui me disent si la solution marche ou pas. -> un peu plus d'1 heure.
Ensuite recherche (en partant du principe '0 redondance sur le coup de fil 2', sinon il faut 0 redondance sur le coup de fil 3...)
Je trouve ça qui marche (les colonnes informent les lignes)
    1    2    3    4    5    6    7    8    9    10    11    12
1                        X        X               
2    X                                        X   
3    X                                        X   
4        X                    X                   
5        X                    X                   
6            X                        X           
7            X                        X           
8                X                        X       
9                X                        X       
10                    X                            X
11                    X                            X
12                        X        X               

Brutal... mais 30' max à rechercher. Du coup 1h30 (et un xls que je vais peut être commercialiser)
Toufau

@TOUFAU: Bravo!
@ebichu: Bravo aussi et je suis curieux de savoir comment toi ou ton programme vous rendez compte des symétries du graphe en question (ce qui fait que son dessin est si beau).

@Ebichu: Ha, j'avais compris qu'un programme t'avais permis d'au moins retirer certaines possibilités. Ok c'est plus clair. "Il se trouve qu'il est symétrique" oui, lol, mais c'est bien moins trivial que tu penses de représenter symétriquement (se rendre compte de la symétrie) un graphe symétrique. Donc vu ta réponse j'en déduis que tu l'as "démêlé" à la main en identifiant les nœuds qui jouent le même rôle. bravo en tout cas. (Ce graphe porte un nœud et a une propriété particulière, je la donnerais après l’énigme)

Pour Bafouille, un graphe de Petersen devrait pouvoir faire l'affaire. Les trois représentations ci-dessous devraient être topologiquement équivalentes:



Pour Jacasse par contre, je suis à la rue et la possible dissymétrie me perturbe aussi.
Affaire à suivre ...

Edit:
En y réfléchissant, il semble normal que le graphe pour Jacasse soit dissymétrique, car sinon il serait filaire. Avec 12 sommets et 12 x 4 / 2 = 24 arêtes, le graphe de Chvatal semble fonctionner, dont voici trois représentations équivalentes (il reste cependant à rajouter les flèches).

Bravo à tous les participants!

Quelques précisions:
-Le graphe pour le cas non orienté se nomme graphe de Petersen.
https://en.wikipedia.org/wiki/Petersen_graph
-Le graphe pour le cas orienté fait parti d'une famille nommé digraphe de Kautz
https://en.wikipedia.org/wiki/Kautz_graph
Vous pouvez voir sur cette page le cas ABC qui correspond à l’énigme.
Cette seconde question donne donc quelque chose qui se généralise (qui est efficace mais je ne sais pas si c'est démontre minimal pour les autres tailles du problème).

Plus généralement toutes ses questions se rapprochent des problématiques degree-diametre dans les graphes.

On peut trouver des informations ici:
http://combinatoricswiki.org/wiki/The_D … ral_Graphs
http://combinatoricswiki.org/wiki/The_D … l_Digraphs

Ce qui me passionne dans ces structures n'a qu'un rapport éloigné avec la communication, je reflechissais à comment un organisme doit s'organiser pour être capable de se reconstruire de la manière la plus robuste. Ça se rapproche des problématiques de programmes avec codes correcteurs mais dans un cas ultraparallelisé (ou chaque cellule ou agent agit parallelement avec les autres pour assurer l'intégrité du tout)

Voila voila!