Aide du package ExplorateurDeGraphes

Introduction

Le package ExplorateurDeGraphes sert

a)    à déclarer des graphes
        *    explicitement par des arcs ordinaires ou
        *    récursivement par des arcs universels ou conditionnels;

b)    à rechercher dans le graphe
        *    des sommets possédant une propriété particulière ou
        *    un chemin vers des sommets possédant une propriété particulière.

Les arcs universels ou conditionnels sont des règles de transition dont les sommets de destination ne sont construits qu'en cas de besoin pour effectuer des recherches. C'est pourquoi on dit que le graphe ainsi défini est virtuel. En particulier, on peut déclarer un graphe d'ordre infini et y réaliser des recherches.

Fonctions disponibles

<<ExplorateurDeGraphes`

Names["ExplorateurDeGraphes`*"]

Déclaration d'un graphe (exemple)

Les sommets peuvent être de n'importe quel type, sauf du type List. Par exemple, un sommet pourrait être un enregistrement de la forme

livre[titre["Les Misérables"], auteur[prenom[Victor], nom[Hugo]]]

Début  et fin d'une session de déclarations

?debutDeclaration

debutDeclaration[]  effectue les intitialisations nécessaires.

?finDeclaration

Puisque  finDeclaration[]  collecte les racines factuelles du graphe, il doit précéder les appels à la fonction  racinesGraphe[].

Déclaration d'arcs ordinaires

debutDeclaration[]

?arc

Les arcs sont orientés:

arc[998,499]

arc[998,991]

arc[997,990]

arc[997,1]

L'intérêt d'un graphe est que certains sommets possèdent plusieurs successeurs distincts.

Déclaration d'arcs universels

Pour tout nombre x, un successeur de x est  x-7

arc[x_,x-7]

Déclaration d'arcs conditionnels

?arcConditionnel

Si n est divisible par 2, alors un successeur de n est le quotient de n par 2:

arcConditionnel[ n_, Quotient[n,2],EvenQ[n]]

Si n est premier, alors un successeur de n est 1

arcConditionnel[n_,1,PrimeQ[n]]

Remarque
Formellement, la condition est une fonction du sommet de départ. Mais, puisque le sommet d'arrivée est une fonction du sommet de départ, on peut faire en sorte que la condition porte sur des propriétés du sommet d'arrivée.

Déclaration des arêtes

On peut aussi déclarer des arêtes. Les arêtes ne sont pas orientées (On peut aussi considérer qu'elles possèdent les deux orientations).

?arete

Barrière

?barriereQ

Les nombres ≤ 0 ne sont pas des sommets valides

Clear[barriereQ];
barriereQ[x_]:=x≤0

Pour exclure une liste de sommets, on peut utiliser la fonction barriereQ:

interdits={sommet1, sommet2, ...};
	Clear[barriereQ];
	barriereQ[nd_]:=MemberQ[interdits, nd];

finDeclaration[]

Représentation interne des règles de transformations conditionnelles

Dans le but de déverminer un programme, il peut s'avérer utile d'observer comment les arcs sont représentés à l'intérieur du package ExplorateurDeGraphes. L'ensemble des arcs est représenté par une fonction dénommée trans; chaque règle porte un numéro:

??ExplorateurDeGraphes`Private`trans

Le nombre total de règles est dénommé nbreRegles:

??ExplorateurDeGraphes`Private`nbreRegles

Recherche de sommets vérifiant une propriété

Successeurs

?succ

succ[48]

succ[21]

succ[14]

Algorithme de succ

Pour éviter les boucles, dans succ[x], l'élément  x  est automatiquement supprimé.

A chaque évaluation de succ[x], les successeurs qui vérifient barriereQ  sont éliminés (mais x n'est pas testé!).

La fonction elague  construit une liste de sommets interdits. A chaque évaluation de succ[x], les successeurs interdits sont éliminés (mais x n'est pas testé!).

Recherche d'un sommet possédant la propriété proprQ

?sommetPropriete

sommetPropriete[3072,egalQ[12]]

Donc un chemin de 3072 à 12 existe tandis qu'il n'y a pas de chemin de 500 à 84:

sommetPropriete[500,egalQ[84]]

Algorithme de sommetPropriete

Pour éviter les boucles, la procédure sommetPropriete mémorise les sommets précédemment visités et n'examine que les autres successeurs. De cette manière, le sous-graphe exploré est transformé en un arbre dénommé arbre des visites.

Afin d'arriver au but par le chemin le plus court, sommetPropriete explore l'arbre des visites en largeur, niveau par niveau.

La recherche est interrompue au niveau dans lequel un sommet vérifie la condition proprQ. Si, à la profondeur d'arrêt, plusieurs sommets vérifient la condition proprQ, la procédure les retourne tous. Les solutions situées à une plus grande profondeur dans l'arbre des visites sont ignorées.

Recherche exhaustive des sommets vérifiant butQ

?ensembleSommetsPropriete

Voici la liste de tous les descendants de 188 qui sont des multibpes de 5

ensembleSommetsPropriete[188,Mod[#,5]==0&]

Algorithme de ensembleSommetsPropriete

ndDpt peut être un sommet ou une liste de sommets. La procédure ensembleSommetsPropriete construit tous les successeurs de ndDpt et retourne la liste des sommets qui vérifient la condition proprQ. Dans le cas où ndDpt possède un trop grand nombre de descendants, on peut limiter la profondeur de la recherche.

Recherche des descendants d'un sommet

?ensembleDescendants

ensembleDescendants[100]

Prédécesseurs

?pred

pred[990]

pred[3]

Chemins vers des sommets vérifiant une propriété
(chemins simples de longueurs minimales)

Chemin courant vers un sommet donné

?cheminCourant

Cette fonction ne peut être utilisée que pendant ou après une recherche qui a abouti au sommet nd.

cheminCourant[96]

Chemin conduisant à un sommet qui vérifie proprQ

Pour chercher un chemin dont le sommet final vérifie une propriété, on compose les fonctions sommetPropriete puis cheminCourant.
Par exemple, cherchons un chemin de 3072 vers 12

cheminCourant[sommetPropriete[3072,egalQ[12]]]

Cherchons un chemin de 17 vers 3 ou 5

cheminCourant[sommetPropriete[17,membreQ[{3,5}]]]

Nombre de chemins retournés par la composition  cheminCourant[sommetPropriete[ndDpt, proprQ]]

Si la recherche ne porte que sur un seul sommet, la composition  retournera au plus un chemin.
Si la recherche porte sur plusieurs sommets, la composition ne reournera que des chemins de même longueur conduisant à des sommets distincts.

Chemins conduisant vers tous les sommets qui vérifient la propriété proprQ

Pour chercher un chemin dont le sommet final vérifie une propriété, on compose les fonctions ensembleSommetsPropriete puis cheminCourant.
Par exemple, cherchons un chemin vers tous les successeurs de 384 qui sont des multiples de 48:

enLignes[cheminCourant[ensembleSommetsPropriete[384,Mod[#,48]==0&]]]

Il y a 4 solutions; chaque solution est à lire en ligne.

Recherche de chemins vérifiant une propriété
(chemins simples de longueurs bornées)

Déclaration d'un nouveau graphe

debutDeclaration[]

arete[1,2]

arete[1,3]

arete[1,5]

arete[2,4]

arete[2,6]

arete[3,4]

arete[3,5]

arete[4,6]

arete[5,6]

finDeclaration[]

Hamilton

Un chemin est simple lorsqu'il ne visite pas pusieurs fois le même sommet.

Un chemin est fermé lorsque parmi les sucesseurs du dernier sommet figure le premier sommet.

Un cycle est un chemin simple fermé.

Un cycle hamiltonien est un chemin simple fermé qui passe par tous les sommets du graphe.

CheminSimple

?cheminSimple

Un chemin d'une longueur donnée:

cs=cheminSimple[{1},longueurQ[3],3]

Un cycle d'une longueur donnée:

cs=cheminSimple[{1},cycleQ[4],4]

Un chemin par des sommets prescrits

cs=cheminSimple[{1},passeParQ[{4,5}]]

Un chemin par tous les sommets prescrits (la longueur maximale du chemin est égale au nombre de sommets prescrits):

cs=cheminSimple[{1},passeParQ[{4,5,6}],3]

Un cycle hamiltonien (la longueur du cycle est égale à l'ordre du graphe;
si le graphe contient un cycle hamiltonien, on dit que le graphe est hamiltonien):

cycleHamilt=cheminSimple[{1},cycleQ[5]]

Un chemin hamiltonien (la longueur du chemin est égale à l'ordre  du graphe et le chemin n'est pas un cycle)

cheminHamilt=cheminSimple[{1},longueurQ[5][#]∧!cycleQ[5][#]&]

ensembleCheminsSimples

?ensembleCheminsSimples

Tous les chemins d'une longueur donnée:

enLignes[ensembleCheminsSimples[{1},longueurQ[3],3]]

Tous les cycles d'une longueur donnée:

enLignes[ensembleCheminsSimples[{1},cycleQ[4],4]]

Tous les chemins par des sommets prescrits

enLignes[ensembleCheminsSimples[{1},passeParQ[{4,5}]]]

Tous les chemins par tous les sommets prescrits (la longueur maximale du chemin est égale au nombre de sommets prescrits):

enLignes[ensembleCheminsSimples[{1},passeParQ[{4,5,6}],3]]

Tous les cycles hamiltoniens (la longueur du cycle est égale à l'ordre du graphe):

enLignes[ensembleCheminsSimples[{1},cycleQ[5]]]

Tous les chemins hamiltoniens (la longueur du chemin est égale à l'ordre  du graphe et le chemin n'est pas un cycle)

enLignes[ensembleCheminsSimples[{1},longueurQ[5][#]∧!cycleQ[5][#]&]]

Tous les chemins dans un sous-graphe prescrit. On peut définir le sous-graphe par une propriété caractéristique des sommets ou par la liste de ses sommets:

ess=ensembleCheminsSimples[{1},chaqueSommet[OddQ]]

ess=ensembleCheminsSimples[{1},sousGrapheQ[{1,2,4,6}],3]

ce qui équivaut à

ess=ensembleCheminsSimples[{1},chaqueSommet[membreQ[{1,2,4,6}]],3]

Chemins avec distance au but

Méthode des buts intermédiaires (ou balises)

cheminBalises

On cherche un chemin qui passe par certains sommets qu'on définit par des propriétés.  Une balise est un but intermédiaire, c'est-à-dire est fonction booléenne qui s'applique à un sommet.

?cheminBalises

Méthode de la réduction de la distance au but

Métaphore

Dans une région vallonnée, partant d'un point élevé pour atteindre la mer, on peut - si possible - suivre une ligne de plus grande pente. Ainsi, l'altitude décroît le long du chemin. Dans le cas où l'on aboutit au fond d'une cuvette, il faut accepter de remonter un peu; une méthode consiste à explorer le voisinage par cercles concentriques jusqu'à ce que l'on repère un point dont l'altitude est inférieure à celui du fond de la cuvette. On se rend alors en ce point, et le chemin vers la mer peut continuer.

Chemin de forte pente

On cherche un chemin qui, si possible, passe par des sommets dont la distance au but décroît. Dans le cas où aucun successeur direct n'est à une distance inférieure au but, le programme recherche le sommet le plus proche (en nombre d'arcs) dont la distance au but est à une distance inférieure.

?descenteForte

Chemin de faible pente

On cherche un chemin qui, si possible, passe par des sommets dont la distance au but décroît. Dans le cas où aucun successeur direct n'est à une distance inférieure au but, le programme recherche le sommet le plus proche (en nombre d'arcs) dont la distance au but est à une distance inférieure.

?descenteFaible

Fonctions booléennes (tests)

Reprenons l'exemple du début:

debutDeclaration[];
arc[998,499];arc[998,991];arc[997,990];arc[997,1];
arc[x_,x-7];
arcConditionnel[n_, Quotient[n,2],EvenQ[n]];
arcConditionnel[n_,1,PrimeQ[n]];
Clear[barriereQ];barriereQ[x_]:=x≤0;
elague[7];elague[2];
finDeclaration[]

Fonction d'égalité

?egalQ

Par exemple,

egalQ[11][13]

egalQ[13][13]

Un autre exemple est donné sous  Recherche d'un sommet.

Fonction d'appartenance

?membreQ

membreQ[{11,13,17}][12]

membreQ[{11,13,17}][13]

Un autre exemple est donné sous  Recherche d'un sommet.

Un sommet est-il une racine ?

?racineQ

racineQ[998]

racineQ[500]

Un sommet est-il terminal

?terminalQ

terminalQ[10]

terminalQ[1]

Autres fonctions

Reprenons l'exemple du début:

debutDeclaration[];
arc[998,499];arc[998,991];arc[997,990];arc[997,1];
arc[x_,x-7];
arcConditionnel[n_, Quotient[n,2],EvenQ[n]];
arcConditionnel[n_,1,PrimeQ[n]];
Clear[barriereQ];barriereQ[x_]:=x≤0;
finDeclaration[]

Coût d'une recherche

?cout

Par exemple,

sommetPropriete[144,egalQ[12]];cout[]

Ensemble des racines factuelles du graphe

?racinesGraphe

racinesGraphe[]

Affichage en colonnes

?enColonnes

Voir exemple sous recherche d'un chemin.

Affichage en lignes

?enLignes

enLignes[cheminCourant[ensembleSommetsPropriete[100,Mod[#,10]==0&]]]

Il y a deux solutions, chaque chemin étant écrit en ligne.

Profondeur d'une recherche

?profondeur

profondeur[]

sommetPropriete[50001,egalQ[1]]

profondeur[10000]

sommetPropriete[50001,egalQ[1]]

profondeur[]

profondeur[64]

?maxFct

?minFct