Cette section  présente deux  approches permettant de 
générer des fonctions $f$ dont le graphe des itérations $\textsc{giu}(f)$ 
est fortement 
connexe.
La première est algorithmique mais grossière (section~\ref{sub:sccg2})
tandis que la seconde s'appuie sur des conditions suffisantes 
sur le graphe d'interactions de la fonction booléenne $f$ 
(Section~\ref{sub:sccg1}). 
%pour obtenir un graphe d'itérations fortement connexe (Section~\ref{sub:sccg1}).
  
\subsection{Génération algorithmique grossière}\label{sub:sccg2} 
Cette section présente une première approche permettant 
de générer une fonction booléenne $f$ dont le graphe des itérations $\textsc{giu}(f)$
est fortement connexe.
La méthode est itérative et basée sur une démarche générer-tester.

On considère en premier lieu la fonction 
négation $\neg$ dont le graphe des itérations 
$\textsc{giu}(\neg)$ est fortement connexe. 
Soit un  graphe $\textsc{giu}$, initialisé avec
$\textsc{giu}(\neg)$. L'algorithme  effectue itérativement les deux étapes suivantes:
\begin{enumerate}
\item sélection aléatoire d'un arc du graphe d'itérations en cours,
  $\textsc{giu}$, puis
\item analyse de la forte connexité du graphe d'itérations en cours auquel on enlèverait cet arc.
  Dans le cas positif, cet arc est enlevé de $\textsc{giu}$,
\end{enumerate} et ce jusqu'à ce qu'un taux $r$ d'arcs 
enlevés soit supérieur à un seuil donné 
par l'utilisateur.
Si $r$  est proche de  $0\%$ (\textit{i.e.} peu d'arcs ont été supprimés),
il reste peu ou prou $n\times 2^n$ arcs.  
Dans le cas contraire, si $r$ est proche de 
$100\%$, il ne reste plus qu'environ $2^n$ arcs.
Dans tous les cas, cette étape retourne un graphe $\textsc{giu}$ 
qui est fortement connexe. 
A partir du graphe $\textsc{giu}$, il est alors  facile de construire la 
fonction $f$. 

Même si cet algorithme retourne toujours des fonctions dont le graphe 
des itérations est fortement connexe, il n'en est pas pour le moins efficace.
Un défaut de l'algorithme est de nécessiter une vérification systématique de 
forte connexité sur le graphe entier composé de  $2^{\mathsf{N}}$ sommets et ce,
à chaque itération!   
La section suivante propose une solution à ce problème.
Elle présente des conditions suffisantes sur un graphe à ${\mathsf{N}}$ sommets
qui permettent d'obtenir des graphes d'itérations fortement connexes.



\subsection{Conditions suffisantes sur le graphe d'interactions}\label{sub:sccg1}

Cette partie énonce un théorème dont les hypothèses 
portent sur les interactions entre $x_i$ et 
$f_j$ et qui permet de n'engendrer que des fonctions
$f$ dont le  graphe d'itérations
 $\textsc{giu}(f)$  est fortement connexe.

\begin{theorem}\label{th:Adrien}
Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ vers lui-même telle que:
\begin{enumerate}
\item 
$\Gamma(f)$ n'a pas de cycle de longueur supérieure ou égale à deux;
\item 
chaque sommet de  $\Gamma(f)$ qui possède une boucle 
positive a aussi une boucle négative;
\item
chaque sommet de $\Gamma(f)$ est accessible depuis un sommet qui possède 
une boucle négative.
\end{enumerate}
Alors, $\textsc{giu}(f)$ est fortement connexe.
\end{theorem}

La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}.

Illustrons ce théorème par un exemple. On considère par le graphe d'interactions 
$\Gamma(f)$ donné en figure~\ref{fig:Adrien:G}. 
Il vérifie le théorème~\ref{th:Adrien}: 
toutes les fonctions $f$ possédant un tel graphe d'interactions
ont un graphe d'itérations  $\textsc{giu}(f)$ fortement connexe.
Pratiquement, il existe 34226 fonctions de $\Bool^4$ dans lui même qui 
vérifient ce graphe d'intéraction. 
Cependant, nombreuses sont celles qui possèdent un comportement équivalent.
Deux fonctions sont équivalentes si leurs \textsc{giu} sont isomorphes 
(au sens de l'isomorphisme de graphes). Il ne reste alors plus que 
520 fonctions $f$ non équivalentes de graphe d'interactions $\Gamma(f)$.

\begin{figure}%[h]
  \begin{center}
    \includegraphics[scale=0.5]{images/Gi.pdf}
  \end{center}
\caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:Adrien:G}
\end{figure}
