Description du problème

Considérons un graphe $\mathcal{G} = \langle \mathcal{V}, \mathcal{E} \rangle$ où $\mathcal{V} = \{v_1, \dots, v_N\}$ est un ensemble de $N$ sommets et $\mathcal{E} \subset \binom{\mathcal{V}}{2}$ est un ensemble de paires de sommets de la forme $\{u, v\}$ , avec $u \neq v$ . Ce graphe est simple (aucun sommet n’est relié à lui même) et symétrique (les connexions sont non orientées).

Nous appelons étiquetage des sommets une fonction injective $f: \mathcal{V} \to \llbracket 1, N \rrbracket$ qui à chaque sommet associe un entier compris entre $1$ et $N$ . Son score $S_\mathcal{G}(f)$ pour un graphe $\mathcal{G}$ est défini comme suit :

Le problème auquel nous nous intéressons est le suivant : trouver un étiquetage $f$ de score $S_\mathcal{G}(f)$ le plus petit possible pour le graphe $\mathcal{G}$ suivant :

La matrice d’adjacence $\textbf{A}$ du graphe $\mathcal{G}$ ci-dessus, définie par $\textbf{A}_{u, v} = \left\{\begin{array}{ll}1 & \textbf{si } \{u, v\} \in \mathcal{E} \\ 0 & \textbf{sinon}\end{array}\right.$ , est fournie dans les modèles de code que vous trouverez plus bas.

Exemple

Sur le graphe décrit dans la figure ci-après, le score le plus bas possible est 13. L’étiquetage correspondant est représenté au centre de chaque sommet.

Modèles de code

Pour faciliter le démarrage de l’exercice, nous fournissons des squelettes de code pour quelques langages de programmation usuels. Il autorisé d’utiliser un autre langage que ceux pour lesquels un fichier est fourni.

Chacun des fichiers contient trois éléments principaux :

Une constante $\texttt{graph}$ représentant la matrice d’adjacence $\textbf{A}$ du graphe étudié, donnée sous la forme d’un tableau de $N$ listes; la liste à l’indice $i$ contenant les indices des sommets voisins du sommet $i$ .
Une fonction $\texttt{result}$ , prenant en paramètre un étiquetage $f$ des sommets de $\mathcal{G}$ , qui affiche sur la sortie standard une chaîne de caractères représentant $f$ .
Une fonction $\texttt{main}$ , point d’entrée du programme, qu’il vous faudra compléter.

Classement actuel

Classement	Equipe
1	Jnuteurs
1	Pluto

Soumettre une réponse

Soit $f$ un étiquetage des sommets solution au problème posé. La réponse au problème doit être fournie sous la forme $f_1 - f_2 - \dots- f_N$ , où $f_i$ est l’étiquette associée au sommet d’indice $i$ dans $\textbf{A}$ . Dans les fichiers fournis, la fonction $\texttt{result}$ affiche $f$ sous cette forme.

Vous devez être inscrit au concours pour pouvoir soumettre une réponse.