Générateur de graphes - v5.4 - © Cyril Gavoille - Février 2023

USAGE

gengraph [-options] graph [parameters]

DESCRIPTION

Génère sur la sortie standard un graphe. Par défaut le graphe est non orienté et affiché selon une liste d'arêtes (au format texte), mais d'autres formats sont possibles: liste d'adjacence, format dot de GraphViz, xfig ou pdf par exemple. En paramètre figure le nom du graphe ainsi que ses paramètres éventuels, typiquement le nombre de sommets. La commande appelée seule affiche l'aide sur les options du générateur. Si les paramètres d'une option ou d'un graphe sont absents ou remplacés par "?", une aide spécifique est affichée. Une console supportant l'UTF8 est préférable.

       Ex: gengraph -help
	   gengraph -list | sort
	   gengraph -not ?
	   gengraph -xy unique ?
	   gengraph tree ?
	   gengraph ? arbre
	   gengraph tutte
           gengraph hypercube 8
           gengraph mesh 7 3 -not
	   gengraph mesh 50 50 -dele .5 -maincc -visu
	   gengraph rdodecahedron -visu
           gengraph tree 100 -visu
	   gengraph web 10 3 -visu
	   gengraph gabriel 50 -caption "Grabriel with n=50" -visu
	   gengraph gabriel 2000 -xy seed 1 0.15 -visu
	   gengraph gabriel 700 -xy seed 1 -0.3 -visu
	   gengraph sierpinski 7 3 -visu
	   gengraph udg 400 .1 -visu
	   gengraph udg 400 .1 -xy seed 3 1.5 -visu
	   gengraph udg 400 -1 -vsize -vcolor deg -visu
	   gengraph arytree 6 3 3 -dot filter circo -visu
	   gengraph dyck -dot filter circo -visu
	   gengraph ringarytree 4 2 3 0 -label 1 -visu
	   gengraph arboricity 100 2 -vcolor degr -visu
	   gengraph prime 6 -directed -loop 0 -visu
	   gengraph aqua 3 2 1 . -label 1 -dot filter dot -visu
	   echo "0->1->2->0" | gengraph load - -check bfs 0
	   gengraph tutte | gengraph -filter - diameter p
           gengraph rplg 300 3 -maincc -vcolor degr -vcolor pal wz -vsize -visu
           gengraph -xy box 15 15 -xy round 0 -xy grid 16 rng 30 -visu
	   gengraph linial 7 3 -check kcolorsat 3 | glucose -model

LE FORMAT STANDARD

Le format par défaut (ou standard) est une liste d'arêtes ou de chemins écrits au format texte. Ce format minimaliste est très proche de celui du format "dot" de GraphViz. D'autres formats de sortie sont possibles, notamment le format "dot" (voir l'option -format). Les sommets sont numérotés consécutivement de 0 à n-1 où n est le nombre de sommets présents dans le graphe (en fait cela peut être changé avec l'option -shift). Une arête entre i et j est représentée par i-j, un arc de i vers j par i->j. Les sommets isolés sont simplement représentés par le numéro du sommet suivit d'un espace ou d'un retour de ligne. Le nombre de sommets du graphe est l'entier le plus grand plus un.

Pour une représentation plus compacte, les arêtes (ou arcs) consécutives d'un chemin du graphe peuvent être regroupées en blocs i-j-k-…. Par exemple, les deux arêtes 3-5 et 5-8 peuvent être regroupées en 3-5-8. Mais ce n'est pas obligatoire. Également, les arêtes (ou arcs) d'une étoile peuvent être groupées avec i-(j k …). Par exemple, 3-(5 7 8) représente les arêtes 3-5, 3-7 et 3-8. Il n'est pas possible cependant de combiner chemins et étoiles, comme 3-(5-7-8) ou 3-(5-(7 8)). Toutefois 3-5-(7 …) est correct, mais pas 3-(5 6)-7 ni (3 5)-6. Les sommets isolés et les arêtes (ou les blocs d'arêtes) sont séparés par des espaces ou des sauts de ligne. Une boucle sur un sommet i est codée par i-i. Les arêtes multiples sont codées par la répétition d'une même arête, comme par exemple i-j i-j, ou encore i-j-i (même convention pour les arcs i->j->i).

       Ex: 0 1-2-3-1            0   1
                                   / \
                                  3───2

représente un graphe à 4 sommets, composé d'un sommet isolé (0) et d'un cycle à trois sommets (1,2,3). Une représentation graphique possible est donnée à droite.

       Ex: 4-2-1-0-3-2-5

représente un graphe à 6 sommets composé d'un cycle de longueur 4 et de deux sommets de degré 1 attaché à 2. On aurait pu coder le même graphe avec l'expression 2-(1 3 4 5) 1-0-3. En voici une représentation graphique possible:

       Ex:        1
                 / \
              4-2   0
               / \ /
              5   3

Plus généralement, une famille de graphes peut être définie en précédant chaque graphe par "[n]" où n est un entier unique représentant l'identifiant du graphe.

       Ex: [17] 0-1 [22] 0->1->2->0

représente une famille composée de deux graphes: un chemin à deux sommets (d'identifiant 17) ainsi d'un cycle orienté à trois sommets (d'identifiant 22).

COMMENT FONCTIONNE LE GÉNÉRATEUR ?

Pour chaque graphe une fonction adj(i,j) est définie. Elle fournit d'adjacence (0 ou 1) entre les sommets i et j, des entiers entre 0 et n-1. Le graphe est affiché en générant toutes les paires {i,j} possibles et en appelant adj(i,j) (ou tous les couples (i,j) possibles dans le cas orienté). Les graphes sont ainsi générés de manière implicite. Les arêtes du graphe ne sont pas stockées en mémoire, mais affichées à la volée. Ceci permet de générer des graphes de très grande taille sans nécessiter O(n²) espace de mémoire centrale. Pour certains graphes cependant, comme les arbres aléatoires, les graphes géométriques ou certains graphes d'intersections, une structure de données en O(n) peut être utilisée. Pour les formats d'affichage liste, matrix, et smatrix une structure de données de taille linéaire (en O(n+m) où m est le nombre d'arêtes) est utilisée en interne. Pour la génération de très grand graphe, le format standard ou dot doit être privilégié.

COMMANDES EXTERNES

Le programme fait appel, pour certaines fonctions, aux commandes systèmes suivantes qui doivent être dispnibles: sed, grep, awk, more, sort, dot.

OPTIONS

-help [word]
? [word]
[option|graph] ?

Affiche l'aide en ligne qui est contenue dans le fichier source du générateur. Pour cela, le code source .c doit être dans le même répertoire que l'exécutable. Si "word" est précisé, alors les options et noms de graphe contenant "word" sont affichés. La variante "[option|graph] ?" affiche une aide détaillée sur une option ou un graphe précis.

       Ex: gengraph ? arbre
           gengraph ktree ?
	   gengraph ? hedron
	   gengraph ? planaire

La forme ? peut ne pas fonctionner correctement si un fichier d'un seul caractère existe dans le répertoire courant (à cause de l'interprétation du shell). Il faut alors utiliser '?' au lieu de ?.

-list

Affiche la liste des graphes et leurs paramètres qu'il est possible de générer. Sont listés d'abord les graphes de bases puis les composés. On obtient une aide sur un graphe particulier si son nom est suivit de " ?" ou si ses paramètres éventuelles sont absents (dans ce cas il doit être le dernier mot de la commande).

       Ex: gengraph -list | sort
	   gengraph gabriel

-version

Affiche la version courante du générateur (en fait du programme source), un réel > 1. Pour cela, le code source .c doit être dans le même répertoire que l'exécutable.

-directed
-undirected

L'option -directed produit le graphe orienté en testant les n² arcs possibles, l'option -undirected permettant de revenir à la situation par défaut, soit en testant les n(n-1)/2 paires de sommets. Les boucles peuvent être testées ou pas grâce à l'option -loop. En format standard ou dot, un arc apparaît comme i->j au lieu de i-j ou i--j pour une arête. Tous les graphes ne sont pas forcément définis pour fonctionner comme espéré avec l'option -directed car certaines fonctions d'adjacence supposent que i<j et l'option par défaut (-undirected). Avec -directed, la plupart des graphes vont apparaître comme orientés symétriques. L'option -directed active l'option -loop 1.

       Ex: gengraph clique 5 -directed
           gengraph cycle 5 -directed

-not

Inverse la fonction d'adjacence, et donc affiche le complément du graphe. Cette option est prioritaire sur l'option -redirect.

-loop p

Supprime (p=0), autorise (p=1) ou force (p=2) les boucles du graphe généré. L'option par défaut pour les graphes non-orientés est p=0, et pour les graphes orientés c'est p=1. Pour qu'une boucle apparaise avec p=1, il faut que le graphe définisse l'adjacence i-i ou i->i. Pour p=2, une boucle à chaque sommet sera générée, même si le graphe ne définit pas cette adjacence. L'option -loop étant modifiée par -(un)directed, elle doit être placée après pour avoir un effet.

       Ex: gengraph cycle 5 -loop 2
           gengraph cycle 5 -directed -loop 1
           gengraph cycle 5 -directed -loop 2

-dele p

Permet de supprimer chaque arête du graphe générée avec probabilité p.

-delv p

Similaire à -dele p mais concerne les sommets. Chaque sommet, et ses arêtes incidentes, est alors supprimés avec probabilité p. Si p est un entier <0, alors exactement |p| sommets sont supprimés uniformément aléatoirement. Dans tous les cas, si k sommets sont supprimés, alors le nom des sommets restant est dans l'intervalle [0,n-k[ où n est le nombre de sommets initial du graphe. Les noms des sommets sont donc éventuellement renumérotés. Voir aussi les options -permute et -shift. Bien sûr la fonction d'adjacence est appliquée sur les noms (i,j) originaux.

-redirect p

Redirige chaque arête uniformément avec probabilité p. Plus précisément, si {i,j} est une arête du graphe original G, alors avec probabilité p l'arête affichée est {i,k} au lieu de {i,j} où k est un sommet choisi uniformément parmi les sommets du graphe G. Si l'arête {i,j} est supprimée par -dele ou si le sommet i est supprimé par -delv, la redirection n'a pas lieu. Cette option est appliquée après l'option -not. Le graphe G tient donc compte de -not avant de rediriger ses arêtes.

-star n

Ajoute n sommets pendant (degré 1) aux sommets du graphe. Si n>0, alors n représente le nombre total de sommets ajoutés, chacun des n sommets étant connectés aléatoirement uniformément aux sommets du graphe original. Si n<0, alors |n| sommets sont ajoutés à chacun des sommets du graphe. [Cette option n'est plus effective depuis v4.5. Elle le sera de nouveau dans une prochaine version.]

-apex n

Ajoute n sommets universels, donc connectés à tous les sommets du graphe. [Cette option n'est plus effective depuis v4.5. Elle le sera de nouveau dans une prochaine version.]

-seed s

Permet d'initialiser le générateur aléatoire avec la graine s, permettant de générer plusieurs fois la même suite aléatoire. Par défaut, la graine est initialisée par une combinaison du numéro de processus de la commande et le temps. Donc le programme génère par défaut des suites différentes à chaque lancement. Le générateur est initialisé lorsque l'option est lue sur la ligne de commande. Le comportement du programme peut donc être affecté suivant son ordre d'apparition. Cependant le graphe est généré après l'analyse de la ligne de commande.

-width m

Limite à m le nombre d'arêtes et de sommets isolés affichés par ligne. Cette option n'a pas de signification particulière en dehors des formats standard et dot. Par exemple, -width 1 affiche une arrête (ou un sommet isolé) par ligne. L'option -width 0 affiche tout sur une seule ligne. La valeur par défaut est 12.

-shift s

Permet de renuméroter les sommets à partir de l'entier s positif. La valeur par défaut est -shift 0. L'intérêt de cette option est de pouvoir réaliser des unions de graphes simplement en renumérotant les sommets et en concaténant les fichiers aux formats standard ou list. Cette option n'a pas d'effets pour les formats de sortie de type matrice.

-permute

Permute aléatoirement uniformément le nom des sommets lorsqu'ils sont affichés (ou chargés en mémoire dans le cas d'options -check), et donc après la génération du graphe. Les numéros restent dans l'intervalle initial qui, sauf si l'option -shift a été utilisée, est [0,n[ où n est le nombre de sommets du graphe réellement généré. Voir aussi l'option -label.

-header

Affiche un préambule donnant certaines informations sur le graphe, sous forme de commentaire à la C++ (//). Par défaut aucun préambule n'est affiché. Les informations affichées sont: - l'heure, la date et la graine du générateur aléatoire - la ligne de commande qui a produit la génération du graphe - le nombre de sommets, d'arêtes, le degrés maximum et minimum Pour les formats standard et dot, le nombre d'arêtes (et les degrés min et max) n'est pas déterminé avant l'affichage du graphe. Pour cette raison ces nombres ne sont affichés qu'après le graphe. Pour n'avoir que les informations sur le graphe, utiliser -header avec l'option -format no. Voir aussi -check info.

-caption title

Permet d'ajouter une légende à un graphe. Cette option n'a d'effet qu'avec le format dot et ces variantes. Il est possible d'afficher la "seed" avec le format %SEED. On ne peut avoir plus d'une occurrence du même format (%SEED) dans cette option.

       Ex: gengraph gabriel 30 -caption ex1 -visu
           gengraph gabriel 30 -caption "Exemple 2" -visu
           gengraph gabriel 30 -caption "graph with seed=%SEED" -visu

-fast

Génère le graphe sans tester les O(n²) arêtes possibles, mais en utilisant directement la liste d'adjacence du graphe préalablement générée lors de l'initialisation du graphe, comme c'est le cas pour les graphes basés sur "load" (load, mst, bdrg, ...) ou sur une "k-orientation" (arboricity, kpage, planar, expander, ...). Le résultat est une génération du graphe en temps O(n+m) au lieu de O(n²) au détriment d'un espace mémoire O(m+n) supplémentaire. Le temps pris par chacun des deux types de génération peut être mesuré avec -check info. Voir aussi "loadc".

       Ex: gengraph load file -fast -delv 0.3 -check ncc

Cet exemple permet de calculer le nombre de composantes connexes sur un sous-graphe contenu dans un fichier le tout en temps linéaire. D'autres graphes peuvent supporter une génération rapide si elle est implantée dans l'initialisation de la fonction d'adjacence. Certaines options, comme -not et -loop 2, n'ont plus d'effet en présence de -fast. Cependant, -permute, -delv, -dele, et d'autres fonctionnent normalement.

-variant v

Permet de passer un entier v pour contrôler certaines fonctionnalités du générateur, la valeur par défaut étant v=0. Par exemple, "-variant 1 -check routing cluster -1" permettra de calculer une variante du schéma de routage "cluster". Seule la dernière occurence de l'option -variant est prise en compte.

-check [parameters]

Stocke en mémoire le graphe généré sous la forme d'une liste d'adjacence, et lui applique un algorithme. Le graphe est généralement affiché, sauf pour certaine options comme -check maincc ou -check routing. Utiliser "-format no" pour ne pas afficher le graphe généré. Cette option nécessite un espace supplémentaire en O(n+m) pour le stockage du graphe avant application de l'algorithme.

-check info

Affiche quelques caractéristiques du graphe, après avoir effectué un tri puis un simple parcours de ses listes d'adjacences. Indique, par exemple, si le graphe est orienté, s'il contient des boucles, des multi-arêtes, etc. Le graphe lui-même n'est pas affiché. Indique aussi l'occupation mémoire du graphe, le temps de génération ou de chargement et le temps de parcours.

-check simplify

Permet de simplifier un graphe en supprimant les boucles et multi-arêtes, ceci par un simple parcours du graphe après un tri de ses listes d'adjacences. Les arêtes sont affichées au format standard une par ligne, comme avec -width 1 -format standard. Cette option est un moyen rapide de sortir un graphe au "bon" format. Elle est insensible aux options d'affichage, en particulier -format. Il est possible de ne pas supprimer les boucles en utilisant -loop 0.

          Ex: gengraph loadc G -check simplify > H
	      gengraph load G -fast -permute -check simplify > H

La différence avec "gengraph load G > H", qui produit aussi une sortie valide, est qu'avec "gengraph loadc G -check simplify > H" le graphe G est lu et affiché en temps quasi-linéaire sans la (re)génération de ses arêtes en temps O(n²).

-check bfs s

Effectue un parcours en largeur d'abord sur le graphe généré depuis le sommet s. La distribution des distances depuis s est affichée, ainsi que l'arborescence (-1 indique que le sommet n'a pas de père). La longueur du plus petit cycle passant par s est aussi donnée. Elle vaut -1 s'il n'existe pas.

-check bellman s

Calcule les plus courts chemins depuis le sommet s par l'algorithme de Bellman-Ford. Si le graphe est géométrique, le poids de chaque arête correspond à la distance euclidienne entre ses extrémités, sinon il vaut 1 et le résultat sera similaire à un bfs. Dans le cas géométrique, l'étirement maximum depuis s est calculé, ainsi qu'un chemin le réalisant. L'implémentation à l'aide d'une file prend un temps linéaire en pratique.

-check stretch

Calcule, comme -check bellman s, l'étirement d'un graphe géométrique depuis chaque source s. On affiche une source atteignant l'étirement maximum, mais aussi une source atteignant l'étirement minimum, ainsi qu'un chemin réalisant ces étirements. Utilisez l'option "-format no" pour ne pas avoir l'affichage de la génération du graphe.

-check volm

Calcule la distribution du volume monotone des sommets. Le volume monotone d'un sommet u est le nombre d'arcs du sous-graphe des sommets accessibles depuis u dans le graphe où seuls les arcs u->v avec u<v ont été gardés. Cette mesure dépend de la numérotation des sommets. À utiliser en combinaison dans l'option -permute.

-check ball r

Calcule la distribution du nombre de sommets des boules fermées de rayon r des sommets.

          Ex: gengraph tree 1000 -format no -check ball 3

-check ncc
-check connected

Donne le nombre de composantes connexes, leur taille s'il y en a plusieurs, ainsi que le nombre de sommets d'articulations (cut-vertex) du graphe. Ces informations sont aussi affichées par -check dfs 0.

-check dfs s

Effectue un parcours en profondeur d'abord de toutes les composantes connexes du graphe généré depuis le sommet s. Complète l'affichage de -check ncc en affichant en plus l'arborescence (-1 indique une racine) ainsi que la distribution de profondeur des sommets.

-check deg
-check edge
-check edges

Affiche la distribution des degrés et le nombre d'arêtes du graphe.

-check degenerate

Donne la dégénérescence du graphe, ainsi que l'ordre d'élimination correspondant des sommets.

-check girth

Donne la maille du graphe dans le cas non orienté. La valeur -1 est renvoyée si le graphe est acyclique, et la valeur 0 dans le cas orienté.

-check diameter

Calcule le diamètre du graphe généré. Affiche +∞ pour un graphe non connexe.

-check radius

Calcule le rayon du graphe généré, soit la hauteur minimum d'un arbre couvrant. Affiche +∞ pour un graphe non connexe.

-check gcolor

Donne une borne supérieure sur le nombre chromatique du graphe en utilisant l'heuristique du degré minimum.

-check kcolor k

Donne une k-coloration du graphe (et la couleur pour chaque sommet), si c'est possible. Pour cela une recherche exhaustive de toutes les k-colorations est effectuée. Le temps est raisonnable si k=3 et n<20.

-check kcolorsat k

Donne une formulation SAT de la k-coloration du graphe. Il s'agit de la formulation multi-valuée classique, un sommet pouvant avoir plusieurs couleurs sans que cela nuise à la validité du résultat. Les contraintes sont décrites au format Dimacs CNF. On peut alors envoyer le résultat à un solveur SAT comme MiniSat ou Glucose. Le graphe n'est pas affiché, et donc "-format no" n'est pas nécessaire.

          Ex: gengraph linial 6 3 -check kcolorsat 3 | glucose -model

-check kindepsat k

Donne une formulation SAT d'un ensemble indépendant de taille k du graphe. Les variables i=1 à n indiquent si le sommet numéroté i-1 est dans la solution ou pas. Les contraintes sont décrites au format Dimacs CNF. On peut alors envoyer le résultat à un solveur SAT comme MiniSat ou Glucose. Le graphe n'est pas affiché, et donc "-format no" n'est pas nécessaire.

Pour le problème clique de taille k, il suffit de chercher un ensemble indépendant de taille k pour le complément du graphe. Et pour le problème "vertex cover" de taille k, c'est un ensemble indépendant de taille n-k sur le complémentaire qu'il suffit de chercher.

-check ps1
-check ps1b
-check ps1c
-check ps1x n u_1 v_1 … u_n v_n

Applique le test ps1 ou l'une de ses variantes (voir -filter ps1 pour plus de détail sur ce test). Affiche aussi le nombre de tests réalisés (nombre de paires de sommets et de chemins testés).

-check paths x y

Liste tous les chemins simples entre les sommets x et y. N'affiche rien si x et y ne sont pas connectés. L'ordre est défini suivant le premier plus court chemins dans l'ordre des sommets depuis le sommet x.

-check iso H

Teste si le graphe généré G est isomorphe à H. Ici H est un fichier de graphe au format standard ou bien - pour l'entrée standard. Si oui, l'isomorphisme de G à H est donné. Le nombre de tests affichés est le nombre de fois où les graphes sont comparés, la comparaison prenant un temps linéaire en la taille des graphes. Plus les graphes sont symétriques (comme un cycle ou un hypercube), plus le nombre de tests sera important.

          Ex: gengraph linial 4 2 | gengraph linialc 4 2 -check iso -

C'est exemple prend ~ 500 000 tests, soit 0"05 environ, pour ce graphe 4-régulier avec 12 sommets. Tester l'isomorphisme entre deux cycles de 8 sommets étiquetés aléatoirement prend environ 4 mille tests, et entre deux cycles de 12 sommets, 30 millions de tests soit 9" environ. Pour deux arbres à 75 sommets (aléatoires mais isomorphes), moins de 20 tests suffisent. En revanche, le teste pour des graphes arêtes et sommets transitifs à 16 sommets, comme "gpetersen 8 3" et "haar 133", est hors de portée.

-check sub H
-check span H

Teste si le graphe généré G est un sous-graphe couvrant de H (donc avec le même nombre de sommets). Ici H est un fichier de graphe au format standard ou bien - pour l'entrée standard. S'ils ont le même nombre d'arêtes, le test est équivalent à l'isomorphisme. Le nombre de tests est le nombre total de fois où deux graphes sont comparés. On peut tester si H est Hamiltonien en prenant pour G un cycle.

Tester un cycle de longueur 12 dans une grille 3x4 prend jusqu'à environ 32 millions de tests (parfois bien moins), soit au plus 10".

-check isub H

Teste si le graphe généré G est un sous-graphe induit de H. Contrairement à l'option -check sub, G et H n'ont pas forcément le même nombre de sommets. Ici H est un fichier de graphe au format standard ou bien - pour l'entrée standard.

-check minor H

Teste si le graphe G généré contient H comme mineur. Ici H est un fichier de graphe au format standard ou bien - pour l'entrée standard. Les graphes peuvent être non connexes. S'ils ont le même nombre de sommets le test est équivalent à celui du sous-graphe (voir -check sub). Dans le cas positif, un modèle de H dans G est fourni. Ci-dessous l'exemple teste si le graphe H = cube est un mineur de G = K_{3,7}. La réponse est non, après 2 729 118 tests en 16" environ.

          Ex: gengraph cube | gengraph bipartite 3 7 -check minor -

Le principe consiste à contracter des arêtes de G, de toutes les manières possibles, et à tester si H est un sous-graphe du graphe contracté. Le nombre de tests affichés est le nombre de contractions plus le nombre total de tests réalisés par les tests de sous-graphe. Pour H=K₄ il est préférable d'utiliser -check twdeg qui donne < 3 ssi le graphe ne contient pas K₄ comme mineur.

-check twdeg

Donne une borne supérieure et inférieure sur la treewidth du graphe. Pour la borne supérieure, on utilise l'heuristique du sommet de degré minimum que l'on supprime et dont on complète le voisinage par une clique. En cas d'égalité (même degré) on sélectionne le sommet dont il faut rajouter le moins d'arêtes. La borne inférieure qui est donnée provient de la dégénérescence. La treewidth est exacte si 0,1 ou 2 est retourné. L'algorithme est en O(n²).

-check tw

Calcule la treewidth du graphe en analysant tous les ordres d'éliminations. La complexité est donc en n!. Il ne faut l'utiliser que si le nombre de sommets est < 12 (Ex: gengraph random 12 .5 -check tw donne 5 en environ 750 millions de tests). Parfois, l'utilisation de -permute peut accélérer le traitement, car partir d'un ordre d'élimination déjà bon permet d'éliminer rapidement beaucoup d'ordres possibles.

-check maincc

Affiche, dans le mode standard seulement, le graphe correspondant à la composante connexe ayant le plus grand nombre de sommets. Le graphe initial n'est pas affiché. Les sommets sont renumérotés si le graphe initial n'était pas connexe. Attention ! l'affichage de la composante n'est sensible qu'à l'option -width. En particulier il n'est pas possible d'afficher la composante dans un autre format (-format) ou avec les noms originaux (-label). Cependant, avec "-check maincc | gengraph load -" on peut afficher le graphe dans le format souhaité, ou ajouter -visu. (Voir aussi le raccourcis -maincc.)

Notez que "-check maincc -visu" provoque une erreur, car -visu applique l'option "-format dot" incompatible avec -check maincc.

-check subdiv n

Affiche, dans le mode standard seulement, une subdivision uniforme du graphe telle que chaque arête possède n nouveaux sommets. Les variantes suivantes sont possibles, sélectionnables via l'option -variant v, m étant le nombre d'arêtes du graphe initial:

v=0: subdivision uniforme, chaque arête comprenant n nouveaux sommets. C'est la valeur par défaut.

v=1: subdivision comprenant un total de n nouveaux sommets répartis aléatoirement uniformément sur les m arêtes du graphe.

v=2: comme ci-dessus sauf que chaque arête est subdivisée au moins une fois (il faut donc que n≥m).

Si n<0, alors c'est équivalent à mettre |n·m| comme paramètre. Notez que "-check subdiv n -visu" provoque une erreur, car -visu applique l'option "-format dot" incompatible avec -check subdiv.

          Ex: gengraph clique 4 -check subdiv -30 | gengraph load - -visu

-check prune d

Affiche, dans le mode standard seulement, le sous-graphe obtenu en supprimant récursivement tous les sommets de degrés ≤ d.

          Ex: gengraph mesh 10 10 -delv .3 -check prune 1 | gengraph load - -visu

-check routing [hash h] [scenario [nomem] s] scheme [parameters]

Construit les tables de routage pour le graphe selon le schéma de routage "scheme", ce schéma pouvant comporter des paramètres spécifiques. La sortie consiste en statistiques sur les tables (taille, temps de calcul) et le graphe. L'option "scenario" permet en plus de tester certains types de routage (s) sur le graphe et d'afficher des statistiques sur les longueurs de routes générées (dont l'étirement). L'option "hash" permet de préciser la fonction de hashage (h) appliquée le cas échéant aux sommets souvent utilisés dans les schémas de type "name-independent". Le graphe doit être connexe et comporter au moins une arête, propriétés qui sont toujours testées.

          Ex: gengraph -permute rplg 200 2.3 -maincc > G1
	      gengraph loadc G1 -check routing scenario all cluster -1

L'option "nomem" après "scenario" permet d'optimiser la mémoire en ne stockant pas les distances calculées pour établir l'étirement (par défaut elles le sont). En contrepartie le temps de calcul est allongé. Cela peut avoir un intérêt si le graphe est très grand (n ≃ 1.000.000 sommets) et qu'un scenario comme "pair -1000" est testés. Les scenarii possibles sont (n=nombre de sommets du graphe):

scenario none → aucun routage (scenario par défaut)
scenario all → n(n-1) routage possibles
scenario edges → tous les routages entre voisins
scenario npairs → n paires aléatoires de sommets différents
scenario one u → n-1 routages depuis u (choix aléatoire si -1)
scenario pair u v → routage de u à v (choix aléatoire si -1)
scenario pair -p → routage depuis p>0 paires aléatoires
scenario until s → routage jusqu'à l'étirement s ou plus

Les fonctions de hachages h:[0,n[->[0,k[ possibles sont: (shuffle et mod atteignent le nombre de collisions minimum de ⎡ n/k⎤)

hash prime → h(x)=((a·x+b)%p)%k où 0<a,b<p sont aléatoires et p=2^31-1 est premier (hash par défaut)
hash mix → h(x)=mix(a,b,x)%k où a,b sont aléatoires sur 32 bits et mix() la fonction mélange de Bob Jenkins (2006)
hash shuffle → h(x)=𝜋(x)%k où 𝜋(x) est une permutation de [0,n[ basée sur deux entiers aléatoires de [0,n[.
hash mod → h(x)=(x+a)%k où a est aléatoire dans [0,k[.

-check routing cluster k

Schéma de routage name-independent "cluster" de paramètre k. Un sommet de degré maximum est choisi comme "centre", puis k-1 de ces voisins de plus haut degrés sont choisis pour former un cluster de taille au plus k. Un arbre BFS est enraciné depuis le centre. Chaque sommet possède une boule par rayon croissant qui s'arrête avant de toucher un sommet du cluster. On route de u vers v d'abord dans la boule de u. Sinon on va dans le cluster pour chercher un sommet du cluster responsable du hash de v. Une fois atteint on route selon l'arbre BFS ou selon un plus court chemin si la distance à la destination est ≤ logn/loglogn. Les sommets ayant un voisin dans le cluster et qui ne sont pas eux-mêmes dans le cluster possèdent dans leur table tout leur voisinage. Les boules sont optimisées par l'usage d'un voisin par défaut.

Si k=-1, alors k est initialisé à ⎡ √n⎤. Si k=-2 il est initialisé à n si bien que le cluster est fixé à tout le voisinage du centre. Dans tous les cas, l'étirement est toujours ≤ 5. Il est même ≤ 3 si k=1. La taille des tables est réduit dans le cas de graphes power-law (comme RPLG). Il existe plusieurs variantes (option -variant v) où chacun des bits de v mis à 1 est interprété comme suit:

bit-0: le routage est réalisé sans les boules de voisinages ce qui réduit la taille moyenne mais augmente l'étirement maximum.

bit-1: le routage dans le cluster est réalisée dans l'étoile couvrant le cluster, sans les autres arêtes du cluster. Cela réduit la taille des tables sans modifier l'étirement maximum. Si de plus k=1, le routage est alors réalisé via la racine de l'arbre BFS ce qui réduit au minimum la taille moyenne des tables (2 en moyenne).

bit-2: les tables des sommets voisins du cluster sont vides. L'étirement devient ≤ 7 au lieu de 5 au maximum, mais la taille des tables est réduite.

bit-3: les tables des sommets voisins du cluster ne contiennent que des sommets qui ne sont pas de le cluster. L'étirement ≤ 5 est préservé, mais généralement la taille maximum des tables est réduite, l'étirement moyen augmentant que très légèrement.

-check routing dcr k

Schéma de routage name-independent "dcr" de paramètre k>0 représentant le nombre de couleurs. C'est une simplification du schéma "agmnt". L'étirement est toujours ≤ 5 et le nombre d'entrées des tables est en moyenne f(k,n) = 2n/k + (k-1)·(H(k)+1) où H(k) ~ ln(k)+0.577… est le k-ième nombre harmonique. Le principe du schéma est le suivant. Chaque sommet possède une couleur, un entier aléatoire de [0,k[, les sommets landmarks étant ceux de couleur 0. Les boules de voisinages des sommets sont définies par volume comme la plus petite boule contenant au moins chacune des couleurs (ou tous les sommets s'il manque une couleur n'est pas représentée), les sommets du dernier niveau étant ordonnés par identifiant croissant. Le routage s→t s'effectue selon un plus court chemin si t est dans la boule de s ou si t est un landmark. Sinon, on route vers le sommet w de la boule de s dont la couleur est égale au hash de t, une valeur aussi dans [0,k[. Puis le routage w→t s'effectue dans l'arbre BFS enraciné dans le plus proche landmark de s ou de t, celui minimisant la distance de w à t.

Si k=-1, alors k est initialisé à sa valeur optimale théorique, celle qui minimise le nombre moyen d'entrées f(k,n), valeur calculée numériquement et qui vaut environ k ≃ √(n/ln(n))/2, ce qui donne environ 2√(n·ln(n·ln(n))) entrées en moyenne. Si k=-2, le nombre de couleur est initialisé à n. Les valeurs de k>n sont possibles, il s'agit alors d'un routage de plus court chemins comme pour le cas k=n ou k=1. Il existe une variante (-variant 1) lorsque k>1 qui a pour effet de choisir les landmarks comme les sommets de plus haut degré. Plus précisément, les ⎡ n/k⎤ sommets de plus haut degré sont coloriés 0 et les autres coloriés aléatoirement dans [1,k[. Dans cette variante, la borne sur l'étirement est toujours garantie mais plus sur le nombre maximum d'entrées. Cependant, pour certains graphes l'étirement moyen est amélioré.

-check routing agmnt k

Schéma de routage name-independent dit "agmnt" du nom de ces auteurs Abraham et al. (2008). C'est la version originale du schéma "dcr" qui diffère par l'algorithme de routage. Comme dans "dcr", le routage s→t s'effectue directement vers t si t est dans la boule de s ou est un landmark. Sinon, vers le sommet w de la boule de s dont la couleur est égale au hash de t. Le routage w→t s'effectue suivant la meilleure des options suivantes: router via un arbre BFS d'un des landmarks; ou bien router via un arbre couvrant la boule d'un sommet s' contenant à la fois w et un sommet x voisin d'un sommet y contenu dans la boule de t (les boules s' et de t, si elles existent, sont dites "contiguës via l'arête x-y"). L'étirement est toujours ≤ 3 et les tables ont le même nombre d'entrées que "dcr", bien que plus complexes. Le temps de calcul des tables est plus important que pour "dcr". Toutes les variantes de "dcr" (-variant, k<0) s'appliquent aussi à "agmnt".

-check routing tzrplg t

Schéma de routage étiqueté inspiré de celui de Thorup & Zwick (2001) optimisé pour les Random Power-Law Graphs (voir prlg) de paramètre réel t (power-law exponent) et proposé par Sommer et al. (2012). L'étirement est toujours ≤ 5. Les valeurs de t entre ]0,1.5] sont interdites. Le schéma utilise des sommets landmarks où des arbres BFS sont enracinés, ainsi que des boules (de voisinage) définies par rayons croissant qui s'arrête avant de toucher un landmark. Le routage s'effectue alors en priorité via les boules ou alors via le landmark le plus proche de la destination (sans raccourcis), information précisée dans l'étiquette de la destination. Les landmarks sont les sommets de plus haut degré. Par défaut (-variant 0) leur nombre vaut:

si t>1.5, ⎡ n^((t-2)/(2t-3))⎤
si t=0, ⎡ √n⎤
si t<0, |t|

Si -variant 1 et t>1.5, alors les landmarks sont tous les sommets de degré > n^1/(2t-3). Si -variant 2 et t>0, alors les landmarks sont t sommets choisis aléatoirement. L'étirement est ≤ 3 si un seul landmark est choisi.

-check routing hdlbr k

Schéma de routage name-independent HDLBR selon Tang et al. (2013) avec k>0 landmarks qui sont les sommets de plus haut degré. Si k<0, alors k est initialisé à ⎡ √n⎤. Chaque sommet qui n'est pas un landmark possède une boule dont le rayon est juste inférieure au plus proche landmark. Chaque sommet possède sa boule boule inverse (qui peut être vide), définie comme l'ensemble des sommets le contenant dans leur boule. Chaque landmark a une couleur unique. On route directement de u à v si v est dans la boule de u, la boule inverse de u, ou si v est un landmark. Sinon, on route vers le landmark (selon un plus court chemin) dont sa couleur vaut le hash de v. Delà on route suivant un plus court chemin vers le plus proche landmark de v, l(v). On utilise ensuite le next-hop de l(v) vers v, un sommet nécessairement contenant v dans sa boule inverse. À chaque étape du routage, si v est dans la boule ou boule inverse du sommet courant, on route directement vers celui-ci. La longueur de route entre u et v est au plus 2d(u,v)+2r, où r est la distance maximum entre deux landmarks. La valeur de r est bornée par une constante pour k ≃ √n et pour les Random Power-Law Graphs (voir rplg).

-check routing bc k

Schéma de routage étiqueté selon Brady-Cowen (2006). L'étirement est additif ≤ 2k, et donc multiplicativement ≤ 2k+1. En particulier, si k=0, il s'agit d'un routage de plus court chemin. Il est adapté aux Power-Law Random Graphs (voir plrg). Le principe est le suivant: on construit un arbre BFS (=T) enraciné dans un sommet (=r) de plus haut degré. Le coeur (=C) est la boule de rayon k depuis r. On construit une liste (=L) de BFS couvrant G ainsi qu'une forêt (=H) de BFS de G comme suit. Au départ, L={T}, et H est la forêt T\C. Puis, pour chaque arête {u,v} de G\C\T, on vérifie si l'ajout de {u,v} à H crée un cycle ou pas. Si c'est non, on met à jour la forêt H en lui ajoutant {u,v}. Si c'est oui, on calcule un BFS de G de racine u (ou v) qu'on ajoute à L. Une fois le calcul de H terminé, on calcule une forêt BFS couvrante de H qu'on ajoute à L. L'algorithme de routage de u à v consiste simplement à router dans l'arbre de L qui minimise la distance de u à v.

-filter family[:range] [not] test [parameters]

Affiche les graphes d'une famille pour lesquels le test est vrai (ou faux si "test" est précédé de "not"). Le paramètre "family" est un nom de fichier ou "-" pour l'entrée standard. La lecture de la famille se fait en temps linéaire. Il contient la famille de graphes (ou un graphe seul) au format standard. La première ligne affichée contient le nombre de graphe de la famille résultante. L'affichage de chaque graphe est influencé par l'option -width qui doit être placée avant -filter. La variante "family:range" permet de sélectionner les graphes de la famille dont les identifiants sont spécifiés par "range", comme par exemple "family:5-8" qui sélectionne les graphes d'identifiant 5,6,7,8. De manière générale, "range" est un ensemble de valeurs selon le format "value" décrit ci-après (voir aussi -filter F id value). La variante "-:range" est possible.

Dans la suite, la présence de "value" dans les paramètres d'une option représente un ensemble de valeurs entières possibles. Par exemple, -filter F vertex '>5' filtre les graphes de la famille F comportant plus de 5 sommets. De manière générale, "value" est une suite d'intervalles d'entiers séparés par des "," (interprétées comme "ou"), chaque intervalle étant codé comme suit:

<x → valeur inférieure à l'entier x
>x → valeur supérieure à l'entier x
x ou =x → valeur égale à l'entier x
x-y → valeur dans l'ensemble d'entiers {x,…,y}
t → toujours vrai (intervalle infini)
p → affiche la valeur plutôt que le graphe

       Ex: -filter F vertex '5,7-13,>100'
           -filter F vertex '5-10,p'
           -filter F edge p
           -filter F id 5,7
           -filter F vertex p | head -1
           -filter … p | grep '^\[' | sort -rnk 3 | head
           -filter … p | grep '^\[' | sort -nk 3 | head

Le premier exemple filtre les graphes de la famille F ayant un nombre de sommets n vérifiant soit n=5, soit 7 ≤ n ≤ 13, ou soit n>100. L'exemple 2 affiche le nombre de sommets des graphes ayant entre 5 et 10 sommets. L'exemple 3 affiche le nombre d'arêtes de chaque graphe. L'exemple 4 affiche les graphes d'identifiant 5 et 7 de la famille F. L'exemple 5 affiche le nombre de graphes de la famille (ce qui correspond à la première ligne de commentaires). Les deux derniers exemples permettent d'avoir le maximum/minimum de "value".

Si "value" contient le symbole > ou < il est alors préférable de mettre des quotes ('>14' par exemple) pour que la commande soit correctement interprétée par le shell.

La différence principale avec -check est que le résultat de -filter est non verbeux alors que -check, qui ne s'applique pas a priori sur des familles de graphes mais sur un graphe seul, peut donner des explications sur l'exécution de l'algorithme dont la sortie n'est pas forcément un ou une liste de graphes. Aussi, avec -check l'algorithme s'applique au graphe généré, donc après un temps a priori en O(n²), alors qu'avec -filter c'est toujours à partir d'un fichier (ou de l'entrée standard), lu en temps linéaire.

-filter F id value

Filtre les graphes de F dont l'identifiant est déterminé par value. Cela permet d'extraire un ou plusieurs graphes donnés. C'est équivalent à "-filter F:value all".

-filter F rename shift

Affiche tous les graphes de la famille en renumérotant les graphes à partir de l'entier "shift".

-filter F vertex value

Filtre les graphes de F ayant un nombre de sommets déterminé par value.

-filter F edge value
-filter F edges value

Filtre les graphes de F d'un nombre d'arêtes déterminé par value.

-filter F all (= vertex t)

Affiche tous les graphes de F ce qui permet en particulier de savoir combien il y en a en examinant la première ligne affichée.

-filter F1 minus F2

Affiche F1\F2, c'est-à-dire tous les graphes de F1 qui ne sont pas isomorphes à F2 (si F2 est un graphe) ou à l'un des graphes de F2 (dans le cas d'une famille).

-filter F1 minus-id F2

Comme "minus" mais concerne les identifiants: supprime de F1 les graphes dont l'identifiant existe dans F2 (qui peut être un graphe ou une famille de graphes). La complexité est environ (|F1|+|F2|)·log|F2|, alors que pour "minus" elle est en |F1|·|F2|·T où T est le temps pour décider si deux graphes pris dans F1 et F2 sont isomorphes.

-filter F minor[-inv] H

Filtre les graphes de F contenant H comme mineur. La variante minor-inv filtre les graphes de F qui sont mineurs de H. Si H=K₄, il est préférable d'utiliser -filter tw2.

-filter F sub[-inv] H

Filtre les graphes de F contenant H comme sous-graphe, chaque graphe de F devant avoir le même nombre de sommets que H. La variante sub-inv filtre les graphes de F qui sont un sur-graphe de H.

-filter F isub[-inv] H

Filtre les graphes de F contenant H comme sous-graphe induit. La variante isub-inv filtre les graphes de F qui sont sous-graphes induits de H.

-filter F iso H

Filtre les graphes de F isomorphes à H.

-filter F degenerate value

Filtre les graphes de F de dégénérescence déterminée par value.

-filter F forest value

Filtre les graphes de F qui sont des forêts dont le nombre d'arbres est déterminé par value.

-filter F isforest (= forest t)

Filtre les graphes de F qui sont des forêts.

-filter F istree (= forest '=1')

Filtre les graphes de F qui sont des arbres.

-filter F cycle (= not forest t)

Filtre les graphes de F contenant au moins un cycle.

-filter F degmax/degmin value

Filtre les graphes de F de degré maximum (ou minimum) déterminé par value.

-filter F deg value

Filtre les graphes de F où tous les sommets ont un degré déterminé par value. Ainsi -filter deg 4-7 filtre les graphes avec un degré minimum au moins 4 et un degré maximum au plus 7.

-filter F gcolor value

Filtre les graphes de F dont le nombre de couleurs obtenu selon l'heuristique du degré minimum est déterminé par value.

-filter F bipartite (= gcolor <3)

Filtre les graphes de F qui sont bipartis.

-filter F component value

Filtre les graphes de F dont le nombre de composantes connexes est déterminé par value.

-filter F connected (= component 1)

Filtre les graphes de F qui sont connexes.

-filter F biconnected

Filtre les graphes de F qui sont 2-connexes. Un graphe G est k-connexe s'il n'y a pas d'ensemble avec <k sommets qui déconnecte G ou laisse G avec 1 sommet. Un graphe est 2-connexe s'il est connexe, ne possède pas de sommet d'articulation et a plus de 2 sommets. Les cliques de taille k+1 sont k-connexes.

-filter F radius value

Filtre les graphes de F dont le rayon est déterminé par value. Le rayon est la profondeur du plus petit arbre couvrant le graphe. Il vaut -1 si le graphe n'est pas connexe.

-filter F girth value

Filtre les graphes de F dont la maille est déterminée par value. La maille est la taille du plus petit cycle. Elle vaut -1 si le graphe n'a pas de cycle. Elle n'est définie que si les graphes sont orientés.

-filter F diameter value

Filtre les graphes de F dont le diamètre est déterminé par value. Le diamètre vaut -1 si le graphe n'est pas connexe.

-filter F cut-vertex value

Filtre les graphes de F dont le nombre de sommets d'articulations est déterminé par value. Un sommet est un point d'articulation si sa suppression augmente le nombre de composante connexe. Les sommets de degré 1 ne sont pas des point d'articulation. Le graphe est biconnexe ssi value<1 ou si le graphe est une clique avec au moins deux sommets. On peut tester si un graphe est une clique avec -filter degmin ou -filter deg.

-filter F ps1
-filter F ps1b
-filter F ps1c
-filter F ps1x n u_1 v_1 … u_n v_n

Filtre les graphes G de la famille F dont le test ps1 est vrai, c'est-à-dire si l'évaluation de la fonction f(G,{}) décrite ci-après est vraie.

Soit P un chemin d'un graphe G tel que G\P est connexe. La fonction f(G,P) est vraie ssi G est vide (en pratique |G|-|P|<3 suffit) ou s'il existe deux sommets x,y de G où y n'est pas dans P tels que pour tout chemin Q entre x et y dans G "compatible" avec P (c'est-à-dire P et Q s'intersectent en exactement un segment) on a les deux conditions suivantes: (1) il n'y a pas d'arête entre les sommets de P\Q et de G\(Q∪P); et (2) pour toute composante connexe C de G\(Q∪P), f(C∪Q,Q) est vraie. Le test est optimisé dans un certain nombre de cas, en particulier: les arbres (toujours vrai), les cliques (vrai ssi n<5).

La variante ps1b calcule et affiche de plus un graphe des conflits (affichage modifiable par -width), chaque noeud de ce graphe correspondant à un argument (C∪Q,Q) évalué à faux par f. La valeur (ou code) d'un noeud est 0 (=lourd ou faux), 1 (=léger ou vrai) ou - (indéterminée). Suivant certaines règles, les valeurs 0 ou 1 sont propagées selon le type des arêtes du graphes des conflits. Résoudre le graphe des conflits revient à trouver une affectation des valeurs 0 ou 1 aux noeuds qui respecte (sans contradiction) toutes les règles.

La fonction f(G,{}) est évaluée à vraie si le graphe des conflits n'a pas de solution, c'est-à-dire si une contradiction a été découverte ou si pour une paire de sommets (x,y) tous ses noeuds sont à 1.

On affiche le code d'un noeud (0,1,-) ainsi que les sommets de sa composante (par ex: [237]). Les noeuds du graphe des conflits sont reliées par des arêtes typées. Les voisins v d'un noeud u sont listés avec le type de l'arête, si l'un des 4 cas suivants se produit (il n'y a pas d'arête entre u et v dans les autres cas):

v< (la composante de v est incluse dans celle de u) v> (la composante de v contient celle de u) v= (les composantes de u et v sont les mêmes) v| (les composantes de u et v sont disjointes)

Parmi les règles on trouve par exemple: si deux noeuds du graphe des conflits u=(C∪Q,Q) et v=(C'∪Q',Q') sont disjoints, c'est-à-dire C n'intersecte pas C', alors seule une des expressions f(C∪Q,Q) ou f(C'∪Q',Q') peut être fausse, pas les deux. Dit autrement, les composantes de u et v ne peuvent pas être "lourdes" (=0) toutes les deux en même temps. Et donc, si le code de u est 0, celui de v est 1. Notons que le code de u et v égale à 1 est compatible avec cette règle.

La variante ps1c est similaire à ps1b sauf que récursivement seul le test ps1 est appliqué, et pas ps1b. Le test ps1c est plus long que ps1 mais plus rapide que ps1b. La variante ps1x est similaire à ps1b sauf que les valeurs v_i sont écrites dans le noeuds u_i du graphe des conflits principal (pas ceux générés lors des appels récursifs). Plus précisément, v_1 (0 ou 1) est écrit dans le noeud u_1, puis sa valeur est propagée. Ensuite v_2 est écrit puis propagée, etc.

Dans tous les cas, si G n'est pas connexe, le résultat n'est pas déterminé.

-filter F tw value

Filtre les graphes de F selon leur treewidth. L'algorithme pour le calcul de la treewidth est assez lent. Pour les petites valeurs de tw, des alternatives sont possibles (voir -check tw et -filter tw2). Pour savoir si un graphe G est de treewidth 3 il suffit de savoir si G contient l'un des 4 mineurs suivants:

              echo "[0]"  > F; ./gengraph clique 5 >> F
	      echo "[1]" >> F; ./gengraph wagner >> F
	      echo "[2]" >> F; ./gengraph prism 5 >> F
	      echo "[3]" >> F; ./gengraph hajos >> F ; echo "0-1-2-0" >> F
	      cat G |./gengraph -filter F minor-inv - -format no

-filter F tw2

Affiche les graphes de F de treewidth ≤ 2. L'algorithme est en O(n²). Ce test peut être utilisé pour tester (plus rapidement qu'avec -filter minor) les graphes sans mineur K₄.

-filter F hyper value

Filtre les graphes de F selon leur hyperbolicité. Il s'agit de la valeur (entière) maximum, sur tous les quadruplets de sommets {u,v,x,y}, de la différence des deux plus grandes sommes parmi les sommes de distance : uv+xy, ux+vy et uy+vx. La complexité est en O(n⁴).

-format type

Spécifie le format de sortie. Il est préférable d'utiliser cette option en dernier. Les valeurs possibles pour "type" sont:

standard: format standard (liste d'arêtes), c'est le plus compact.
list: liste d'adjacence.
matrix: matrice d'adjacence.
smatrix: matrice supérieure, diagonale comprise.
vertex i: liste des voisins du sommet i.
dot: format de GraphViz qui est très proche du format standard.
dot<type>: dessine le graphe avec GraphViz et convertit au format <type>.
html: dessin dynamique au format html et vis.js (cf. http://visjs.org).
xy: positions X,Y qui ont été utilisées pour le graphe géométrique.
no: n'affiche rien, à utiliser en combinaison avec -header ou -check.

Les formats matrix/smatrix/list/vertex nécessitent de stocker le graphe en mémoire, donc nécessite un espace en O(n+m), alors que le graphe est généré à la volée pour les formats standard, dot ou html. Pour html, nécessite le script vis.min.js qui est chargé soit localement s'il existe soit sur un dépôt externe officiel sinon. Le script peut être lent pour le calcul des coordonnées à partir d'une centaine de sommets. Les valeurs les plus utilisées de <type> pour le format dot<type> sont: pdf, fig, svg, ps, jpg, gif, png (voir man dot ou faire dot -T.).

L'option -format dot<type> est équivalent à "-format dot | dot -T<type>". Par conséquent, elle doit donc être utilisée en dernier. Le filtre dot utilisé pour dessiner le graphe peut être spécifié par l'option -dot filter. L'affichage des noms de sommets est contrôlé par l'option -label.

Les positions affichées dans le format dot ([pos="…"]) diffèrent d'un facteur proportionnel à √n par rapport aux positions originales du graphe (qui peuvent être affichées par -format xy ou -label -3). Ce facteur permet de garder une taille raisonnable pour les sommets car sous dot les sommets ont une taille fixe minimale.

-vcolor option [parameters]

Ces options permettent de modifier la couleur des sommets. Ces options n'ont d'effets qu'avec le format dot (et ses variantes y compris -visu). Par défaut les sommets sont de couleur noire. Notez que les attributs par défaut des sommets (couleurs, formes, etc.) peuvent être modifiés directement par dot (voir l'option -N de dot). Cependant l'option -vcolor permet d'individualiser la couleur d'un sommet, en fonction de son degré par exemple. Ici le degré est le degré non-orienté. Il peut avoir plusieurs options -vcolor pour une même commande.

-vcolor deg[r]

La couleur dépend du degré du sommet (deg) ou du rang du degré du sommet (degr). Ainsi, les sommets de plus petit degré obtiennent la première couleur de la palette, les sommets de plus grand degré la dernière couleur de la palette, et les autres sommets une couleur intermédiaire de la palette. Donc une seule couleur est utilisée si le graphe est régulier.

-vcolor degm

Effectue une coloration propre (deux sommets voisins ont des couleurs différentes) suivant l'heuristique du degré minimum: récursivement, le sommet de degré minimum obtient la plus petite couleur qui n'est pas utilisée par ses voisins. Cela donne des colorations avec assez peu de couleurs pour les graphes de faible arboricité (planaire, tw, pw, kout, expander, …) ou de faible degré. Avec cette technique, les graphes bipartis (tree, crown, …) sont coloriés avec deux couleurs. Cette option nécessite un espace et un temps en O(n+m).

-vcolor randg

Effectue une coloration propre en utilisant un algorithme glouton sur un ordre aléatoire des sommets: récursivement, le sommet d'indice i obtient la plus petite couleur qui n'est pas utilisée par ses voisins d'indice j<i. Cette option nécessite un espace et un temps en O(n+m).

-vcolor kcolor k

Effectue une k-coloration propre du graphe, si c'est possible. Si cela n'est pas possible, la première couleur est appliquée à tous les sommets. L'algorithme (exponentiel) est le même que celui utilisé pour -check kcolor.

-vcolor pal grad

Permet de fixer la palette de couleurs utilisée par les sommets. Le paramètre "grad" est un mot sur l'alphabet [a-z] (sans les guillemets). Les caractères en dehors de cet alphabet sont ignorés. Chaque lettre correspond à une couleur de base:

           a=aquamarine     h=hotpink      o=olive         v=violet
	   b=blue           i=indigo       p=purple        w=white
	   c=cyan           j=orange       q=pink          x=gray
	   d=darkorange     k=khaki        r=red           y=yellow
	   e=chocolate      l=lavender     s=salmon        z=black
	   f=forestgreen    m=magenta      t=teal
	   g=green (lime)   n=navy         u=yellowgreen

La palette est calculée selon une interpolation linéaire entre les points définis par le mot "grad". Par exemple, si "grad" vaut rb, la palette sera composée d'un dégradé allant du rouge (r) au bleu (b). Si "grad" vaut rgbr, le dégradé ira du rouge au vert puis au bleu et enfin au rouge. Pour avoir une couleur (de base) unique, disons w, sur tous les sommets, poser "grad" égale à w. Par exemple, pour avoir tous les sommets blancs, on peut faire:

              gengraph gabriel 30 -vcolor deg -vcolor pal w -visu

La palette par défaut correspond au mot "grad" suivant: redjykugfocatbhsqvmpinzxlw. On peut visualiser la palette avec l'option "-vcolor list".

-vcolor list

Produit l'affichage de la palette des couleurs utilisées pour un graphe plutôt que le graphe lui-même. Cela permet en particulier de savoir combien de couleur ont été utilisées. La palette est générée en affichant au format dot un graphe particulier où les sommets (représentés par un rectangle) sont les couleurs utilisées. Utilisez -visu pour visualiser la palette sous forme pdf. Le nom des sommets correspond à la lettre de la couleur de base comme spécifié par -vcolor pal.

          Ex1: gengraph gabriel 50 -vcolor degm -vcolor list
	  (génère la palette utilisée pour ce graphe de Gabriel)

          Ex2: gengraph prime 53 -vcolor list
	  (un moyen simple de générer la palette par défaut)

          Ex3: gengraph clique 100 -vcolor degm -vcolor pal rb -vcolor list
          (génère un dégradé de 100 couleurs allant du rouge au bleu)

-vsize

La taille des sommets est proportionnelle à son degré, alors que par défaut elle est fixe. Cette option n'a d'effet qu'avec le format dot (et ses variantes). Elle peut être combinée avec -vcolor.

-visu
-visuh

Crée un fichier "g.pdf" (ou "g.html" pour -visuh) permettant de visualiser le graphe. Il s'agit d'un raccourci de l'option "-format dotpdf" ("-format html") qui rajoute également la redirection "> g.pdf" ("> g.html") en fin de la ligne de commande.

-maincc

Affiche la composante connexe principale du graphe, les sommets étant éventuellement renumérotés si le graphe n'est pas connexe. C'est un raccourci pour "-check maincc | gengraph load - -fast". (Voir aussi -check maincc.) Cet affichage est réalisé en temps linéaire grâce à l'option -fast. Les options placées avant -maincc affectent le graphe initial alors que celles placées après affectent la composante principale. Les options ayant un effet pour les formats hors standard (comme -vsize ou -visu) ne devraient être placées qu'après cette option.

-dot option [parameters]

Cette option permet de contrôler la sortie au format dot. Elle permet par exemple de modifier le filtre, la longueur des arêtes ou l'échelle du dessin.

-dot scale s

Spécifie le facteur d'échelle pour le format dot. Cela affecte les coordonnées des sommets et des arêtes, pas des étiquettes (sommets ou arêtes). Cela permet d'écarter les sommets les uns des autres si nécessaires. Le format pour s prend plusieurs formes: x ou x,y pour un facteur d'échelle identique ou pas en X et Y. La valeur par défaut est s=1. On peut aussi mettre "auto" qui calcule automatiquement un facteur d'échelle (symétrique en X et Y) qui vaut 1/√n ou 1/max(ΔX,ΔY) dans le cas de graphes géométriques.

          Ex: gengraph gabriel 10 -label -3 -dot scale 3,2 -visu

-dot len p

Spécifie la longueur des arêtes pour le format dot et le filtre "neato". La valeur par défaut est 1, et une valeur plus grande (comme 2.5 ou 3) allonge les arêtes et permet dans certains cas de mieux visualiser le graphe. C'est parfois nécessaire pour éviter l'intersection des sommets lorsqu'on utilise -label 1. On peut obtenir le même genre d'effet avec -dot scale.

-dot dir type

Spécifie le type d'orientation et l'affichage d'une arête pour le format dot. Cela revient à mettre l'attribut dir=type pour les arêtes. Il faut que "type" soit l'un des mots clés suivants: forward, back, both, none. L'effet est de modifier le rendu d'un arc A->B, voir d'une arête A--B, présent dans le .dot. Cela n'affecte pas les autres format. Pour type=back, c'est l'arc inverse qui sera affiché, comme si on avait mis B->A (car en dot A<-B n'est pas autorisé). C'est très utile en combinaison avec l'option -directed. Pour type=both, c'est A<->B qui sera affiché. Pour type=none, c'est A--B qu'on affiche (cas non-orienté par défaut) et pour type=forward, c'est A->B (cas orienté par défaut).

L'exemple ci-après affiche un arbre avec une orientation vers ses fils (au lieu de son père comme par défaut).

          Ex: gengraph tree 15 -label 1 -directed -dot dir back -visu

-dot filter f

Spécifie le filtre de GraphViz, c'est-à-dire l'algorithme de dessin utilisé par dot. Par défaut, le filtre est "neato". Les filtres principaux sont: dot, neato, twopi, circo, fdp, sfdp, … Faire "dot -K ." pour afficher les filtres disponibles.

-dot attr s

Ajoute un ou plusieurs attributs lors de la génération du graphe au format dot. La chaîne de caractères s est simplement ajoutée au corps du graphe avant la description des arêtes et des sommets. On peut mettre dans s autant d'attributs que l'on veut, mais on ne peut mettre qu'une seule option -dot attr. Attention ! L'ajout d'attributs d'arêtes peut provoquer la création de multi-arêtes.

         Ex: gengraph tree 20 -dot attr "0 [color=red]; 0--1 [color=blue];" -visu

-pos b

Active (b=1) ou désactive (b=0) la génération des positions des sommets pour le format dot. Cela sert à indiquer à l'algorithme de dessin dot de respecter (b=1) ou pas (b=0) les coordonnées des sommets. L'option par défaut est -pos 0, mais cette option est activée pour tous les graphes géométriques (udg, gabriel, thetagone, …).

-label b

Active (b≠0) ou désactive (b=0) l'affichage du nom des sommets pour les formats dot et standard. Les valeurs possibles de l'entier b sont b∈[-3,3]. Si b=1, il s'agit du nom original du sommet, par exemple un mot binaire pour l'hypercube. Cette fonctionnalité n'est pas implémentée pour tous les graphes, le nom par défaut étant les entiers de [0,n[ où n est le nombre de sommets du graphe généré. L'option -label 1 -visu permet alors d'afficher sur le dessin du graphe le nom des sommets. Ils ne le sont pas par défaut (b=0). L'option -label 2 -visu force l'affichage des noms sous forme d'entiers de [0,n[ et non pas du nom original (s'il était défini). L'option -label 3 permet, dans le cas de graphe géométrique (ou si -pos 1), d'afficher les coordonnées des points. Si b<0, alors l'effet est similaire à -label |b| sauf que le nom du sommet est affiché à coté du sommet et non au centre. L'option -label 1 annule l'option -permute, mais -label 2 ne le fait pas. Comme l'option -label influence -format dot<type>, -label devrait être placée avant -format.

       Ex: gengraph petersen -label 1 -width 1
           gengraph petersen -label 1 -format dot | grep label
           gengraph petersen -label 1 -dot len 2 -visu
           gengraph gabriel 30 -pos 0 -label 1 -visu
	   gengraph gabriel 30 -label -3 -dot scale 4 -xy round 2 -visu

-norm ℓ [parameters]

Fixe la norme d'un vecteur (x,y) du plan (ou la fonction de distance entre deux points du plan) pour l'adjacence de certains graphes géométriques (dont udg, gabriel, rng, nng, …). Par défaut c'est la norme Euclidienne qui est utilisé. Les valeurs possibles pour ℓ sont:

L1 → |x|+|y|, distance de Manhattan
L2 → √(x²+y²), norme Euclidienne
Lmax → max{|x|,|y|}
Lmin → min{|x|,|y|}
poly p → distance polygonale de paramètre p
hyper → distance hyperbolique

Il s'agit de pseudo-norme (ou pseudo-distance) puisque par exemple la norme "Lmin" ne vérifie pas l'inégalité triangulaire. La norme polygonale est le rayon du cercle inscrit dans le polygone régulier convexe à p cotés contenant (x,y), le polygone étant centré en (0,0) et orienté de façon à avoir son coté le plus à droit vertical. Ainsi "poly 4" correspond à la norme "Lmax". Une valeur de p<3 est interprétée comme p=+∞ ce qui correspond à la norme Euclidienne. Attention ! la norme "poly p" n'est pas toujours symétrique, lorsque p est impair par exemple. La norme (ou distance) hyperbolique n'est définie que pour des points du disque ouvert unité centré en (0,0).

-xy option [parameters]

Cette option contrôle la façon dont sont générées les coordonnées des sommets d'un graphe géométrique. Par défaut les positions sont tirées aléatoirement uniformément dans le carré [0,1[², mais cela peut être changé grâce à -xy. Notez bien que, même si c'est improbable, deux sommets peuvent avoir les mêmes positions (voir l'option -xy unique). Il est possible de visualiser les points issus des options -xy (voir le graphe "point n"). La présence d'une option -xy active l'option -pos et rend le graphe géométrique comme:

       Ex: gengraph path 20 -xy unique -visu

-xy load file

Charge les positions à partir du fichier "file" ou de l'entrée standard si file=-. Cela permet de tester les adjacences d'un graphe géométrique à partir de positions pré-déterminées. Le format est celui de -format xy.

          Ex: gengraph gabriel 10 -xy load file.pos

Le nombre de sommets du graphe est déterminé par le fichier et non par les paramètres du graphe. Cette option n'a d'effet que pour les graphes géométriques. La structure du fichier texte doit être:

                 n
		 x_1 y_1
		 x_2 y_2
		 …
		 x_n y_n

où n est le nombre de positions. Les positions x_i y_i ne sont pas forcément dans l'intervalle [0,1[. Notez qu'avec l'option -format xy, il est possible d'effectuer la transformation d'un fichier de positions. L'exemple suivant normalise les coordonnées du fichier g.pos dans le carré unité:

          Ex: gengraph -xy load g.pos -xy box 1 1 -format xy

-xy box a b

Effectue un redimensionnement des positions de sorte quelles se situent dans le rectangle [0,a[ × [0,b[. En prenant a=b=1, les coordonnées seront renormalisées dans le carré [0,1[². Cette opération est effectuée juste avant la génération des arêtes, mais après avoir effectué l'opération -xy noise (voir ci-après) et/ou -xy load.

-xy grid p

Ajoute une grille p × p au graphe généré, ce qui est utile lorsque les coordonnées des points sont entiers. Techniquement, on ajoute au format de sortie dot un sous-graphe représentant la grille où les sommets et les arêtes sont de couleur grise. Si p<0, alors le paramètre est initialisé à 1+⎣ √n⎦ ou bien à n si l'option "-xy permutation" est présente, n étant le nombre de sommets du graphe. Pour être visible, le nombre de lignes (et de colonnes) de la grille générée doit être au moins 2.

-xy zero

Ajoute l'origine (0,0) au dessin qui est représenté par un cercle rouge.

-xy vsize f

Facteur de grossissement des sommets pour le format dot. Par défaut f=1.

-xy noise r p

Effectue une perturbation aléatoire sur les positions des sommets. Le déplacement de chaque sommet est effectué dans sa boule de rayon r (pour p>0) selon une loi en puissance de paramètre p. Prendre p=0.5 pour une perturbation uniforme dans cette boule, p>0.5 pour une concentration des valeurs vers le centre et p<0.5 pour un écartement du centre. Les valeurs <0 de p donne des écartements au delà du rayon r.

Plus précisément, une direction (angle de 0 à 2𝜋) est choisie aléatoirement uniformément, puis, selon cette direction, un décalage aléatoire est effectué selon une loi en puissance: si x est uniforme dans [0,1[, le décalage sera d(x)=r·x^p. Après cette opération, il est possible que les points ne soient plus dans le rectangle d'origine, ce qui peut bien sûr être corrigé par -xy box.

-xy seed k p

Génère les points à partir (ou autour) de k>0 graines. Les graines sont choisies uniformément dans le carré [0,1[² puis centrées par rapport à leur barycentre. Chaque point est alors tiré aléatoirement autour d'une des graines et à une distance variant selon une loi en puissance (voir -xy noise) de paramètre p et de rayon r ≃ √(ln(k+1)/k). Ce rayon correspond au seuil de connectivité pour un Unit Disk Graph à k sommets dans le carré [0,1[² (voir udg n r). On peut obtenir une distribution uniforme dans un disque avec -xy seed 1 0.5 (voir aussi -xy disk) sauf que le centre est en (1/2,1/2) au lieu de (0,0) comme avec -xy disk.

          Ex: gengraph point 1000 -xy seed 1 1
	      gengraph point 1000 -xy seed 1 0.5

-xy permutation

Génère les points correspondant à une permutation 𝜋 aléatoire uniforme. Le point i aura pour position (i,𝜋(i)).

-xy mesh x y

Génère tous les points de coordonnées entières correspondant aux sommets d'une grille de x colonnes et de y lignes.

-xy cycle

Génère les points régulièrement espacés le long d'un cercle de centre (0,0) et de rayon 1. Les points sont ordonnées selon l'angle de leurs coordonnées polaires.

          Ex: gengraph cycle 10 -xy cycle -visu

-xy unif

Génère les points aléatoirement uniformément dans le carré [0,1[². C'est la distribution par défaut.

-xy circle

Génère les points aléatoirement uniforme le long d'un cercle de centre (0,0) et de rayon 1. Les points sont ordonnées selon l'angle de leurs coordonnées polaires.

-xy disk

Génère les points aléatoirement uniforme dans le disque unité de centre (0,0) triés selon l'angle de leurs coordonnées polaires. Cette distribution permet de générer, par exemple, un polygone "star-shaped". La distribution est similaire à l'option "-xy seed 1 0.5" sauf que les points sont ordonnées.

          Ex: gengraph cycle 25 -xy disk -visu

Remarque: les points sont générés avant l'application des options comme -xy round, -xy noise, ou -xy unique qui modifient les coordonnées et qui peuvent donc produire des croisements avec le graphe cycle par exemple.

-xy hyper p

Génère les points aléatoires selon une loi exponentielle de paramètre p dans le disque unité de centre (0,0), chaque point étant placé à une distance exp(-p·u) du centre où u est uniforme dans [0,1]. Les points sont triés selon l'angle de leurs coordonnées polaires.

-xy convex
-xy convex2

Génère les points aléatoirement en position convexe à l'intérieur d'un cercle de rayon 1 et de centre (0,0), ce qui peut être modifié par -xy ratio. Ils sont numérotés consécutivement selon le parcours de l'enveloppe convexe. On les génère comme suit, n étant le nombre points à générer. Inductivement, une fois que n-1 points en position convexe ont été générés, on choisit un angle 𝛼 aléatoire du cercle de rayon 1 et de centre (0,0) supposé à l'intérieur du convexe. On détermine ensuite la partie S du segment d'angle 𝛼 où chacun des points de S=[a,b[ forment avec les n-1 points précédant un convexe. Enfin, on choisit aléatoirement un point de S selon la probabilité √|b-a| pour obtenir n points en position convexe. Les angles des trois premiers points sont choisis parmi trois secteurs non adjacents d'angle 𝜋/3 si bien que l'origine est toujours à l'intérieur de l'ensemble convexe.

La variante -xy convex2 génère également des points aléatoires en position convexe, selon la méthode suivante. On génère n points aléatoires u_i du carré [0,1[² puis on calcule les vecteurs différences v_i ≡ u_{i+1}-u_i (mod n). Les vecteurs (dont la somme est nulle) sont ensuite triés par angle croissant, puis les points en position convexe sont obtenus de proche en proche en ajoutant chacun des vecteurs v_i. Cette méthode tend à générer des points proches d'un cercle, chaque angle et chaque longueur entre deux points consécutifs suivant une loi normale.

          Ex: gengraph cycle 25 -xy convex -visu
	      gengraph dtheta 100 6 -xy convex -visu

L'ordre des sommets peut être modifié par certaines options (voir la remarque de l'option -xy disk).

-xy polygon p

Génère des points aléatoires uniformément dans un polygone convexe régulier à p≥3 cotés inscrit dans le cercle de centre (0,0) et de rayon 1 de sorte qu'un des cotés du polygone soit vertical. Les sommets ne sont pas spécifiquement ordonnés. Pour une distribution uniforme dans un disque, soit lorsque p=+∞, utiliser -xy disk. L'option pour p=4 est similaire à -xy unif, sauf que pour p=4 la distribution est dans le carré [-c,+c[ × [-c,+c[ où c = cos(𝜋/4) = ½√2 ≃ 0.707… au lieu du carré [0,1[².

-xy ratio r

Modifie les distributions de points faisant intervenir une forme de largeur 1 et de hauteur r, comme: -xy unif, -xy circle, -xy cycle, -xy convex, -xy disk, -xy seed. La valeur par défaut est r=1. Le réel r>0 est donc le ratio de la hauteur par la largeur de la forme. Par exemple, pour la distribution par défaut (-xy unif), les points seront aléatoires uniformes dans le rectangle [0,1[ × [0,r[. Si la forme est un cercle (-xy circle ou -xy disk), alors la forme devient une ellipse dont le rayon horizontal est 1 et celui vertical r. Dans le cas de -xy seed, les graines sont alors générés dans le rectangle [0,1[ × [0,r[.

-xy surface s

Définit la signature s de la surface sur laquelle va être construit le graphe géométrique. La surface peut-être orientable ou non, avec ou sans bord. Elle est représentée par un polygone convexe régulier inscrit dans un cercle de rayon 1 et dont les 2|s| cotés sont appariés. Cette option se charge également de générer des points aléatoirement uniformes sur la surface. La signature est un mot s sur l'alphabet {h,c,b} de longueur |s|=2g, où g est le genre de la surface, indiquant comment sont appariés les 4g cotés du polygone. Chaque coté est apparié avec le coté +2 (le suivant du suivant) ou le coté -2 selon l'une des trois coutures suivantes:

h = handle = couture orientée ou anse
c = crosscap = couture non-orientée
b = border = aucune couture

La caractéristique d'Euler de la surface (ou sa courbure) vaut 2-|s| = 2-2g. Certaines signatures ont des synonymes. Par exemple, "-xy surface torus" est synonyme de "-xy surface hh" (voir ci-dessous leurs listes).

          Ex: -xy surface bb (ou plane ou square)  → plan réel
              -xy surface hb (ou cylinder) ....... → cylindre
              -xy surface cb (ou mobius) ......... → ruban de Möbius
              -xy surface hh (ou torus) .......... → tore
	      -xy surface ch (ou klein) .......... → bouteille de Klein
              -xy surface cc (ou projective) ..... → plan projectif
	      -xy surface hhhh ................... → double tore

Cette option active également -xy polygon 4g et -xy ratio 1 pour générer des points aléatoires uniformément sur la surface.

-xy round p

Arrondi les coordonnées à 10^-p près. Il faut que p soit un entier < DBL_DIG, soit p<15 en général. Donc p=0 arrondi à l'entier le plus proche. Cet opérateur est appliqué après -xy box. Il sert aussi à préciser le nombre de décimales à afficher pour l'option -format xy (par défaut p=6). Par exemple, la combinaison -xy box 100 100 -xy round -1 permet d'avoir des coordonnées multiples de 10.

-xy unique

Supprime les sommets en double, correspondant aux mêmes positions. Cela peut être utile lorsqu'on utilise -xy round par exemple. Cette opération est appliquée après toutes les autres, notamment après -xy box et -xy round. Ceci est réalisé à l'aide d'un tri des points, l'ordre n'est donc pas préservé).

GRAPHES

Deux types de graphes sont possibles : les graphes de base et les graphes composés. Ces derniers sont obtenus en paramétrant un graphe de base. Une catégorie importante de graphes sont les graphes géométriques (qui peuvent être composés ou de bases). L'adjacence est déterminée par les coordonnées associées aux sommets. De nombreuses options s'y réfèrent. Ils activent tous par défaut l'option -pos. Les graphes orientés activent quant à eux tous l'option -directed.

GRAPHES DE BASE :

grid n_1 … n_k .

Grille à k dimensions de taille n_1 × ⋯ × n_k. Si la taille n_i est négative, alors cette dimension est cyclique. Par exemple, "grid -10 ." donnera un cycle à 10 sommets.

ring n c_1 … c_k .

Anneaux de cordes à n sommets chacun ayant k cordes de longueur c_1,…,c_k. Par exemple, "ring 10 1 ." donnera un cycle à 10 sommets. Chaque cᵢ peut être positif ou négatif, mais il faut cᵢ≥-n. Si k=0, il s'agit d'un stable à n sommets. L'option -directed permet d'obtenir une k-orientation.

cage n c_1 … c_k .

Graphe pouvant servir à la construction de graphes n-cage, c'est-à-dire aux plus petits graphes cubiques à n sommets de maille donnée. Ils sont toujours Hamiltoniens. Ils peuvent être vus comme des anneaux de cordes irréguliers. Ils sont construits à partir d'un cycle de longueur n découpé en n/k intervalles de k>0 sommets. Le i-ème sommet de chaque intervalle, disons le sommet numéro j du cycle, est adjacent au sommet numéro j+cᵢ du cycle (modulo n). Chaque cᵢ peut être positif ou négatif, mais il faut cᵢ≥-n. Il est aussi possible de construire des graphes avec des sommets de degré 4 comme "cage 8 0 2 .", le graphe de Chvátal, ou avec des sommets de degré 2 comme "cage 4 2 0 .".

arboricity n k

Graphe d'arboricité k à n sommets aléatoire. Ce graphe est composé de l'union de k>0 arbres aléatoires. Il est donc toujours connexe. Chacun des arbres est un arbre plan enraciné aléatoire uniforme dont les sommets sont permutés aléatoirement, sauf le premier arbre dont les sommets sont numérotés selon un parcours en profondeur. Ces graphes possèdent au plus k·(n-1) arêtes, et pour k=1 il s'agit d'un arbre. L'option -directed permet d'obtenir une k-orientation.

rarytree n b z

Arbre b-aire plan aléatoire uniforme à n noeuds internes. Il faut b≥2. Il possède bn+1+z sommets, z étant un paramètre valant 0 ou 1. La racine est de degré b+z, les autres sommets sont de degré b+1 (soit b fils) ou 1 (=feuille). Les sommets sont numérotés selon un parcours en profondeur modifié: tous les fils du sommet courant sont numérotés avant l'étape de récursivité. Si n=1, alors le graphe est une étoile à b+z feuilles. Le dessin avec dot (-visu) ne respecte pas le plongement de l'arbre. L'option -directed permet d'obtenir une 1-orientation.

ringarytree h k r p

Arbre de hauteur h où chaque noeud de profondeur < h à exactement k fils, sauf la racine qui en possède r. Lorsque p>0, un chemin (si p=1) ou un cycle (si p=2) est ajouté entre les sommets de même profondeur. Notez que "ringarytree h 1 r 0" génère une étoile de degré r où chaque branche est de longueur h. Numérotés selon un parcours en profondeur, le nom des sommets est un mot correspondant au chemin depuis la racine.

rectree h f_1 f_2 ... f_d .

Arbre récursif de hauteur h où chaque noeud profondeur < h à exactement d fils, le i-ème fils étant la racine d'un arbre similaire de profondeur h-fᵢ. Il faut fᵢ>0. Ainsi "rectree h 1 1 ." est un arbre binaire complet de hauteur h. Le graphe "rectree h 1 1 ... 1 ." est un arbre complet de hauteur h identique à "ringarytree h d d 0". L'arbre est composé d'un seul sommet si d=0 ou h<=0. C'est une étoile si h>0 et d>=h. Le nombre de sommets est exponentiel en h dès que d≥2, plus précisément de la forme 𝛼·ρ^h-1 pour des constantes 𝛼>0 et ρ>1 dépendant des fᵢ. Pour f₁=f₂=1, 𝛼=ρ=2. Pour f₁=1 et f₂=2, 𝛼≃1.23 et ρ≃1.61. Pour f₁=1 et f₂=3, 𝛼≃1.34 et ρ≃1.47. Numérotés selon un parcours en profondeur, le nom des sommets est un mot correspondant au chemin depuis la racine.

kpage n k

Graphe k-pages connexe aléatoire. Un graphe k-page peut être représenter en plaçant les sommets le long d'un cercle, en dessinant les arêtes comme des segments de droites, et en coloriant les arêtes en k>0 couleurs de façon à ce que les arêtes de chaque couleur induisent le dessin d'un graphe planaire-extérieur. La numérotation des sommets est faite le long du cercle. Les graphes 1-page sont les graphes planaires-extérieurs, les 2-pages sont les sous-graphes de graphes planaires Hamiltoniens. Les graphes planaires de degré au plus 4 sont 2-pages, les 3-arbres planaires (ou graphes Apolloniens) sont 3-pages, et les cliques avec 2k-1 ou 2k sommets des k-pages. L'option -directed permet d'obtenir une 2k-orientation.

Ces graphes sont construits par le processus aléatoire suivant. On génère k graphes planaires-extérieurs aléatoires uniformes connexes à n sommets (plan et enraciné) grâce à une bijection avec les arbres plans enracinés dont tous les sommets, sauf ceux de la dernière branche, sont bicoloriés. On fait ensuite l'union de ces k graphes en choisissant aléatoirement la racine des arbres, sauf celui du premier planaire-extérieur, ce qui correspond à une permutation circulaire des sommets sur la face extérieure.

cactus n

Graphe cactus aléatoire à n sommets. Il s'agit d'arbres de cycles, c'est-à-dire de graphes connexes où chaque arête appartient à au plus un cycle. Ce sont aussi les graphes planaires-extérieurs connexes sans cordes. Ils sont générés à partir d'un "outerplanar n" dans lequel les arêtes internes (ou cordes) des composantes biconnexes ont été supprimés. L'option -directed permet d'obtenir une 2-orientation.

ktree n k

k-arbre aléatoire à n sommets. Il faut n>k≥0. C'est un graphe chordal appelé aussi graphe triangulé (triangulated). Il est généré à partir d'un arbre enraciné aléatoire uniforme à n-k noeuds de manière similaire à "tree n-k". Cela constitue les "sacs" que l'on remplit avec les n sommets comme suit: on met k+1 sommets dans le sac racine connecté en clique, puis, selon un parcours en profondeur de l'arbre, on met un sommet différent pour chacun des autres sacs. Ce sommet est alors connectés à exactement k sommets choisis aléatoirement dans le sac parent et sont ajoutés à son sac. Lorsque k=1, c'est un arbre, et lorsque k=0, c'est un stable. L'option -directed permet d'obtenir une k-orientation.

kpath n k

k-chemin aléatoire à n sommets. La construction est similaire à celle utilisée pour ktree, sauf que l'arbre est un chemin. Ces graphes sont des graphes d'intervalles particuliers (voir "interval n"). L'option -directed permet d'obtenir une k-orientation.

kstar n k

k-star aléatoire à n sommets. La construction est similaire à celle utilisée pour ktree, sauf que l'arbre est une étoile. Ces graphes, qui sont des "split graphs", sont composés d'une clique à k+1 sommets et de n-k-1 sommets indépendants connectés à k sommets aléatoire de la clique. Il est possible d'obtenir le graphe "split n k" si à chaque fois les k sommets de la clique tirés aléatoires sont toujours les mêmes. L'option -directed permet d'obtenir une k-orientation.

rig n k p

Graphe d'intersections aléatoire (Uniform Random Intersection Graph). Il possède n sommets, chaque sommet u étant représenté par un sous-ensemble S(u) aléatoire de {1,…,k} tel que chaque élément appartient à S(u) avec probabilité p. Il y a une arête entre u et v ssi S(u) et S(v) s'intersectent. La probabilité d'avoir une arête entre u et v est donc Pₑ=1-(1-p²)^k, mais les arêtes ne sont pas indépendantes (Pr(uv|uw)>Pr(uv)). En général, pour ne pas avoir Pₑ qui tend vers 1, on choisit les paramètres de façon à ce que kp²<cste. Lorsque k≥n³, ce modèle est équivalent au modèle des graphes aléatoires d'Erdös-Reny (voir random n p). Si p<0, alors p est fixée au seuil théorique de connectivité, à savoir p=√(ln(n)/(nk)) si k>n et p=ln(n)/k sinon.

apollonian n

Graphe Apollonien aléatoire uniforme à n≥4 sommets. Les graphes Apolloniens sont les 3-arbres planaires ou encore les graphes planaires maximaux chordaux. Ils sont obtenus en subdivisant récursivement un triangle en trois autres. Ils sont 3-dégénérés, de treewidth 3, et de nombre chromatique 4. La distance moyenne est ϴ(logn). Ils sont en bijection avec les arbres ternaires à n-3 noeuds internes. Pour n=5, il s'agit d'un K₅ moins une arête qu'on peut obtenir aussi avec "split 5 3". L'option -directed permet d'obtenir une 3-orientation.

polygon n

Triangulation aléatoire uniforme d'un polygone convexe à n≥3 cotés. Ce sont aussi des graphes planaires-extérieurs maximaux aléatoires. Ils sont Hamiltoniens, 2-dégénérés, de treewidth 2, et de nombre chromatique 3. Ils sont en bijection avec les arbres binaires (complets) à n-2 noeuds internes ou encore les mots de Dyck de longueur 2(n-2). La numérotation des sommets n'est pas cyclique le long du polygone. Ce graphe n'est pas un graphe géométrique contrairement à ses variantes utilisant -xy convex comme dans l'exemple ci-après.

       Ex: gengraph polygon 20 -dot filter circo -visu
           gengraph td-delaunay 20 -xy convex2 -visu

planar n f d

Graphe planaire aléatoire composé de n faces internes de longueur f≥3, les sommets internes étant de degré au moins d et ceux de la face externe au moins 2. Ils possèdent entre n+f-1 et n(f-2)+2 sommets, sont 2-connexes, 2-dégénérés, de maille f. Si d>4 alors ils sont d'hyperbolicité O(f). Ils sont construits en ajoutant itérativement les faces par le processus aléatoire suivant. Au départ, il s'agit d'un cycle de longueur f. Pour chaque nouvelle face on ajoute un sommet u que l'on connecte à un sommet quelconque du cycle C formant le bord de la face extérieure du graphe courant. Puis on ajoute un chemin allant de u à un sommet v de C de façon à respecter: 1) la contrainte des degrés des sommets qui vont devenir internes; et 2) la contrainte sur la longueur de la nouvelle face créée. Le sommet v est choisit uniformément parmi tous les sommets possibles de C respectant les deux contraintes. Si d<0, alors on fait comme si d=+∞ (aucun sommet ne pouvant alors être interne) et le résultat est un graphe planaire-extérieur Hamiltonien, c'est-à-dire 2-connexe. Si f<0, alors chaque face créée est de longueur aléatoire uniforme prise dans [3,|f|] au lieu d'être de longueur exactement |f|. Si f=d=4, il s'agit d'un "squaregraph". Les valeurs d=0,1,2 sont équivalentes. L'option -directed permet d'obtenir une 2-orientation.

hyperbolic p k h

Graphe issu du pavage du plan hyperbolique ou euclidien par des polygones réguliers à p≥3 cotés où chaque sommets est de degré k≥2. Le graphe est construit par couches successives de polygones, le paramètre h≥1 représentant le nombre de couches. Lorsque h=1, il s'agit d'un seul polygone, un cycle à p sommets. Dans tous les cas les graphes sont planaires avec O((pk)^h) sommets, ils sont 2-connexes et d'arboricité 2 pour p>3. Lorsque p=3, ils sont 3-connexes et d'arboricité 3. L'option -directed permet d'obtenir une 3-orientation. Sans être les mêmes graphes, il y a des similarités avec les graphes "planar n f d". Pour paver le plan hyperbolique, représentable sur le disque de Poincaré, il faut 1/p + 1/k < 1/2. Dans ce cas, le graphe est d'hyperbolicté O(p). Pour paver le plan euclidien il faut prendre p=k=4 (grille carrée) ou p=3, k=6 (grille triangulaire) ou p=6, k=3 (grille hexagonale). Si k≤3 et p≤5, alors le graphe existe que pour certaines valeurs de h≤3. Le cas k=3, p=4, h=2 correspond au cube, et k=3, p=5, h=3 est le graphe dodécahèdre ("dodecahedron"). Si k=2, alors h=1 et le graphe est un cycle à p sommets.

rlt p q d

Random Lattice Triangulation. Il s'agit d'un graphe planaire aléatoire construit à partir d'une triangulation de la grille p × q. Toutes les faces, sauf celle extérieure, sont des triangles. Il possède pq sommets et (2p-1)(2q-1)-pq arêtes, dont les 2(p+q-2) qui sont sur le bord de la grille et le reste est à l'intérieur. Le paramètre d contrôle la longueur des arêtes suivant la norme Lmax. Par exemple, si d=1, les arêtes seront soit celles de la grille (verticales ou horizontales) ou diagonales. Si d<0, alors l'effet est similaire à d=+∞. Si d=0, on obtient un stable. Si p=1 ou q=1 (et d≠0), on obtient un chemin.

       Ex: gengraph rlt 8 14 2 -dot scale 0.1 -visu

Il est difficile de générer de telles grilles aléatoirement uniformément. Il faut pour cela utiliser une technique de flips avec une chaîne de Markov dont le mixing time n'est pas connu. Il est cependant bien connu que le milieu de chaque arête e d'une triangulation T de grille a pour coordonnées (i+1/2,j) ou (i+1/2,j+1/2) où i,j sont des entiers. Et inversement, chaque point "milieu" de la grille est coupé par exactement une arête de T. Il est aussi connu que si l'on parcourt les points milieux de la grille de bas en haut et de gauche à droit, alors il n'y qu'au plus deux choix possibles pour l'arête ayant ce milieu. Malheureusement, suivre ce parcours et choisir aléatoirement l'une ou l'autre de ces arêtes ne donne pas une distribution aléatoire uniforme. On propose ici la construction d'une triangulation T de manière aléatoire comme suit:

Tant qu'il reste au moins un point milieu faire: 1. choisir uniformément un point milieu R parmi les points restant 2. déterminer la liste L des arêtes possibles ayant pour milieu R (respectant la planarité et le critère de longueur) 3. choisir uniformément une arête de L et l'ajouter au graphe

kneser n k r

Graphe de Kneser généralisé. Le graphe de Kneser K(n,k) classique est obtenu avec r=0. Les sommets sont tous les sous-ensembles à k éléments de [0,n[ (il faut donc 0≤k≤n). Deux sommets sont adjacents ssi leurs ensembles correspondant ont au plus r éléments en commun. Le nombre chromatique de K(n,k), établit par Lovász, vaut n-2k+2 pour tout n≥2k-1>0. Le graphe de Petersen est le graphe K(5,2). Ils ont un lien avec les graphes de Johnson J(n,k) et les odd graphs.

gpetersen n r

Graphe de Petersen généralisé P(n,r), 0≤r<n/2. Ce graphe cubique possède 2n sommets qui sont u_1,…,u_n,v_1,…,v_n. Les arêtes sont, pour tout i: u_i-u_{i+1}, u_i-v_i et v_i-v_{i+r} (indice modulo n). Il peut être dessiné tel que toute ses arêtes sont de même longueur (unit distance graph). Ce graphe est biparti ssi n est pair et r est impair. C'est un graphe de Cayley ssi r²=1 (modulo n). P(n,r) est Hamiltonien ssi r≠2 ou n≠5 (modulo 6). P(n,r) est isomorphe à P(n,(n-2r+3)/2)). P(4,1) est le cube, P(5,2) le graphe de Petersen, P(6,2) le graphe de Dürer, P(8,3) le graphe de Möbius-Kantor, P(10,2) le dodécaèdre, P(10,3) le graphe de Desargues, P(12,5) le graphe de Nauru, P(n,1) un prisme.

squashed n k p

Squashed Cube aléatoire à n sommets. Il faut 0<k<n et p∈[0,1]. Les sommets sont des mots aléatoires de k lettres sur {0,1,'*'} où p est la probabilité d'obtenir '*'. La probabilité d'obtenir 0 est la même que celle d'obtenir 1, soit (1-p)/2. Deux sommets sont adjacents si la distance de Hamming entre leur mots vaut 1 avec la convention que la distance à la lettre '*' est nulle. Lorsque que p=0, le graphe généré est un sous-graphe isométrique de l'hypercube où certains sommets sont dupliqués en sommets jumeaux non-adjacents (ce sont les sommets correspondant au même mot). En particulier, le graphe est biparti et la distance entre deux sommets est données par la distance de Hamming entre leur mot, sauf s'ils ont le même mot. Si p=-1 alors p est fixée à l'équiprobabilité de chacune des lettres, soit p=1/3.

antiprism n

Graphe composé de deux cycles à n sommets connectés par 2n triangles. Le prisme est similaire sauf que pour ce dernier les deux cycles sont connectés par des carrés. Il est ainsi planaire, 4-régulier, possède 2n sommets et 4n arêtes. C'est aussi le dual du trapézoèdre n-gonal.

rpartite a_1 … a_k .

Graphe k-parti complet K_{a_1,…,a_k}. Ce graphe possède a_1 + ⋯ + a_k sommets partitionnés en k parts. La i-ème part contient a_i sommets numérotés consécutivement dans l'intervalle [ a_1 + ⋯ + a_{i-1}, a_1 + ⋯ + a_i [. Les sommets i et j sont adjacents ssi i et j appartiennent à des parts différentes.

ggosset p d_1 v_1 … d_k v_k .

Graphe de Gosset généralisé. Les sommets sont tous les vecteurs entiers (et leurs opposés) de dimension d = d_1 + ⋯ + d_k dont les coordonnées comprennent exactement dᵢ≥1 fois la valeur vᵢ. Le nombre de sommets est donc n = 2·∏_i binomial(d-(∑_{j<i}d_i), d_i). Il existe une arête entre les vecteurs u et v si et seulement le produit scalaire entre u et v vaut l'entier p. Des valeurs intéressantes sont par exemple "ggosset 1 2 -1 2 0 ." ou "ggosset 8 2 3 6 -1 ." (le graphe de Gosset).

schlafli

Graphe de Schläfli. Il s'agit du sous-graphe induit par les voisins d'un quelconque sommet du graphe de Gosset. Il possède 27 sommets, 216 arêtes et est 16-régulier. Il est sans-griffe, Hamiltonien, de diamètre 2, de maille 3 et de nombre chromatique 9.

crown n

Graphe biparti régulier à 2n sommets où le i-ème sommet de la première partie de taille n est voisin au j-ème sommet de la seconde partie ssi i≠j. Pour n=3, il s'agit du cycle à 6 sommets, pour n=4, il s'agit du cube (à 8 sommets).

split n k

Graphe split (ou fendu) à n sommets et de clique maximum k. Il s'agit d'un graphe à n sommets composé d'une clique à k sommets et d'un ensemble indépendant de n-k sommets connectés chacun à tous ceux de la clique. C'est un graphe triangulé (chordal) et un cas particulier de "kstar n k". On peut montrer que presque tous les graphes triangulés à n sommets sont des graphes split (Bender et al. 1985). Si k≥n-1, alors il s'agit d'une clique, et si k=n-2, il s'agit d'une clique moins une arête. Si k=1 il s'agit d'une étoile à n-1 branches.

fan p q

Graphe de p+q sommets composé d'un chemin à p sommets et de q sommets, chacun connectés à tous ceux du chemin. Le graphe classique "fan n" correspond à p=n et q=1.

flip n

Graphe des flips des triangulations d'un polygone convexe à n>2 sommets. Les sommets, qui sont les triangulations, sont en bijection avec des arbres binaires (complets) à m=n-2 noeuds internes qui sont codés par les mots de Dyck de longueur 2m (mots que l'on peut afficher avec -label 1). Le nombre de sommets est donc C(m) = binom(2m,m)/(m+1), le nombre de Catalan d'ordre m. Les adjacences peuvent être vues aussi comme des rotations d'arbres. Le diamètre est 2n-10 pour n>12. Le nombre chromatique n'est pas connu. On sait pas s'il est constant ou pas. Il vaut 3 pour n=5..9, et 4 pour n=10 et 11.

interval n

Graphe d'intersection de n intervalles d'entiers aléatoires uniformes pris dans [0,2n[. Des graphes d'intervalles peuvent aussi être générés par "kpath n k".

circle n

Graphe d'intersection de n cordes aléatoires d'un cercle. Il est réalisé par le graphe d'inclusion de n intervalles d'entiers aléatoires uniformes pris dans [0,2n[. Les graphes de permutation et les planaires extérieurs sont des exemples de circle graphs.

permutation n

Graphe de permutation sur une permutation aléatoire uniforme des entiers de [0,n[.

prime n

Graphe à n sommets tel que i est adjacent à j ssi i>1 et j divisible par i.

paley n

Graphe de Paley à n sommets. Deux sommets sont adjacents ssi leur différence est un carré modulo n. Il faut que n soit la puissance d'un nombre premier et que n≡1 (mod 4), mais le graphe est aussi défini pour les autres valeurs. Les premières valeurs possibles pour n sont: 5, 9, 13, 17, 25, 29, 37, 41, 49, … Ces graphes sont Hamiltoniens. Si n est simplement premier, alors ils sont de plus auto-complémentaires et réguliers. Paley 17 est le plus grand graphe G où ni G ni son complémentaire ne contient K₄, d'où Ramsey(4)=18.

mycielski k

Graphe de Mycielski de paramètre (nombre chromatique) k. C'est un graphe sans triangle, k-1 (sommets) connexe, et de nombre chromatique k. Le premier graphe de la série est M2 = K2, puis on trouve M3=C5, M4 est le graphe de Grötzsch à 11 sommmets.

windmill n

Graphe composé de n cycles de longueur trois ayant un sommet commun.

barbell n1 n2 p

Graphe des haltères (Barbell Graph) composé de deux cliques de n1 et n2 sommets reliées par un chemin de longueur p. Il possède n1+n2+p-1 sommets. Si p=0 (p=-1), le graphe est composé de deux cliques ayant un sommet (une arête) en commun. Plus généralement, si p≤0, le graphe est composé de deux cliques s'intersectant sur 1-p sommets.

chess p q x y

Graphe composé de p x q sommets représentant les cases d'un échiquier p x q, deux cases étant connectée s'il existe un déplacement d'une case vers l'autres avec un saut de x cases selon un axe et y selon un autre. Le "knight graph" classique est donc un "chess 8 8 2 3", et "chess n 2 1 0" correspond à "ladder n".

sat n m k

Graphe aléatoire issu de la réduction du problème k-SAT à Vertex Cover. Le calcul d'un Vertex Cover de taille minimum pour ce graphe est donc difficile pour k>2. Soit F une formule de k-SAT avec n>0 variables x_i et m>0 clauses CNF de k>0 termes. Le graphe généré par "sat n m k" possède un Vertex Cover de taille n+(k-1)m si et seulement si F est satisfiable.

Ce graphe est composé d'une union de n arêtes indépendantes et de m cliques à k sommets, plus des arêtes dépendant de F connectant certains sommets des cliques aux n arêtes. Les n arêtes représentent les n variables, une extrémité pour x_i, l'autre pour ¬(x_i). Ces sommets ont des numéros dans [0,2n[, x_i correspond au sommet 2i-2 et ¬(x_i) au sommet 2i-1, i=1…n. Les sommets des cliques ont des numéros consécutifs ≥ 2n et correspondent aux clauses. Le p-ème sommet de la q-ème clique (pour p=1…k et q=1…m) est connecté à l'une des extrémités de la i-ème arête (pour i=1…n) ssi la p-ème variable de la q-ème clause est x_i ou ¬(x_i).

La formule F est construite en choisissant indépendamment et uniformément pour chacune des m clauses et chacun des k termes une des variables parmi x_1,…,x_n,¬(x_1),…,¬(x_n). Ainsi chaque sommet d'une clique possède exactement un voisin (choisi aléatoirement uniforme) parmi les 2n extrémités d'arêtes.

tree_fibo n

Arbre des appels pour la fonction récursive calculant le (n+1)-ième nombre f(n) de la suite de Fibonacci pour tout n≥0. Il est défini par la récurrence f(n) = n si n<2, f(n) = f(n-1) + f(n-2). L'arbre est orienté et possède 2f(n+1)-1 ≃ 1.789*1.618^n sommets. Le nombre de feuilles vaut précisément f(n), ce qui donne un moyen de le calculer en comptant les feuilles avec -undirected -check deg.

       Ex: gengraph tree_fibo 10 -label 1 -dot filter dot -visu
           gengraph tree_fibo 10 -undirected -format no -check deg

tree_part n k

Arbre des appels pour la fonction récursive calculant le nombre p(n,k) de partition de l'entier n>0 en 0<k≤n parts. Il est défini par la récurrence p(n,k) = 1 si k=1, p(n,k) = p(n-1,k-1) si n<2k, et p(n,k) = p(n-1,k-1) + p(n-k,k) sinon. L'arbre est orienté et le nombre de feuilles vaut précisément p(n,k), ce qui donne un moyen de le calculer en comptant les feuilles avec -undirected -check deg.

       Ex: gengraph tree_part 22 6 -label 1 -dot filter dot -visu
           gengraph tree_part 22 6 -undirected -format no -check deg

Il existe une variante (-variant 1), calculant également p(n,k), avec une récurrence légèrement différente qui est: p(n,k) = 0 si n<k, p(n,k) = 1 si k=n ou k=1, et p(n,k) = p(n-1,k-1) + p(n-k,k) sinon. Dans ce cas l'arbre est binaire complet (chaque sommet a 0 ou 2 fils), mais le nombre de feuilles n'est plus p(n,k), il est plus grand. De plus il a plus de sommets que la variante par défaut (-variant 0).

tree_binom n k

Arbre des appels pour la fonction récursive calculant le coefficient binomial binom(n,k) pour tout entiers n≥1 et 0≤k≤n. Il est défini par la récurrence binom(n,k) = binom(n-1,k-1) + binom(n-1,k) si 0<k<n, et binom(n,k) = 1 si k=0 ou k=n. L'arbre est un arbre binaire orienté et possède binom(n,k) = n!/k!/(n-k)! feuilles, ce qui donne un moyen de calculer ce nombre en comptant les feuilles avec -undirected -check deg.

       Ex: gengraph tree_binom 5 2 -label 1 -dot filter dot -visu
           gengraph tree_binom 5 2 -undirected -format no -check deg

kout n k

Graphe à n sommets k-dégénéré crée par le processus aléatoire suivant: les sommets sont ajoutés dans l'ordre croissant de leur numéro, i=0,1,…,n-1. Le sommet i est connecté à d voisins qui sont pris aléatoirement uniformément parmi les sommets dont le numéro est < i. La valeur d est choisie aléatoirement uniformément entre 1 et min{i,k}. Il faut 0<k<n. Le graphe est connexe, et pour k=1, il s'agit d'un arbre. L'option -directed permet d'obtenir une k-orientation.

       Ex: gengraph kout 50 2 -directed -vcolor deg -vcolor pal wbn -vsize -visu

expander n k

Graphe à n sommets composé de k>0 cycles Hamiltoniens aléatoires. Le degré des sommets varie entre 2 et 2k pour n>2. Il possède le cycle 0,1,…,n-1,0 comme cycle Hamiltonien, et a la propriété d'expansion à partir de k≥4. Plus précisément, avec grande probabilité, les valeurs propres de la matrice d'adjacence du graphe sont ≤ 2√(2k). On rappelle que la constante d'expansion, isopérimétrique, ou de Cheeger, h(G) d'un graphe d-régulier G est toujours comprise entre (d-λ₂)/2 ≤ h(G) ≤ √(2d(d-λ₂)) où λ₂ est la deuxième plus grande valeur propre de la matrice d'adjacence de G. L'option -directed permet d'obtenir une k-orientation.

margulis n

Graphe de Margulis à n^2 sommets. Il s'agit d'un expandeur avec λ₂ ≤ 5√2 (cf. graphe "expander n k") de degré maximum 8 et de degré minimum 2. Les sommets sont les paires d'entiers (x,y) avec x,y ∈ [0,n[ avec les 8 adjacences suivantes: (x+y,y), (x-y,y), (x,y+x), (x,y-x), (x+y+1,y), (x−y+1,y), (x,y+x+1) et (x,y−x+1), toutes ces opérations étant modulo n.

comb n
centipede n

Arbre de 2n sommets en forme de peigne, composé d'un chemin à n sommets avec un sommet pendant à chacun d'eux. On peut l'obtenir en supprimant une arête d'un sunlet n.

sunlet n

Cycle à n sommets avec un sommet pendant à chacun d'eux. Un sunlet 3 est parfois appelé netgraph.

parachute n

Graphe Parachute. Il est planaire à n+3 sommets composés du graphe "fan n 2" dont un des deux sommets de degré n possède un sommet pendant. Le graphe classique correspond à n=4. C'est le complémentaire du graphe parapluie n.

alkane t n

Graphe planaires dont les sommets sont de degré 1 ou 4 représentant la structure moléculaire d'hydrocarbure alkalin à n atomes de carbones. Le paramètre t (voir ci-dessous les six types possibles) contrôle la topologie des liaisons simples entre atomes de carbone (C), les atomes d'hydrogènes (H) étant des sommets pendants de sorte que chaque atome C soit de degré 4. Certaines topologies ne sont définies que pour certaines valeurs de n. Les alkalins, de formule C_n H_{2n+2} si type≠"cyclo", sont des arbres de 3n+2 sommets alors que les cycloalkalin, de formule C_n H_{2n} si type="cyclo", ont 3n sommets et possède un cycle. Chaque type peut abrégé par ses 2 premières lettres. L'option "-label 1" activée par défaut permet de distinguer les atomes C et H.

           t      topologie     n             t     topologie     n
                                                    C─┐
          normal  C─ ⋯ ─C      n≥1           neo    C─C─ ⋯ ─C    n≥5
                                                    C─┘
                  ┌─C─ ⋯ ─C                           ┌─C─ ⋯ ─C
          cyclo   C       │    n≥3           sec    C─C          n≥6
                  └─C─ ⋯ ─C                           └─C─ ⋯ ─C
                  C─┐                                 ┌─C─ ⋯ ─C
          iso       C─ ⋯ ─C    n≥4           tret   C─C─C─ ⋯ ─C  n≥7
                  C─┘                                 └─C─ ⋯ ─C

Il est possible d'utiliser les alias suivants:

            n-alkane n ......... (= alkane normal n) 
            cyclo-alkane n ..... (= alkane cyclo n)
	    iso-alkane n ....... (= alkane iso n)
	    neo-alkane n ....... (= alkane neo n)
	    sec-alkane n ....... (= alkane sec n)
	    tret-alkane n ...... (= alkane tret n)
	    methane ............ (= alkane normal 1)
	    ethane ............. (= alkane normal 2)
	    propane ............ (= alkane normal 3)
	    butane ............. (= alkane normal 4)
	    pentane ............ (= alkane normal 5)
	    hexane ............. (= alkane normal 6)
	    heptane ............ (= alkane normal 7)
	    octane ............. (= alkane normal 8)
	    nonane ............. (= alkane normal 9)

Il est possible aussi de combiner les préfixes cyclo-, iso-, neo-, sec-, tret- avec les radicaux meth, eth, prop, but, hex, hept, oct, non, lorsque la condition sur n est satisfaite. Par exemple, cyclo-pentane (= alkane cyclo 5) et iso-butane (= alkane iso 4).

icosahedron

Isocahèdre: graphe planaire 5-régulier à 12 sommets. Il possède 30 arêtes et 20 faces qui sont des triangles. C'est le dual du dodécahèdre.

rdodecahedron

Rhombic-dodécaèdre: graphe planaire à 14 sommets avec des sommets de degré 3 ou 4. Il possède 21 arêtes et 12 faces qui sont des carrés. C'est le dual du cuboctaèdre.

deltohedron n
trapezohedron n

Deltoèdre ou trapézoèdre n-gonal: graphe composé de 2n faces en forme de cerf-volant (deltoïdes) décalées symétriquement. C'est un graphe planaire de 2n+2 sommets et 4n arêtes où toutes les faces sont des carrées. C'est aussi le dual de l'antiprisme n-gonal. Il s'agit d'un cube si n=3.

tutte

Graphe de Tutte. C'est un graphe planaire cubique 3-connexe à 46 sommets qui n'est pas Hamiltonien.

hgraph

Arbre à six sommets dont quatre feuilles en forme de H.

rgraph
fish

Fish Graph, graphe à six sommets en forme de R ou de poisson. Il est composé d'un cycle à quatre sommets dont un ayant deux sommets pendants.

cricket

Cricket Graph, graphe à cinq sommets composé d'un triangle où à l'un des sommets est attaché deux sommets pendant (de degré 1).

moth

Moth Graph, graphe à six sommets composé de deux triangles partageant une arête et de deux sommets pendant (degré 1) attachés à un sommet de degré trois.

dart

Dart Graph, graphe à cinq sommets composé de deux triangles partageant une arête et d'un sommet pendant (degré 1) attaché à un sommet de degré trois. Il peut être obtenu à partir du graphe moth en supprimant un sommet pendant.

bull

Bull Graph, graphe à cinq sommets auto-complémentaire en forme de A.

antenna

Antenna Graph, graphe planaire à six sommets formé du graphe house et d'un sommet pendant attaché à son toit. Plus précisément, il est composé d'un carré, d'un triangle partageant une arrête et d'un sommet pendant au sommet de degré 2 du triangle. C'est le complémentaire du graphe formé d'un carré et de deux triangles partageant deux arêtes consécutive du carré.

suzuki

Graphe de Suzuki (2010). C'est l'unique graphe 1-planaire à n=11 sommets et ayant le nombre optimal d'arêtes, soit 4n-8 arêtes (ici 36 donc).

harborth

Graphe de Harborth. C'est un graphe planaire 4-régulier à 52 sommets qui est distance unitaire aussi appelé graphe allumette (voir theta0 et diamond). Il peut ainsi être dessiné sans croisement d'arête qui ont toutes la même longueur.

doily

Graphe Doily (de Payne). C'est un graphe de 15 sommets qui est un carré généralisé pouvant être représenté par 15 points et 15 lignes, avec 3 points par ligne et 3 lignes par point, et sans triangle.

herschel

Graphe de Herschel. C'est le plus petit graphe planaire 3-connexe qui ne soit pas Hamiltonien. Il est biparti, possède 11 sommets et 18 arêtes.

goldner-harary

Graphe de Goldner-Haray. C'est le plus petit graphe planaire maximal qui ne soit pas Hamiltonien. Il possède 11 sommets et donc 27 arêtes (voir aussi Herchel). C'est un 3-arbre planaire (voir apollonian).

fritsch

Graphe de Fritsch. Il est planaire maximal à 9 sommets qui peut être vu comme un graphe de Hajós dans un triangle. C'est, avec le graphe de Soifer, le plus petit contre-exemple à la procédure de coloration de Kempe. C'est le plus petit graphe où l'heuristique de degré minimum donne cinq couleurs.

triplex

Graphe cubique de maille 5 à 12 sommets 1-planaire pouvant être dessiné avec seulement deux croisements d'arête. Un des cinq graphes (avec le Petersen) a être cycliquement-5-connexe (McCuaig 1992).

jaws

Graphe cubique de maille 5 à 20 sommets qui est un doublecross, c'est-à-dire dessinable sur le plan avec deux paires d'arêtes se croisant sur la face extérieure. Il est donc 1-planaire. Tout graphe theta-connecté sans Petersen mais avec Jaws comme mineur est un doublecross.

starfish

Graphe cubique de maille 5 à 20 sommets non-planaire, mais peut-être dessiné comme une étoile à cinq branches avec une couronne centrale à 15 sommets formant un circulant avec une corde de longueur 3. Un graphe theta-connecté (cf. Seymour et al. 2015) ssi il ne contient pas de Petersen comme mineur, si c'est un graphe apex (planaire plus un sommet), un doublecross (voir jaws) ou un starfish.

soifer

Graphe de Soifer. Il est planaire maximal à 9 sommets. C'est, avec le graphe de Fritsch, le plus petit contre-exemple à la procédure de coloration de Kempe. C'est le plus petit graphe où l'heuristique de degré minimum donne cinq couleurs.

poussin

Graphe de Poussin. Il est planaire maximal à 15 sommets. C'est un contre-exemple à la procédure de coloration de Kempe.

heawood4

Graphe de Heawood pour la conjecture des 4 couleurs, contre-exemple de la preuve de Kempe. Il est planaire maximal avec 25 sommets, est de nombre chromatique 4, de diamètre 5, de rayon 3 et Hamiltonien.

errera

Graphe d'Errera. Il est planaire maximal à 17 sommets. C'est un contre-exemple à la procédure de coloration de Kempe.

kittell

Graphe de Kittell. Il est planaire maximal à 23 sommets. C'est un contre-exemple à la procédure de coloration de Kempe.

frucht

Graphe de Frucht. Il est planaire cubique à 12 sommets. Il n'a pas de symétrie non-triviale. C'est un graphe de Halin de nombre chromatique 3, de diamètre 4 et de rayon 3.

treep p

Arbre aléatoire à p>2 feuilles sans sommets internes de degré deux. Il possède entre p+1 et 2p-2 sommets. Ce graphe est à la base de la construction des graphes de Halin.

halin p

Graphe de Halin aléatoire basé sur un arbre à p>2 feuilles. Il possède entre p+1 et 2p-2 sommets. Il est constitué d'un arbre sans sommets de degré deux dont les p feuilles sont connectés par un cycle (de p arêtes). Ces graphes planaires de degré minimum au moins trois sont aussi arête-minimale 3-connexes, Hamiltonien (et le reste après la suppression de n'importe quel sommet), de treewidth exactement 3 (ils contiennent K₄ comme mineur). Ils contiennent toujours au moins trois triangles et sont de nombre chromatique 3 ou 4.

butterfly d

Graphe Butterfly de dimension d. Les sommets sont les paires (x,i) où x est un mot binaire de d bits et i un entier de [0,d]. Les sommets peuvent être représentés en d+1 niveaux chacun de 2^d sommets, les arêtes connectant les niveaux consécutifs. Le sommet (x,i) est adjacent à (y,i+1) ssi les bits de x sont identiques à ceux de y sauf pour celui de numéro i+1 (le bit 1 étant le bit de poids le plus faible). Il possède (d+1)·2^d sommets et d·2^(d+1) arêtes, les sommets de niveau 0 et d étant de degré 2 les autres de degré 4.

shuffle d

Graphe Shuffle-Exchange de dimension d. Les sommets sont les mots binaires de d lettres. Le sommet w et w' sont voisins si w et w' diffèrent du dernier bit, ou bien si w' peut être obtenu par décalage cyclique à droite ou à gauche de w.

debruijn d b

Graphe de De Bruijn de dimension d≥0 et de base b>0. Il a b^d sommets qui sont tous les mots de d lettres sur un alphabet de b lettres. Le sommet (x_1,…,x_d) est voisin des sommets (x_2,…,x_d,*). Ce graphe est Hamiltonien, de diamètre d et le degré de chaque sommet est 2b, 2b-1 ou 2b-2. Pour d=3 et b=2, le graphe est planaire.

kautz d b

Graphe de Kautz de dimension d>0 et de base b>1. Il a b·(b-1)^(d-1) sommets qui sont tous les mots de d lettres sur un alphabet de b lettres avec la contrainte que deux lettres consécutives doivent être différentes. L'adjacence est celle du graphe de De Bruijn. C'est donc un sous-graphe induit de De Bruijn (debruijn d b). Il est Hamiltonien, de diamètre d et le degré de chaque sommet est 2b-2 ou 2b-3. Pour d=b=3 le graphe est planaire.

linial n t

Neighborhood graph des cycles introduit par Linial. C'est le graphe de voisinage des vues de taille t d'un cycle orienté symétrique à n sommets ayant des identifiants uniques de [0,n[. Il faut n≥t>0 et n≥2. Les sommets sont les t-uplets d'entiers distincts de [0,n[. Le sommet (x_1,…,x_t) est voisin des sommets (x_2,…,x_t,y) où y≠x_1 si n>t et y=x_1 si n=t. Le nombre chromatique de ce graphe est k ssi il existe un algorithme distribué qui en temps t-1 (resp. en temps (t-1)/2 avec t impair) peut colorier en k couleurs tout cycle orienté (resp. orienté symétrique) à n sommets ayant des identifiants uniques et entiers de [0,n[. C'est un sous-graphe induit de "linialc n t", et donc du graphe de Kautz (kautz t n) et de De Bruijn (debruijn t). Le nombre de sommets est n·(n-1)┅(n-t+1). Certaines propriétés se déduisent du graphe linialc n t. Pour n=4 et t=2, il s'agit du cuboctaèdre.

linialc m t

Neighborhood graph des cycles colorés. Il s'agit d'une variante du graphe linial n t. La différence est que les sommets du cycle n'ont plus forcément des identités uniques, mais seulement une m-coloration avec m≤n. Il faut m≥t≥0 et m≥2. L'adjacence est identique, mais les sommets sont les t-uplets (x_1,…,x_t) d'entiers de [0,m[ tels que x_i≠x_{i+1}. Il s'agit donc d'un sous-graphe induit de linialc m t, lui-même sous-graphe induit du graphe de Kautz (kautz t m) et donc de De Bruijn (debruijn t m). Le nombre de sommets est m·(m-1)^{t-1} et son degré est ≤ 2·(m-1). La taille de la clique maximum est 3 si m>2 et t>1. Le nombre chromatique de ce graphe pour t=3 est 3 pour m=4, 4 pour 5≤m≤24. Pour 25≤m≤70 c'est au moins 4 et au plus 5, la valeur exacte n'étant pas connue. Tout comme "linial 4 2", pour m=4 et t=2, il s'agit du cuboctaèdre.

pancake n

Graphe "pancake" de dimension n. Il a n! sommets qui sont les permutations de {1,…,n} et (n-1)-régulier. Une permutation, c'est-à-dire un sommet, est voisine de toutes celles obtenues en retournant un de ces préfixes. Plus précisément, les sommets x=(x_1,…,x_n) et y=(y_1,…,y_n) sont adjacents s'il existe un indice k tel que y_i=x_i pour tout i>k et y_i=x_{k-i} sinon. Son diamètre, qui est linéaire en n, n'est pas connu précisément. Les premières valeurs connues, pour n=1…17, sont: 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19. Donc les diamètres 2,6,12 n'existent pas.

bpancake n

Graphe "burn pancake" de dimension n. Il a n!·2^n sommets qui sont les permutations signées de {1,…,n}. Les sommets x=(x_1,…,x_n) et y=(y_1,…,y_n) sont adjacents s'il existe un indice k tel que y_i=x_i pour tout i>k et y_i=-x_{k-i} sinon. Dit autrement la permutation de y doit être obtenue en retournant un préfixe de x et en inversant les signes. Par exemple, le sommet (+2,-1,-5,+4) est voisin du sommet (+5,+1,-2,+4). Comme le graphe pancake, c'est un graphe (n-1)-régulier de diamètre linéaire en n.

gpstar n d

Graphe "permutation star" généralisé de dimension n. Il a n! sommets qui sont les permutations de {1,…,n}. Deux sommets sont adjacents si leurs permutations diffèrent par d positions. Si d<2, il s'agit d'un stable. C'est un graphe régulier.

pstar n

Graphe "permutation star" de dimension n. Il a n! sommets qui sont les permutations de {1,…,n}. Deux sommets sont adjacents si une permutation est obtenue en échangeant le premier élément avec un autre. Le graphe est (n-1)-régulier. Le graphe est biparti et de diamètre ⎣ 3(n-1)/2)⎦. C'est un sous-graphe induit d'un "gpstar n 1".

hexagon p q

Grille hexagonale p x q. C'est un planaire composé de p rangées de q hexagones, le tout arrangé comme un nid d'abeille. Ce graphe peut aussi être vu comme un mur de p rangées de q briques, chaque brique étant représentée par un cycle de longueur 6. Il possède (p+1)·(2p+2)-2 sommets et est de degré maximum 3. Sont dual est le graphe whexagon.

       Ex: gengraph hexagon 20 20 -dele 0.2 -maincc -visu

whexagon p q

Comme le graphe hexagon p q sauf que chaque hexagone est remplacé par une roue de taille 6 (chaque hexagone possède un sommet connecté à ses 6 sommets). C'est le dual de l'hexagone. Il possède p·q sommets de plus que l'hexagone p q.

hanoi n b

Graphe de Hanoï généralisé, le graphe de de Hanoï classique est obtenu avec b=3. Le paramètre n correspond au nombre de disques et b au nombre de piquets. La numérotation des sommets (avec -label 1) correspond aux mots de n lettres choisies parmi l'alphabet [0,b[, indiquant sur quel piquet est chacun des disque. Par exemple, si n=4, alors "2010" indique que le disque 1 est sur le piquet 2, le disque 2 et le disque 4 sur le piquet 0 et le disque 3 sur le piquet 1. Sur un piquet donné, les disques sont ordonnés selon leur taille croissante. Une arête correspond à un mouvement possible. Par exemple "2010" est voisin de "2012". Pour b=3, il est 3-coloriable et hamiltonien. Résoudre le problème de la tour de Hanoï revient à cherche un chemin de "00...0" à "22...2". Le plus court d'entre eux est de longueur ≤ 2^n - 1 (c'est égale si b=3).

[Ce graphe est à revoir, ce n'est plus le graphe Hanoï au delà de b>3. Voir p. 257 du livre [HKP18] où il y a la description du graphe de Hanoi pour n et b quelconque.]

Il est planaire avec b^n sommets et peut être défini de manière récursive comme suit. Le niveau n>0 est obtenu en faisant b copies du niveau n-1 qui sont connectés comme un cycle par une arête, le niveau 0 étant le graphe à un sommet. On obtient le graphe de sierpinski n b en contractant ces arêtes là. Il faut b≥2 et n≥0. Lorsque n=2, on obtient un sorte de fleur, pour n=1 c'est un cycle et pour b=2 il s'agit d'un chemin.

sierpinski n b

Graphe de Sierpiński généralisé, le graphe classique, le triangle Sierpiński qui est planaire, est obtenu avec b=3. Il a ((b-2)·b^n+b)/(b-1) sommets et est défini de manière récursive comme suit. Le niveau n est obtenu en faisant b copies du niveau n-1 qui sont connectés comme un cycle, le niveau 1 étant un cycle de b sommets. Il faut b≥3 et n≥1. À la différence du graphe d'Hanoï, les arêtes du cycle sont contractées. Le graphe de Hajós est obtenu avec n=2 et b=3. Pour n=1 il s'agit d'un cycle.

banana n k

Arbre à n·(k+1)+1 sommets composés de n>0 copies d'étoiles à k branches connectées, par une feuille, à un unique sommet. Si k=0, il s'agit d'un stable à k+1 sommets.

moser

Graphe "Moser spindle" découvert par les frères Moser. C'est un "unit distance graph" du plan (deux points sont adjacents s'ils sont à distance exactement 1) de nombre chromatique 4. Il est planaire et possède 7 sommets. On ne connaît pas d'unit distance graphe avec un nombre chromatique supérieur. C'est aussi le complémentaire du graphe K_{3,3} dont une arête a été subdivisée.

markstrom

Graphe de Markström. Il est cubique planaire à 24 sommets. Il n'a pas de cycle de longueur 4 et 8.

robertson

Graphe de Robertson. C'est le plus petit graphe 4-régulier de maille 5. Il a 19 sommets, est 3-coloriable et de diamètre 3.

wiener-araya

Graphe découvert en 2009 par Wiener & Araya. C'est le plus petit graphe hypo-Hamiltonien planaire connu, c'est-à-dire qu'il n'a pas de cycle Hamiltonien mais la suppression de n'importe quel sommet le rend Hamiltonien. Il possède 42 sommets, 67 arêtes, et est de diamètre 7.

zamfirescu

Graphe de Zamfirescu à 48 sommets découvert en 2007. Il est planaire et hypo-Hamiltonien. C'est le second plus petit (voir wiener-araya). Il possède 76 arêtes et a un diamètre de 7.

hatzel

Graphe de Hatzel. Il est planaire, de diamètre 8, possède 57 sommets et 88 arêtes, et est hypo-Hamiltonien (voir wiener-araya). C'était le plus petit planaire hypo-Hamiltonien connu avant le graphe de Zamfirescu.

clebsch n

Graphe de Clebsch d'ordre n. Il est construit à partir d'un hypercube de dimension n en ajoutant une arête entre chaque paire de sommets opposés, c'est-à-dire à distance n. Le graphe classique de Clebsch est réalisé pour n=4 dont le diamètre est deux.

gear n

Graphe planaire à 2n+1 sommets composé d'une roue à n rayons ("wheel n") et de n sommets chacun connectés deux sommets voisins consécutifs du bord de la roue. Il est construit à partir du graphe "cage 2n 2 0 ." auquel on ajoute un sommet central. Pour n=3, c'est le complémentaire de "helm 3".

helm n

Graphe planaire à 2n+1 sommets composé d'une roue à n≥3 rayons ("wheel n") et de n sommets pendants connectés au bord de la roue. Pour n=3, c'est le complémentaire de "gear 3".

haar n

Graphe de Haar H(n) pour l'entier n>0. C'est un graphe biparti régulier possédant 2k sommets où k=1+⎣ log₂(n)⎦ est le nombre de bits dans l'écriture binaire de n. Ses sommets sont les u_i et v_i pour i=0,…,k-1. Le sommet u_i est adjacent à v_{i+j mod k} ssi le bit j de n vaut 1 (j=0,…,k-1). Si n est impair, H(n) est connexe et de maille 4 ou 6. La valeur maximale de n est 2^32-1 = 4,294,967,295 correspondant à un graphe de 64 sommets. On retrouve respectivement les graphes de Franklin (n=37), de Heawood (n=69) et de Möbius-Kantor (n=133). On a aussi que H(2^n-1) est le biparti K_{n,n}, H(2^n) est "matching n+1", H(2^n+1) est un cycle à n+1 sommets, H(2^n+3) est le "mobius n+1" si n est pair et le "prism n+1" si n est impair, et H(3·2^n-1) est le "crown n+2".

turan n r

Graphe de Turán à n sommets et r parts. Il s'agit d'un graphe r-parti complet de n sommets avec r-(n mod r) parts de ⎣ n/r⎦ sommets et (n mod r) parts de ⎡ n/r⎤ sommets. Il faut n≥r>0. On peut aussi le définir comme le graphe ayant une arête entre i et j ssi |i-j| mod r ≠ 0. C'est la définition utilisée pour générer ce graphe. Il est régulier lorsque r divise n. Il possède ⎣(r-1)n^2/(2r)⎦ arêtes et est de nombre chromatique r. C'est le graphe sans clique de taille r+1 ayant le plus grand nombre d'arêtes. Lorsque n=r, il s'agit d'une clique. Lorsque n=r+1, il s'agit d'une clique moins une arête. Lorsque n=2r, il s'agit du "cocktail party graph" et pour n=8 et r=4 le graphe est 1-planar. Lorsque n=3r, il s'agit du graphe de Moon-Moser, le graphe possédant le plus grand nombre de cliques maximales (soit 3^(n/3)). Lorsque n=6 et r=3, c'est l'octaèdre.

klein p q

Maillage quadrangulaire de genre un, incluant le tore, la bouteille de Klein et le plan projectif. C'est un graphe 4-régulier composé d'une grille |p|×|q| augmentée d'arêtes connectant les bords opposés. La connexion est torique ou en twist suivant le signe de chaque dimension (>0 pour torique et <0 pour twist). Pour la bouteille de Klein, il faut p·q<0, et pour le plan projectif il faut p<0 et q<0. Le nombre chromatique est 4 si |p|≠1 et |q|≠1 (cas d'un cycle) et qu'il y a une dimension <0 impaire, ou que p·q=-4 (K₄). Sinon il est < 4. Les plus petits exemples avec un nombre chromatique 4, à part K₄, sont "klein 3 -3" et "klein -3 -3" (qui de plus est sans K₃). Par défaut, les sommets sont dessinés selon une grille |p|×|q|.

       Ex: gengraph klein -3 -4 -label -1 -xy noise .3 .7 -dot len 1 -visu

flower_snark n

Graphe cubique à 4n sommets construit de la manière suivante: 1) on part de n étoiles disjointes à 3 feuilles, la i-ème ayant pour feuilles les sommets notés u_i,v_i,w_i, i=1…n; 2) pour chaque x∈{u,v,w}, x_1-⋯-x_n induit un chemin; et enfin 3) sont adjacents: u_0-u_n, v_0-w_n et w_0-v_n. Pour n>1, ces graphes sont non planaires, non Hamiltoniens, 3-coloriables et de maille au plus 6. Pour n=1, il s'agit d'un K_{1,3} (claw).

biggs n

Graphe de Biggs-Smith généralisé. Il est cubique sauf pour n=1,2,4,8,16 où son degré maximum est 3. Il possède 6n sommets partitionnés en six blocs de n sommets de numéros consécutifs. Les blocs sont connectés comme le graphe H selon un produit cartésien: les sommets homologues dans chaque blocs (de même modulo n) sont adjacents. Chaque bloc (0…5) induit un anneau de corde de longueur c=0,1,2,4,8 répartis comme ceci:

           2   0     [2n,3n[      [0,n[
           |   |       c=4         c=1
           |   |        |           |
           5---4     [5n,6n[ --- [4n,5n[
           |   |       c=0         c=0
	   |   |        |           |
           1   3      [n,2n[     [3n,4n[
                       c=2         c=8

Donc deux sommets de deux blocs différents sont adjacents si leurs blocs sont adjacents dans H et s'ils ont même modulo n (sommets homologues). Et deux sommets dans un même bloc sont adjacents si leurs différences modulo n vaut c. Sinon, ils ne sont pas adjacents.

udg n r

Graphe géométrique aléatoire (random geometric graph) sur n points du carré [0,1[² (distribution par défaut). Deux sommets sont adjacents si leurs points sont à distance ≤ r. Il s'agit de la distance selon la norme L2 (par défaut), mais cela peut être changée par l'option -norm. Le graphe devient connexe avec grande probabilité lorsque r=rc ~ √(ln(n)/n). Si r<0, alors le rayon est initialisé à rc. Un UDG (unit disk graph) est normalement un graphe d'intersection de disques fermés de rayon 1.

gabriel n

Graphe de Gabriel. Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[² (distribution par défaut). Les points i et j sont adjacents ssi le plus petit disque (voir -norm) passant par i et j ne contient aucun autre point. Ce graphe est connexe et planaire à condition toutefois qu'ils n'existe pas 4 points co-cycliques et par paires diamétralement opposées (dans ce cas une clique et des croisements d'arêtes apparaissent). C'est un sous-graphe du graphe de Delaunay. Son étirement est non borné.

rng n

Graphe du proche voisinage (Relative Neighborhood Graph). Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[². Les points i et j sont adjacents ssi il n'existe aucun point k tel que max{d(k,i),d(k,j)} < d(i,j) où d est la distance (L2 par défaut, voir -norm). Dit autrement, la "lune" définie par i et j doit être vide. Ce graphe est planaire et connexe. C'est un sous-graphe du graphe de Gabriel.

knng n k

Graphe des k plus proches voisins (k-Nearest Neighbor Graph). Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[² (distribution par défaut). Chaque point i est connecté aux k plus proches autres points (par défaut selon la norme L2, voir -norm). Si la norme est L2, le degré des sommets est ≤ 6k. Il peut comporter des croisements d'arêtes dès que k>1. Cependant, chaque arête ne peut être coupée que O(k²) fois. Plus précisément, c'est un t-planaire pour t≤78k^2-6k (cf. [DMW19]). À partir de k=3 apparaît une composante connexe de taille linéaire.

mst n

Graphe aléatoire géométrique définissant un arbre couvrant de poids minimum du graphe complet Euclidien sur n points tirés aléatoirement uniformément dans le carré [0,1[² (distribution par défaut). Par défaut la distance est la norme L2 (voir -norm).

       Ex: gengraph mst 2000 -xy seed 1 .3 -visu

thetagone n p k w

Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[² (distribution par défaut). En général le graphe est planaire et connexe avec des faces internes de longueur au plus p (pour k diviseur de p et w=1). On peut interpréter les paramètres comme suit: p≥3 est le nombre de cotés d'un polygone régulier, k≥1 le nombre d'axes (ou de direction), et w∈[0,1] le cône de visibilité. Toute valeur de p<3 est interprétée comme une valeur infinie, et le polygone régulier correspondant interprété comme un cercle. L'adjacence entre une paire de sommets est déterminée en temps O(kn).

Plus formellement, pour tout point u et v, et entier i, on note P_i(u,v) le plus petit p-gone (polygone convexe régulier à p cotés) passant par u et v dont u est un sommet, et dont le vecteur allant de u vers son centre forme un angle de i·2𝜋/k avec l'axe des abscisses, intersecté avec un cône de sommet u et d'angle w·(p-2)·𝜋/p (w·𝜋 si p est infini) et dont la bissectrice passe par le centre du p-gone. Alors, u est voisin de v s'il un existe au moins un entier i∈[0,k[ tel que l'intérieur de P_i(u,v) est vide. La distance entre u et le centre du p-gone définit alors une distance (non symétrique) de u à v.

Si w=1 (visibilité maximale), P_i est précisément un p-gone. Si w=0 (visibilité minimale), P_i se réduit à l'axe d'angle i·2𝜋/k pour un entier i. Si w=.5, P_i est un cône formant un angle égale à 50% de l'angle défini par deux cotés consécutifs du p-gone, ce dernier angle valant (p-2)𝜋/p. Si w=2p/((p-2)k) (ou simplement 2/k si p est infini) alors la visibilité correspond à un cône d'angle 2𝜋/k, l'angle entre deux axes. Comme il faut w≤1, cela implique que k≥2p/(p-2) (k≥2 si p infini). On retrouve le Theta_k-Graph pour chaque k≥6 en prenant p=3 et w=6/k, le demi-Theta-Graph pour tout k≥3 en prenant p=3 et w=3/k, le Yao_k-Graph pour chaque k≥2 en prenant p=0 (infini) et w=2/k, et la triangulation de Delaunay si p=0 (infini), k très grand et w=1. En fait, ce n'est pas tout-à-fait le graphe Yao_k, pour cela il faudrait que u soit le centre du polygone (c'est-à-dire du cercle).

pat p q r

Graphe possédant pqr sommets, issu d'un jeu à un joueur proposé par Pat Morin (Barbade, mars 2016). Le jeu se déroule sur une grille p×q et comprend r coups. Un coup est un ensemble de positions de la grille strictement croissantes (coordonnées en x et en y strictement croissantes). De plus, si la position (x,y) est jouée alors toutes les positions situées sur la même ligne mais avec une abscisse au moins x ou sur la même colonne mais avec une ordonnées au moins y sont interdites pour tous les coups suivants. Le score est le nombre total de positions jouées en r coups. Il s'agit de trouver le score maximum. Lorsque r=1, le score maximum vaut min(p,q). Lorsque p=q=n et r=2, alors le score maximum vaut ⎣ 4n/3⎦. La question est ouverte lorsque r>2, c'est au moins n^1.516 pour r=n où la constante vaut log_9(28).

Les sommets du graphes sont les positions dans les r grilles p×q et deux sommets sont adjacents les positions sont en conflits. Le score du jeu est alors un ensemble indépendant du graphe. Si r=1, le graphe est une grille p×q. Ce graphe active l'option -pos car un dessin de ce graphe (sous forme de grilles) est proposé.

       Ex: gengraph pat 4 4 4 -check kindepsat 8 | glucose -model

line-graph n k

Graphe ligne aléatoire à n sommets et de paramètre k>0 entier. Plus k est petit, plus le graphe est dense, le nombre d'arêtes étant proportionnel à (n/k)². Si k=1, il s'agit d'une clique à n sommets. Ces graphes sont obtenus en choisissant, pour chaque sommet, deux couleurs de [0,k[. Deux sommets sont adjacents ssi ils possèdent la même couleur. Il contient le graphe "uno n k k" comme sous-graphe. Ces graphes sont claw-free (c'est-à-dire sans K_{1,3} induit). Tout graphe ligne est claw-free, et les graphes ligne connexes avec un nombre pair de sommets possèdent toujours un couplage parfait. On rappelle qu'un graphe G est le graphe ligne d'un graphe H si les sommets de G correspondent aux arêtes de H et où deux sommets de G sont adjacents ssi les arêtes correspondantes dans H sont incidentes. On parle parfois de graphe adjoint.

uno n p q

Graphe ligne aléatoire à n sommets issu d'un graphe biparti de parts de taille p>0 et q>0. Plus précisément, les sommets sont des paires (i,j) d'entiers aléatoires de [0,p[ × [0,q[, pas nécessairement distinctes. Les sommets (i,j) et (i',j') sont adjacents ssi i=i' ou j=j'. C'est un sous-graphe induit du produit cartésien de deux cliques, K_p × K_q. Ce graphe est géométrique, les sommets étant des points de la grille p×q. Les sommets représentent aussi des cartes du jeu de UNO et les arêtes indiquent si un carte peut être jouée consécutivement à une autre. Le graphe "uno n k k" est un sous-graphe de "line-graph n k".

unok n p q k_p k_q

Graphe "uno n p q" particulier où les n points correspondant aux sommets sont pris uniformément parmi les ensembles de n points distincts de [0,p[ × [0,q[ ayant au plus k_p sommets par ligne et k_q par colonne. Il faut n ≤ min{p·k_p,q·k_q} et p, q, k_p, k_q>0. Si k_p<0, alors on fait comme si k_p=p, de même pour k_q=q si k_q<0. Contrairement à uno, deux sommets ont toujours des coordonnées distinctes. Le graphe résultant est de degré au plus k_p+k_q-2, et est de path-width (et aussi de tree-width) au plus celle du produit de clique K_{k_p} × K_{k_q} soit environ k_p·k_q/2. Le temps de génération des n points est en O(npq) contre O(n) pour uno, mais une optimisation (algorithme par rejets) fait qu'il est très souvent en O(n+p+q), dans les cas peu dense par exemple. Si k_p ou k_q=1, le graphe est une union de cliques, et si k_p=k_q=2 et n=2p=2q, c'est une union de cycles.

       Ex: gengraph unok 200 100 100 3 2 -visu

wpsl n p q
upsl n p q
wpsld n p q
upsld n p q

Weighted/Uniform Planar Stochastic Lattice. Graphe planaire aléatoire connexe dont les sommets correspondent à certains points d'une grille p×q et les arêtes à des lignes horizontales ou verticales. Il est généré selon un processus en n≥0 étapes décrit dans un paragraphe ci-après. Il faut p,q≥2. Il comprend au plus 3n+1 faces internes rectangulaires, appelés blocs, qui forment une partition des cases de la grille p×q. C'est un graphe 2-dégénéré qui possède au plus min{5n+4,p·q} sommets dont 4 sont de degré 2, les autres étant de degré 3 ou 4 selon une répartition moyenne 80%-20%. La variante wpsld (ou upsld) représente le graphe dual qui est 4-dégénéré et connexe. Les sommets (au plus 3n+1) correspondent aux blocs (positionnés en leurs centres), deux blocs étant adjacents s'ils ont un bord en commun. Pour le dual les coordonnées des centres des blocs sont doublées pour être entières, et le dessin n'est pas forcément planaire. L'option -directed permet d'obtenir une 2-orientation et une 4-orientation pour le dual.

       Ex: gengraph -seed 0 wpsl 100 400 500 -dot scale auto -visu
           gengraph -seed 0 wpsld 100 400 500 -dot scale auto -visu
	   gengraph wpsl 2500 70000 70000 -dot scale auto -visu
	   gengraph wpsl 2 10 10 -dot scale auto -xy grid 10 -visu

Le graphe est construit en n étapes. Au départ il y a un seul bloc contenant toutes les cases d'une grille p×q. Le bord de ce bloc correspond aux 4 coins de la grille et forme un cycle de longueur 4. À chacune des n étapes ont sélectionne un bloc B parmi ceux déjà construits selon une probabilité proportionnelle de sa surface (pour wpsl) ou uniformément parmi tous les blocs (pour upsl). Ici la surface d'un bloc est le nombre de cases -- et non de points -- de la grille qu'il contient. Puis B est découpé selon une croix dont le centre est un point de la grille interne de B (pas sur un bord) choisi aléatoirement uniformément. (La variante consistant à découper un bloc en deux correspond au graphe wdis et ses variantes.) Le bloc n'est pas découpé s'il ne contient pas de points de la grille. Une autre façon de concevoir le processus pour wpsl est de choisir n points de la grille p×q aléatoirement et uniformément. Puis, depuis chaque point et dans un ordre quelconque, faire pousser une croix jusqu'à atteindre un bord ou une croix précédente, les points se trouvant sur le passage d'une croix étant supprimés. La création du graphe prend un temps O(nlogn) en moyenne, indépendant des dimensions p et q qui peuvent être donc relativement grandes. Ensuite, le test d'adjacence, lié à sa k-orientation, est constant.

wdis n p q
udis n p q
wdisd n p q
udisd n p q

Rectangular Dissection. Graphe planaire aléatoire connexe dont les sommets correspondent à certains points d'une grille p×q et les arêtes à des lignes horizontales ou verticales. Il est généré selon un processus en n≥0 étapes similaires à wpsl (et ses variantes). Les variantes wdisd et udisd correspondent au graphe dual. À chaque étape du processus on sélectionne aléatoirement un bloc, soit proportionnellement à sa surface (wdis) soit uniformément (udis), que l'on le coupe en deux sous-blocs. Le sens de la découpe (verticalement ou horizontalement) est soit aléatoire uniforme (udis) soit selon une probabilité proportionnelle à la longueur des cotés (wdis), préférant découper le plus grand coté. Il possède au plus min{2n+4,p·q} sommets: 4 de degré 2, presque tous les autres de degré 3 sauf quelqu'uns de degré 4. Le dual possède n+1 sommets. Il partage un grand nombres de propriétés communes avec wpsl, en particulier l'orientation. Tous les graphes wpsl peuvent être générés par un wdis.

ngon p c x

Triangulation particulière d'un polygone régulier. Plusieurs types de triangulations sont produites suivant la valeur des paramètres. Elles ont p, 3p ou 4p sommets. Si x&4=0, alors la triangulation a 3p sommets (avec p>0) et est composée d'un triangle équilatéral central. Si x&4=1, alors la triangulation a 4p sommets et est composée d'un carré central avec une diagonale. La triangulation est symétrique dans chacun des 3 ou 4 croissants délimités par chacune des arêtes du polygone central. Si AB est l'une de ces arêtes (A avant B dans le sens direct), alors on note C le point de l'arc de cercle de A à B à distance c de A. On doit avoir c∈[0,p/2]. Les deux bits de poids faible de x définissent comment sont construits les triangulations de l'arc AC et CB. Tous les points de AC sont connectés à A si x&1=1 et à C sinon. Et, tous les points de BC sont connectés à B si x&2=1 et à C sinon. Si x&8=1 alors la triangulation est asymétrique. On remplace c par p-c pour un arc AB sur deux.

Si x=-1, alors il s'agit d'une autre triangulation. Elle a p sommets et est symétrique par rapport à un axe horizontal comprenant trois "fan": un depuis le point 0 vers tous ceux de [c,n-c], un depuis c vers tous ceux de [0,c], et enfin un depuis n-c vers tous ceux de [n-c,n].

Si x=-2, alors il s'agit de la triangulation récursive à 3p sommets. Le paramètre c n'a pas de rôle. Chacun des trois arc est coupé en deux récursivement. Si p n'est pas une puissance de deux, alors le graphe peut ne pas être une triangulation complète, mais le graphe reste cependant planaire.

La triangulation qui expérimentalement minimise le stretch maximum (voir -check stretch) est obtenue avec "ngon p 𝛼p 3" où 𝛼 = 231/512 ≃ 45%. Le stretch maximum est environ 1.455 réalisé entre les sommets u=p+30% et v=3p-20%.

behrend p k

Graphe régulier de p·k sommets possédant un très grands nombre de cycles de longueur k arête-disjoints où p,k ≥ 2. Si p est premier, il en possède exactement p·c! = p^{2-o(1)} où c ~ log(p)/loglog(p). Son degré est 2c! si k>2 ou c! si k=2. Le graphe est défini que p soit premier ou pas. Il est construit à partir de k stables S_0,…,S_{k-1} de chacun p sommets. Chacun des cycles de longueur k contient exactement un élément de chaque S_j qui est le sommet d'indice i+j·x (mod p) dans S_j avec i∈[0,p[ et x∈X où X⊂[0,p[ est un ensemble où k entiers quelconques ne sont jamais en progression arithmétique. On construit X comme l'ensemble de tous les entiers < p/(k-1) s'écrivant sur c chiffres distincts pris dans [0,c[ en base ck+1 avec c maximum. Donc |X|=c!. Lorsque p est petit, le graphe peut ne pas être connexe.

Par exemple, pour p=421 et k=3 on obtient c=3 et X = { 012, 021, 102, 120, 201, 210 } (nombres écrits en base ck+1=10). On vérifie qu'on a bien p > (k-1)·max{X} = 420. Ce graphe et donc 12-régulier possède p·k = 1263 sommets et p·c! = 5052 triangles arête-disjoints car 421 est premier. La table ci-dessous donne en fonction de k et du degré souhaité la plus petite valeur de p=p(k) possible. Si p est plus petit que p(k), alors le degré sera moindre. Lorsque k=2, le degré est c! au lieu de 2·c!.

                     2·2!   2·3!    2·4!       2·5!
              degré    4     12      48        240
    	     ──────────────────────────────────────
               p(2)    6    106   2,359     62,811
               p(3)   15    421  13,885    549,921
               p(4)   28  1,054  46,003  2,419,831
    	     ──────────────────────────────────────

Ces graphes sont utilisés en "property testing" pour montrer qu'il est difficile de déterminer si un graphe dense possède ou pas un cycle de longueur k.

rplg n t

Random Power-Law Graph. Graphe aléatoire à n sommets où les degrés des sommets suivent une loi de puissance d'exposant t>1 (typiquement un réel t∈]2,3[). L'espérance du degré du sommet i=0…n-1 est w_i = (n/(i+1))^(1/(t-1)). La probabilité d'avoir l'arête i-j est min{w_i·w_j/S,1} avec S=∑_k w_k. La valeur communément observée pour le réseau Internet étant t=2.1.

bdrg n_1 d_1 … n_k d_k .

Bounded Degree Random Graph. Graphe aléatoire dont la distribution des degrés des sommets est fixée par les paires (nᵢ,dᵢ) signifiant qu'il y a nᵢ sommets de degré au plus dᵢ. Ainsi "bdrg n 3 ." génère un graphe sous-cubique aléatoire à n sommets, si n est pair. Les sommets sont dupliqués selon leur distribution de degré puis un couplage aléatoire détermine les arêtes. Les boucles et les arêtes multiples sont supprimer. Il suit que le degré des sommets ne dépasse pas dᵢ. Ils peuvent cependant être inférieurs. Le nombre de sommets est n=∑ᵢ nᵢ et le nombre d'arêtes au plus m = ½∑ᵢ (nᵢ·dᵢ). Si cette somme n'est pas entière, alors le degré d'un des sommets ayant dᵢ>0 est diminué d'un. (C'est un sommet avec dᵢ>0 avec le plus grand i qui est choisi.)

fdrg n_1 d_1 … n_k d_k .

Fixed Degree Random Graph. Graphe aléatoire asymptotiquement uniforme dont les degrés des sommets sont fixées par les paires (nᵢ,dᵢ) signifiant qu'il y a nᵢ sommets de degré dᵢ. La suite des degrés doit être graphique, à savoir qu'il existe au moins un graphe simple ayant ces degrés (sinon une erreur est affichée). Ainsi "fdrg n 3 ." génère un graphe cubique aléatoire asymptotiquement uniforme, à condition que n soit pair. Il est possible d'obtenir des graphes non connexe, comme avec "fdrg 3 2 1 0 ." composé d'un triangle et d'un sommet isolé. La complexité est en moyenne O(mΔ+Δ⁴) où m=∑ nᵢdᵢ et Δ=max{dᵢ}, et pour être asymptotiquement uniforme, il faut Δ=o(m^¼) ou Δ=o(√n) pour les graphes réguliers (tous les dᵢ égaux ou k=1).

matching n

Graphe composé de n arêtes indépendantes, c'est-à-dire de n copies de K₂. L'option -directed permet d'obtenir une 1-orientation.

load file[:range]
loadc file[:range]

Graphe défini à partir du fichier "file" ou de l'entrée standard si file vaut "-". Si "file" est une famille de graphes, alors il est possible d'utiliser la variante "file:range" pour préciser l'identifiant du graphe souhaité (sinon c'est le premier graphe de la famille qui sera considéré). Le graphe (ou la famille) doit être au format standard, les sommets numérotés par des entiers positifs. Les caractères situés sur une ligne après "//" sont ignorés, ce qui permet de mettre des commentaires.

Le temps et l'espace nécessaire au chargement du graphe sont linéaires en la taille du fichier (si "file" est une famille de graphes, le fichier est entièrement lu). Cependant, pour la génération à proprement parlée du graphe final, qui peut comprendre l'option -not par exemple, toutes les arêtes potentielles, soit O(n²), sont passées en revue pour être testées. La variante "loadc" (pour "load & check") permet une génération plus rapide lorsqu'utilisée avec -check (ou les alias utilisant -check, comme -maincc par exemple). Elle permet de passer directement de l'étape de chargement du graphe à l'étape du test de l'algorithme en sautant la phase de génération des arêtes. En contre-partie, le graphe n'est pas affiché et les options comme -not, -permute, -delv, -dele, etc. n'ont plus d'effet. La variante "loadc file" est environ 20% plus rapide que "load file -fast".

Pour charger un graphe au format dot on peut utiliser le script dot2gen.awk en amont, comme dans l'exemple suivant:

           nop file.dot | awk -f dot2gen.awk | gengraph load -

Le filtre nop de GraphViz, qui est recommandé mais pas nécessaire, permet de standardiser le format dot initial. Il transforme par exemple les expressions du type "a--{b;c;}" en "a--b;a--c;".

Notez que la suite d'options "load file -fast -format dot<type>" permet de convertir "file" au format <type> souhaité. Ce graphe active l'option -directed si "file" contient au moins un arc. Dans ce cas l'option -undirected n'aura pas d'effet.

GRAPHES ORIENTÉS :

aqua c_1 … c_n .

Graphe orienté dont les sommets sont les suites de n entiers positifs dont la somme fait c_1 et dont le i-ème élément est au plus c_i. Ils représentent les façons de répartir une quantité c_1 de liquide dans n récipients de capacité c_1 … c_n. Il y a un arc u->v s'ils existent i et j tels que v est le résultat du versement du récipient c_i vers le récipient c_j. Le graphe est isomorphe au graphe où les c_i=0 ont été supprimés, les c_i ont été triés par ordre décroissant et où c_1 a été remplacé par min{c_1,c_2+…+c_n}. Par exemple, "aqua 4 1 0 2 ." est isomorphe à "aqua 3 2 1 .". Le nombre de sommets ne peut pas dépasser binom{n+c_1}{n}. Le graphe peut être connexe mais non fortement connexe comme "aqua 2 2 .".

       Ex: gengraph aqua 3 2 1 . -label 1 -dot filter dot -visu

collatz n a_0 b_0 … a_{k-1} b_{k-1} .

Graphe de Collatz généralisé. Il est basé sur la relation C: x ↦ (aᵢ·x + bᵢ)/k, définie pour tout entiers x>0, où i = x%k et où aᵢ,bᵢ sont entiers (pas forcément positifs). Il faut aᵢ·i + bᵢ ≡ 0 (mod k) pour tout i pour que C(x) soit entier, sinon ⎣C(x)⎦ est considérée et C⁻¹ n'est plus forcément injective. Les entiers générés forment les sommets du graphe, les arcs étant les relations x→C(x).

Le graphe pour le problème "3x+1", défini par la relation x↦x/2 si x≡0 (mod 2) et x↦x/2 si x≡1 (mod 2), est donc le graphe "collatz n 1 0 3 1 .".

Si n>0, la boule de volume n est générée en itérant la relation inverse depuis x=1, soit C⁻¹: x ↦ (k·x-bᵢ)/aᵢ pour chaque i tel que aᵢ divise k·x-bᵢ. Il est important que C(x) soit entier pour que C⁻¹ soit injective. Si n<0, la relation est itérée depuis chaque entier x∈[1,|n|]. Dans le cas n>0, le graphe est connexe et comprend au plus n sommets, alors que pour n<0, il peut ne pas être connexe et contenir plus de |n| sommets. Il s'agit de deux sous-graphes (n>0 et n<0) induit du même graphe infini. Dans tous les cas c'est un graphe orienté avec au plus un successeur (arc sortant) et k prédécesseurs (arcs entrant), et peut contenir des cycles dont des boucles et des arcs symétriques.

       Ex: gengraph collatz -65 1 0 5 -1 5 1 3 1 . -label 1 -visu

La fameuse conjecture de Collatz pour le problème "3x+1" affirme que le graphe "collatz n 1 0 3 1 ." est connexe quel que soit n<0 (voir aussi "syracuse n"). Pour de grandes familles de coefficients aᵢ,bᵢ, il est conjecturé que le graphe possède un nombre constant de composantes connexes, comme par exemple 3 pour "collatz n 1 0 5 1 .". Savoir si le graphe généralisé de Collatz est connexe est indécidable, même si tous les bᵢ=0 [Conway'72].

La génération du graphe proprement dite est basée sur une file initialisée aux valeurs 1..|n| pour lesquelles la relation C est successivement appliquée (si n<0). Il s'agit donc d'une sorte de parcours en largeur du graphe depuis n sources en parallèle. La construction est limitée arbitrairement à n² sommets car, suivant les coefficients aᵢ,bᵢ, ce parcours peut ne pas converger pour certain x∈[1,|n|]. Attention! Les valeurs C(x) négatives sont exclues du graphe, ce qui peut aussi exclure les valeurs dépassant 2³¹ et donc déconnecter le graphe. Si n>0, on initialise la file avec seulement la valeur 1 et on itère les k relations inverses, si elles s'appliquent, jusqu'à produire exactement n sommets. Il s'agit donc d'un simple parcours en largeur depuis 1. Bien que le nombre d'arcs soit linéaire, la génération de tous les successeurs prend un temps quadratique en le nombre de sommets final du graphe si n<0, et O(kn²) si n>0.

GRAPHES COMPOSÉS :

mesh p q (= grid p q .)

Grille 2D de p x q sommets.

hypercube d (= grid 2 … 2 .)

Hypercube de dimension d.

path n (= grid n .)

Chemin à n sommets.

cycle n (= ring n 1 .)

Cycle à n sommets.

torus p q (= grid -p -q .)

Tore à p x q sommets.

stable n (= ring n .)
empty n (= ring n .)

Stable à n sommets.

clique n (= -not ring n .)

Graphe complet à n sommets.

bipartite p q (= rpartite p q .)

Graphe biparti complet K_{p,q}.

utility (= rpartite 3 3 .)

Graphe biparti complet K_{3,3} qui doit son nom au problème de la connexion planaire de trois maisons à trois stations (eau, gaz, électricité). C'est aussi le graphe de Haar H(7).

domino (= grid 2 3 .)

Graphe planaire à 6 sommets composé de deux carrés partageant une arête.

kite (= -not banana 1 3)

Kite Graph, graphe à cinq sommets composé de deux triangles partageant une arête et d'un sommet pendant (degré 1) attaché à un sommet de degré deux. C'est aussi un "parachute 2".

parapluie n (= -not parachute n)

Graphe planaire à n+3 sommets, complémentaire du parachute. Le graphe "parapluie" classique correspond à n=4.

hourglass (= barbell 3 3 0)

Graphe Papillon ou encore Butterfly. Il a 5 sommets et est composé de deux triangles partageant un sommet.

cuboctahedron (= linial 4 2)

Cuboctaèdre: graphe planaire 4-régulier à 12 sommets. Il possède 24 arêtes et 14 faces qui sont des triangles ou des carrés. C'est le dual du rhombic-dodécaèdre.

octahedron (= antiprism 3)

Octaèdre: graphe 4-régulier planaire à 6 sommets ayant 8 faces triangulaires. Il s'agit de deux pyramides dont la base à 4 sommets est commune. C'est aussi le graphe de Johnson J(4,2).

d-octahedron d (= -not matching d)

Octaèdre de dimension d: obtenu à partir d'un octaèdre de dimension d-1 auquel on ajoute deux sommets universels, l'octaèdre de dimension 1 étant composé d'un stable de deux sommets. L'octaèdre classique est obtenu avec d=3, pour d=2 il s'agit d'un carré.

tetrahedron (= -not ring 4 .)

Tétraèdre: pyramide composée de 4 faces triangulaires. C'est aussi une clique à 4 sommets.

cube (= crown 4)
hexahedron (= crown 4)

Hypercube de dimension 3, graphe planaire cubique à 8 sommets où toutes les faces sont des rectangles. C'est aussi un hexaèdre (6 faces carrées) ou encore le graphe de Haar H(11).

associahedron (= flip 6)

Associaèdre (3D): graphe planaire cubique à 14 sommets composé de 3 faces carrées et 6 faces pentagonales.

johnson n k (= -not kneser n k k-2)

Graphe de Johnson J(n,k). Les sommets sont tous les sous-ensembles à k éléments de [0,n[ (il faut donc 0≤k≤n). Deux sommets sont adjacents ssi leurs ensembles correspondant ont k-1 éléments en commun. La distance entre deux sommets est la distance de Hamming entre les ensembles correspondant. Ils sont réguliers de degré k(n-k), de diamètre min{k,n-k}, de sommet-connectivité k(n-k). Ils sont aussi distance réguliers. J(n,1) est la clique K_n, J(n,2) est le complément du graphe de Kneser K(n,2) et le graphe ligne de K_n. En fait, tout sous-graphe induit de J(n,2) est un graphe ligne. J(4,2) est l'octaèdre, J(5,2) le complément du graphe de Petersen.

odd n (= kneser 2n-1 n-1 0)

Odd graph de paramètre n>0. Il s'agit du graphe de Kneser K(2n-1,n-1) dont les sommets correspondent aux binom(2n-1,n-1) sous-ensembles à n-1 éléments de {0,…,2n-2}. Le plus petit cycle impair est toujours de longueur 2n-1. Il est n-régulier et son diamètre est n-1. Il est distance-transitif (automorphisme entre paires de sommets à même distance) et donc distance-régulier. Si n>3, il est Hamiltonien et de maille 6. Il n'est jamais un graphe de Cayley si n>2. Pour n=2, il s'agit de K₃ et pour n=3 du graphe de Petersen (et donc non Hamiltonien).

biggs-smith (= biggs 17)

Graphe de Biggs-Smith. Il est cubique, possède 102 sommets, et est distance-régulier. Il n'existe que 13 graphes cubiques distance-réguliers. De nombre chromatique 3, son diamètre est 7, comme son rayon, alors que sa maille est 9.

claw (= rpartite 1 3 .)

Graphe biparti complet K_{1,3}.

star n (= rpartite 1 n .)

Arbre (étoile) à n feuilles et de hauteur 1.

tree n (= arboricity n 1)

Arbre plan enraciné aléatoire uniforme à n sommets. Les sommets sont numérotés selon un parcours en profondeur depuis la racine et le long de la face extérieure.

caterpillar n (= grid n-r . -star r)

Arbre à n sommets dont les sommets internes (de degré > 1) induisent un chemin. Il est obtenu à partir d'un chemin de longueur n-r (où r est un nombre aléatoire entre 0 et n-1) et en appliquant l'option -star r. Si l'option -seed est présente, (pour intervenir sur la valeur "r"), il est important qu'elle figure avant caterpillar. [Ce graphe est désactivé, voir l'option -star.]

outerplanar n (= kpage n 1)

Graphe planaire-extérieur aléatoire connexe à n sommets (plan et enraciné). Ils sont en bijection avec les arbres plans enracinés dont tous les sommets, sauf ceux de la dernière branche, sont bicoloriés. Les sommets sont numérotés le long de la face extérieure. C'est aussi une numérotation selon un parcours en profondeur depuis la racine de l'arbre bicolorié. Il est aussi possible de générer des graphes planaires-extérieurs aléatoires Hamiltoniens, donc 2-connexes, avec "planar n f -1" ou "polygon n". L'option -directed permet d'obtenir une 2-orientation.

squaregraph n (= planar n 4 4)

Squaregraph aléatoire à n faces. Ce sont des graphes planaires 2-connexes dont toutes les faces (sauf l'extérieure) sont des carrées. De plus, les sommets des faces internes sont de degré au moins 4. Ce sont des sous-graphes de quadrangulations et donc des 2-pages. Ce sont éqalement des graphes médians: pour chaque triplet de sommets {u,v,w}, il existe un seul sommet, le médian, appartenant à un plus court chemin u-v, de v-w et de u-w. L'option -directed permet d'obtenir une 2-orientation.

random n p (= -not ring n . -dele 1-p)

Graphe aléatoire à n sommets et dont la probabilité d'avoir une arête entre chaque paire de sommets est p. L'option -dele étant déjà présente, il n'est pas conseillé de la réutiliser pour ce graphe.

netgraph (= sierpinski 2 3 -not)

Graphe à 6 sommets composé d'un triangle avec un sommet pendant à chacun d'eux. C'est le complémentaire du graphe de Hajós. On peut aussi le générer en utilisant "fdrg 3 3 3 1 .".

sunflower n (= cage 2n 2 2 .)

Tournesol à n pétales. C'est un graphe planaire-extérieur à 2n sommets composé d'un cycle de longueur n≥3 où chaque arête partage le coté d'un triangle. C'est le graphe "gear n" sans le sommet central. Pour n=3, c'est le graphe de Hajós.

gem (= fan 4 1)

Graphe à 5 sommets composé d'un chemin et d'un sommet universel.

egraph (= comb 3)

Arbre à 6 sommets et 3 feuilles en forme de E.

tgraph (= banana 1 3)
fork (= banana 1 3)

Fork Graph, arbre en forme de T à 5 sommets dont 3 feuilles.

ygraph (= banana 3 1)

Arbre à 7 sommets composé d'une étoile à trois branches.

cross (= banana 1 4)

Cross Graph, arbre à six sommets en forme de croix chrétienne.

knight p q (= chess p q 1 2)

Graphe des déplacements possible du chevalier dans un échiquier p q.

antelope p q (= chess p q 3 4)

Graphe des déplacements possible d'une antilope dans un échiquier p q, une antilope étant une pièce hypothétique se déplaçant de 3 cases selon un axe et de 4 selon l'autre.

camel p q (= chess p q 1 3)

Graphe des déplacements possible d'un chameau dans un échiquier p q, un chameau étant une pièce hypothétique se déplaçant de 1 case selon un axe et 3 de selon l'autre.

giraffe p q (= chess p q 1 4)

Graphe des déplacements possible d'une giraffe dans un échiquier p q, une giraffe étant une pièce hypothétique se déplaçant de 1 case selon un axe et de 4 selon l'autre.

zebra p q (= chess p q 2 3)

Graphe des déplacements possible d'un zèbre dans un échiquier p q, un zèbre étant une pièce hypothétique se déplaçant de 2 cases selon un axe et de 3 selon l'autre.

petersen (= kneser 5 2 0)

Graphe de Kneser particulier. Il est cubique et possède 10 sommets. Il n'est pas Hamiltonien et c'est le plus petit graphe dont le nombre de croisements (crossing number) est 2. C'est le complément du graphe ligne de K₅.

tietze (= flower_snark 3)

Graphe de Tietze. Il est cubique avec 12 sommets. Il possède un chemin Hamiltonien, mais pas de cycle. Il peut être plongé sur un ruban de Möbius, a un diamètre et une maille de 3. Il peut être obtenu à partir du graphe de Petersen en appliquant une opération Y-Delta.

mobius-kantor (= gpetersen 8 3)

Graphe de Möbius-Kantor. Graphe cubique à 16 sommets de genre 1. Il est Hamiltonien, de diamètre 4 et de maille 6. C'est aussi le graphe de Haar H(133).

dodecahedron (= gpetersen 10 2)

Dodécaèdre: graphe planaire cubique à 20 sommets. Il possède 30 arêtes et 12 faces qui sont des pentagones. C'est le dual de l'icosaèdre.

desargues (= gpetersen 10 3)

Graphe de Desargues. Il est cubique à 20 sommets. Il est Hamiltonien, de diamètre 5 et de maille 6.

durer (= gpetersen 6 2)

Graphe de Dürer. Graphe cubique planaire à 12 sommets de diamètre 4 et de maille 3. Il peut être vu comme un cube avec deux sommets opposés tronqués (remplacés par un cycle de longueur 3).

prism n (= gpetersen n 1)

Prisme, c'est-à-dire le produit cartésien d'un cycle à n sommets et d'un chemin à deux sommets. Pour n=3, c'est un graphe de Halin et aussi le complémentaire d'un cycle de longueur 6, et pour n=4 il s'agit du cube.

cylinder p q (= grid p -q .)

Produit cartésien d'un chemin à p sommets et d'un cycle à q sommets. Cela généralise le prisme (prism n = cylinder n 3). Un cube est un "cylinder 2 4".

nauru (= pstar 4)

Graphe de Nauru. C'est un graphe cubique à 24 sommets. Il s'agit d'un graphe "permutation star" de dimension 4. C'est aussi un graphe de Petersen généralisé P(12,5).

heawood (= cage 14 5 -5 .)

Graphe de Heawood. C'est un graphe cubique bipartis à 14 sommets, de maille 6 et de diamètre 3. C'est le graphe d'incidence du plan projectif d'ordre 2 (plan de Fano). Il est 1-planar. C'est le plus petit graphe dont le nombre de croisements (crossing number) est 3. C'est aussi le graphe de Haar H(69).

franklin (= cage 12 5 -5 .)

Graphe de Franklin. C'est un graphe cubique à 12 sommets, de maille 4 et de diamètre 3. C'est aussi le graphe de Haar H(37).

mcgee (= cage 24 12 7 -7 .)

Graphe de McGee. C'est un graphe cubique à 24 sommets, de maille 7 et de diamètre 4.

bidiakis (= cage 12 -4 6 4 .)

Graphe ou cube de Bidiakis. C'est un graphe planaire cubique à 12 sommets. Il est Hamiltonien et son nombre chromatique est 3. On peut le représenter comme un cube où deux faces opposées comportent une arête supplémentaire perpendiculaire joignant deux bord opposés. On peut aussi le représenter comme un cycle avec 3 colonnes et 3 lignes parallèles joignant des sommets opposés (comme une raquette de tennis).

dyck (= cage 32 5 0 13 -13 .)

Graphe de Dyck. C'est un graphe cubique 3-connexe biparti à 32 sommets. C'est le seul graphe cubique à 32 sommets à être symétrique, c'est-à-dire qui est à la fois arête et sommet transitif. Il est aussi torique, c'est-à-dire de genre 1.

pappus (= cage 18 5 7 -7 7 -7 5 .)

Graphe de Pappus. C'est un graphe cubique à 18 sommets, de maille 6 et de diamètre 4.

tutte-coexter (= cage 30 -7 9 13 -13 -9 7 .)

Graphe de Tutte-Coexter appelé aussi 8-cage de Tutte. C'est un graphe cubique à 30 sommets, de maille 8 et de diamètre 4. C'est un graphe de Levi mais surtout un graphe de Moore, c'est-à-dire un graphe d-régulier de diamètre k dont le nombre de sommets est 1+d·S(d,k) (si d impair) ou 2·S(d,k) (si d pair) avec S(d,k)=∑_{i=0}^{k-1} (d-1)^i.

gray (= cage 54 7 -7 25 -25 13 -13 .)

Graphe de Gray. C'est un graphe cubique à 54 sommets qui peut être vu comme le graphe d'incidence entre les sommets d'une grille 3×3×3 et les 27 lignes droites de la grille. Il est Hamiltonien, de diamètre 6, de maille 8, et de genre 7. Il est arête-transitif et régulier sans être sommet-transitif.

chvatal (= cage 12 3 6 3 6 6 3 6 -3 3 -3 3 3 .)

Graphe de Chvátal (1970). C'est le plus petit graphe régulier sans triangle de nombre chromatique 4. Il est 4-régulier, possède 12 sommets, est non-planaire, Hamiltonien et de diamètre 2.

grotzsch (= mycielski 4)

Graphe de Grötzsch. C'est le plus petit graphe sans triangle de nombre chromatique 4 (sans être régulier contrairement au graphe de Chvátal). Il possède 11 sommets et 20 arêtes. Comme le graphe de Chvátal, il est non-planaire de diamètre 2, de maille 4 et Hamiltonien. C'est le graphe de Mycielskian du cycle à 5 sommets.

hajos (= sierpinski 2 3)

Graphe de Hajós. Il est composé de trois triangles deux à deux partageant un sommet distinct. On peut le dessiner comme un triangle dans un triangle plus grand. Il est planaire et possède 6 sommets. C'est un graphe de Sierpinski ou encore le complémentaire d'un "sunlet 3", complémentaire du "netgraph", un "sunflower 3" ou encore "cage 6 2 0 .".

house (= -not grid 5 .)

Graphe planaire à 5 sommets en forme de maison. C'est le complémentaire d'un chemin à 5 sommets.

wagner (= ring 8 1 4 .)

Graphe de Wagner appelé aussi graphe W₈, un cycle à 8 sommets où les sommets antipodaux sont adjacents. C'est un graphe cubique à 8 sommets qui n'est pas planaire mais sans K₅. C'est aussi une échelle de Möbius.

mobius n (= ring n 1 n/2 .)

Échelle de Möbius, graphe cubique à n sommets obtenu à partir d'un cycle à n sommets dont les sommets opposés sont adjacents. Lorsque n est pair, il s'agit d'un ruban de Möbius, c'est-à-dire d'une échelle dont le premier et dernier barreau sont recollés en sens opposé. Pour n≤5, il s'agit d'une clique à n sommets. Il est donc cubique sauf pour n=1,2,3,5. Lorsque n≥5, le graphe n'est plus planaire, et pour n=8, il s'agit du graphe de Wagner.

ladder n (= grid 2 n .)

Graphe échelle à n barreaux, soit une grille à 2 x n sommets.

diamond (= fan 2 2)

Clique à quatre sommets moins une arête. C'est un graphe allumette, c'est-à-dire planaire et distance unitaire.

gosset (= ggosset 8 2 3 6 -1 .)

Graphe de Gosset. Il est 27-régulier avec 56 sommets et 756 arêtes, de diamètre, de rayon et de maille 3. Il est 27-arête-connexe, 27-sommet-connexe et Hamiltonien. C'est localement un graphe de Schläfli, c'est-à-dire que pour tout sommet le sous-graphe induit par ses voisins est isomorphe au graphe de Schläfli, qui est lui-même localement un graphe de Clebsch.

wheel n (=ringarytree 1 0 n 2)

Roue à n rayons. Graphe planaire à n+1 sommets composé d'un cycle à n sommets et d'un sommet universel, donc connecté à tous les autres.

web n r (=ringarytree r 1 n 2)

Graphe planaire à 1+n·r sommets composé d'une étoile à n branches de longueur r, les sommets de même niveau étant connectés par un cycle. Il généralise "wheel n" (r=1).

binary h (= ringarytree h 2 2 0)

Arbre binaire complet de hauteur h. Il possède 2^(h+1)-1 sommets et la racine est de degré deux.

arytree h k r (= ringarytree h k r 0)

Arbre complet de hauteur h où chaque noeud interne à exactement k fils, la racine étant de degré r.

rbinary n (= rarytree n 2 0)
rbinaryz n (= rarytree n 2 1)

Arbre binaire plan aléatoire uniforme à n noeuds internes. Il possède 2n-1 sommets (2n pour la variante rbinaryz) numérotés selon un parcours en profondeur modifié: tous les fils du sommet courant sont numérotés avant l'étape de récursivité. La racine est de degré 2 (=rbinary) ou 1 (=rbinaryz). Le dessin avec dot (-visu) ne respecte pas le plongement de l'arbre. L'option -directed permet d'obtenir une 1-orientation.

tw n k (= ktree n k -dele .5)

Graphe de largeur arborescente au plus k aléatoire à n sommets. Il s'agit d'un k-arbre partiel aléatoire dont la probabilité d'avoir une arête est 1/2. L'option -dele étant déjà présente, il n'est pas conseillé de la réutiliser pour ce graphe. L'option -directed permet d'obtenir une k-orientation.

pw n k (= kpath n k -dele .5)

Graphe de pathwidth au plus k, aléatoire et avec n sommets.

tadpole n p (= barbell -n 1 p)
dragon n p (= barbell -n 1 p)

Graphe à n+p sommets composé d'un cycle à n sommets relié à un chemin à p sommets.

lollipop n p (= barbell n p 0)

Graphe "tapette à mouches" (Lollipop Graph) composé d'une clique à n sommets reliée à un chemin de longueur p. Il a n+p sommets.

pan n (= barbell -n 1 1)

Graphe à n+1 sommets composé d'un cycle à n sommets et d'un seul sommet pendant.

banner (= barbell -4 1 1)

Graphe à 5 sommets composé d'un carré et d'un sommet pendant.

paw (= barbell -3 1 1)

Graphe à 4 sommets composé d'un triangle et d'un sommet pendant.

theta0 (=barbell -5 -5 -2)

Graphe Theta_0. C'est un graphe à 7 sommets série-parallèle obtenu à partir d'un cycle de longueur 6 et en connectant deux sommets antipodaux par un chemin de longueur 2. C'est un graphe allumette, c'est-à-dire planaire et distance unitaire.

nng n (= knng n 1)

Graphe du plus proche voisin (Nearest Neighbor Graph). Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[² (distribution par défaut). Le point i est connecté au plus proche autre point (par défaut selon la norme L2, voir -norm). Ce graphe est une forêt couvrante du graphe rng de degré au plus 6 (si la norme est L2).

td-delaunay n (= thetagone n 3 3 1)

Triangulation de Delaunay utilisant la distance triangulaire (TD=Triangular Distance). Ce n'est malheureusement pas toujours une triangulation, les sommets du bord pouvant être de degré un. Il s'agit d'un graphe planaire défini à partir d'un ensemble de n points aléatoires du carré [0,1[² (distribution par défaut). Ce graphe a un étirement de 2 par rapport à la distance euclidienne entre deux sommets du graphe. Ce graphe, introduit par Chew en 1986, est le même que le graphe "demi-theta_6", qui est un "theta-graph" utilisant 3 des 6 cônes. La dissymétrie qui peut apparaître entre le bord droit et gauche du dessin est lié au fait que chaque sommet n'a qu'une seule bissectrice de cône dirigée vers la droite, alors qu'il y en a deux obliques vers la gauche.

theta n k (= thetagone n 3 k 6/k)

Theta-graphe à k>0 secteurs réguliers défini à partir d'un ensemble de n points du carré [0,1[². Les sommets u et v sont adjacents si le projeté de v sur la bissectrice de son secteur est le sommet le plus proche de u. Ce graphe n'est pas planaire en général (sauf pour k<3), mais c'est un spanner du graphe complet euclidien si k≥6.

dtheta n k (= thetagone n 3 ⎣ k/2⎦ 6/k)

Demi-Theta-graphe à k≥2 secteurs réguliers défini à partir d'un ensemble de n points du carré [0,1[² (distribution par défaut). La définition est similaire au Theta-graphe excepté que seul 1 secteur sur 2 est considéré. Il faut k pair. Pour k=2, il s'agit d'un arbre, pour k=4, le graphe est de faible tree-width pas toujours connexe. Pour k=6, ce graphe coïncide avec le graphe td-delaunay.

       Ex: gengraph dtheta 500 6 -visu
           gengraph dtheta 500 4 -pos 0 -visu
           gengraph dtheta 500 2 -pos 0 -visu

yao n k (= thetagone n 0 k 2/k)

Graphe de Yao à k>0 secteurs réguliers défini à partir d'un ensemble de n points du carré [0,1[² (distribution par défaut). Les sommets u et v sont adjacents si v est le sommet le plus proche de u (selon la distance euclidienne) de son secteur. Ce graphe n'est pas planaire en général, mais c'est un spanner du graphe complet euclidien. Le résultat est valide seulement si k≥2. En fait, ce n'est pas tout à fait le graphe de Yao (voir thetagone).

percolation a b p (= udg a·b 1 -norm L1 -xy mesh a b -dele 1-p)

Grille de percolation à coordonnées entières (i,j) de [0,a[ × [0,b[ où p représente la probabilité d'existence de chaque arête. La différence avec le graphe "mesh a b -dele 1-p" est qu'ici le graphe est géométrique, donc dessiné selon une grille si l'option -visu est ajoutée.

hudg n r (= udg n r -norm hyper -xy hyper r)

Graphe géométrique aléatoire hyperbolique sur n points du disque unité. Deux sommets sont adjacents si leurs points sont à distance hyperbolique ≤ r. [A FINIR]

point n (= ring n . -pos 1)

Graphe géométrique composé de n points du plan mais sans aucune arête (voir "stable"). Ce graphe permet de visualiser la distribution des points, par défaut uniforme sur [0,1[², mais qui peut être modifiée avec l'option -xy.

       Ex: gengraph point 500 -xy seed 3 2.1 -visu
           gengraph point 1000 -xy seed 3 -0.1 -visu
           gengraph point 1000 -xy disk -visu

star-polygon n (= ring n 1 . -xy disk)

Polygone "star-shaped" aléatoire à n cotés contenu dans le disque unité (voir -xy ratio).

convex-polygon n (= ring n 1 . -xy convex)

Polygone convexe aléatoire à n cotés contenu dans le disque unité (voir -xy ratio). Voir aussi le graphe polygon n.

regular n d (= fdrg n d .)

Graphe d-régulier aléatoire à n sommets asymptotiquement uniforme. Il faut que nd soit pair. L'algorithme est de complexité O(nd²) et pour être asymptotiquement uniforme, il faut d=o(√n). On obtient nécessairement un matching si d=1, un stable si d=0, un cycle si d=2 et n<6.

cubic n (= fdrg n 3 .)

Graphe cubique aléatoire à n sommets asymptotiquement uniforme. Il faut que n soit pair.

plrg n t (= bdrg n_1 d_1 … n_k d_k .)

Power-Law Random Graph (ou scale-free graph). Graphe aléatoire à n sommets dont la distribution des degrés suit une loi en puissance d'exposant t>0 (typiquement un réel t∈]2,3[), la probabilité qu'un sommet soit de degré i>0 étant proportionnelle à 1/i^t. Plus précisément, la distribution est la suivante:

d_1=1, n_1=⎣ exp(𝛼)⎦ + n-s(𝛼)
d_i=i, n_i=⎣ exp(𝛼)/i^t⎦ pour 2≤i≤p(𝛼)

où a est un réel minimisant |n-s(𝛼)| avec p(𝛼)=⎣ exp(𝛼/t)⎦ et s(𝛼)=∑_{i=1}^{p(𝛼)} ⎣ exp(𝛼)/i^t⎦. Ce sont les mêmes graphes que ceux générés par Brady-Cowen'06 ou ceux étudiés par Lu'01.

syracuse n (= collatz n 1 0 3 1 .)

Graphe orienté issu du problème "3x+1" de Collatz. D'après la conjecture, il s'agit d'un graphe connexe. Les arcs sont définis par la relation x↦x/2 si x est pair, et x↦(3x+1)/2 sinon. La boule de volume n est générée depuis 1 si n>0 en itérant la relation inverse, et dans ce cas le graphe a précisément n sommets. Si n<0, la relation est itérée pour tous les entiers de [1,|n|] dans la limite de n² sommets.

       Ex: gengraph syracuse 18 -label 1 -visu 
           gengraph syracuse -18 -label 1 -visu

Le rayon de la boule de volume n (excluant les valeurs multiples de 3 qui n'ont toujours qu'un seul prédécesseur) est expérimentalement < ln(n)/ln(1.36) pour tout n<10^18 et conjecturée en ln(n)/ln(4/3). La hauteur maximum atteinte à partir d'un entier de [1,n] est expérimentalement < n², avec seulement 7 exceptions pour n<10^18 (et dans ces cas là, la hauteur est < 9n²). Pour n=27, on obtient une hauteur record de 4,616 ≃ 7n², le second record pour n<10^18. Selon les conjectures, les trajectoires de hauteur maximum pour n ont une forme générale qui consiste à une montée ≃ 8·ln(n) étapes pour atteindre le maximum, puis une descente ≃ 24·ln(n) étapes, et les trajectoires extrêmes ont ≃ 42·ln(n) étapes.

kakutami_3x+1 n (= collatz n 1 0 6 2 .)

Variante de syracuse "non-compressée" qui est définie par la relation x↦x/2 si x est pair et et x↦3x+1 sinon. Comme le graphe de Collatz, il est possible d'avoir n<0.

kakutami_5x+1 n (= collatz n 3 0 30 6 3 0 2 0 3 0 30 6 .)

Graphe orienté issu du problème "5x+1" de Kakutami (cf. syracuse) défini par la relation x↦x/2 si x est pair, x↦x/3 si x est divisible par 3 mais pas par 2, et x↦5x+1 sinon. D'après la conjecture de Kakutami, il s'agit d'un graphe connexe. On peut se ramener à un graphe de Collatz en considérant 2×3=6 paires de coefficients. Comme le graphe de Collatz, il est possible d'avoir n<0.

       Ex: gengraph kakutami_5x+1 91 -undirected -visu

kakutami_7x+1 n (= collatz n 15 0 210 30 15 0 10 0 … 210 30 .)

Graphe orienté issu du problème "7x+1" de Kakutami (cf. syracuse) défini par la relation x↦x/2 si x est pair, x↦x/3 si x est divisible par 3 mais pas par 2, x↦x/5 si x est divisible par 5 mais ni par 2 ni par 3, et x↦7x+1 sinon. D'après la conjecture de Kakutami, il s'agit d'un graphe connexe. On peut se ramener à un graphe de Collatz en considérant 2×3×5=30 paires de coefficients. Comme le graphe de Collatz, il est possible d'avoir n<0.

farkas n (= collatz n 6 0 6 6 6 0 4 0 6 0 … 18 6 .)

Graphe orienté issu de la relation introduite par Farkas en 2005 qui a prouvé qu'elle définissait un arbre de racine 1. Proche du problème "3x+1" elle est définie par x↦x/2 si x est pair, x↦x/3 si x est divisible par 3 mais pas par 2, (3x+1)/2 si x≡3 (mod 4) et (3x+1)/2 si x≡1 (mod 4). On peut se ramener à un graphe de Collatz en considérant 12 paires de coefficients. Comme le graphe de Collatz, il est possible d'avoir n<0.

       Ex: gengraph farkas -34 -label 1 -visu

HISTORIQUE

v1.2 octobre 2007:

            - première version

v1.3 octobre 2008:

            - options: -shift, -width
            - correction d'un bug pour les graphes de permutation
	    - accélération du test d'ajacence pour les arbres, de O(n) à O(1),
              grâce à la représentation implicite
	    - nouveau graphes: outerplanar, sat

v1.4 novembre 2008:

            - format de sortie: matrix, smatrix, list
            - nouveau graphe: kout
            - correction d'un bug dans l'option -width
	    - correction d'un bug dans la combinaison -format/shift/delv

v1.5 décembre 2008:

            - correction d'un bug dans tree lorsque n=1

v1.6 décembre 2009:

            - nouveaux graphes: rpartite, bipartite

v1.7 janvier 2010:

            - nouveaux graphes: icosa, dodeca, rdodeca, cubocta, geo,
	      wheel, cage, headwood, pappus, mcgee, levi, butterfly,
	      hexagon, whexagone, arytree, binary, ktree, tw, kpath,
	      pw, arboricity, wagner, mobius, tutte-coexter, paley
            - nouveau format de sortie: -format dot
	    - nouvelles options: -header, -h, -redirect, -dotpdf
            - correction d'un bug dans kout, et dans tree lorsque n=0
	    - tree devient un cas particulier d'arboricity.
	    - aide en ligne pour les paramètres des graphes.

v1.8 juillet 2010:

            - nouveaux graphes: chvatal, grotzsch, debruijn, kautz
	      gpstar, pstar, pancake, nauru, star, udg, gpetersen,
              mobius-kantor, desargues, durer, prism, franklin,
	      gabriel, thetagone, td-delaunay, yao, theta, dtheta
            - suppression du graphe geo (remplacé par udg)
            - nouvelles options: -pos, -norm, -label, -dotfilter
	    - nouvelle famille d'options: -xy file/noise/scale/seed
	    - définition plus compacte dodeca (non explicite)
	    - utilisation du générateur random() plutôt que rand().
	    - correction d'un bug dans "-format standard" qui provoquait une erreur.
	    - correction d'un bug dans kneser pour k=0, n=0 ou k>n/2.
	    - nouveaux formats: -format dot<type>, -format xy
	    - suppression de -dotpdf (qui est maintenant: -format dotpdf)
	    - labeling pour: gpetersen, gpstar, pstar, pancake, interval,
	      permutation

v1.9 août 2010:

            - renome -h en -list
	    - renome -xy file en -xy load
	    - centrage des positions sur le barycentre des graines (-xy seed)
	    - nouvelles options: -star, -visu, -xy round
	    - les graphes peuvent être stockés en mémoire, sous la forme d'une liste
	      d'adjacence grâce à l'option -check.
	    - généralisation de -delv p avec p<0
	    - nouveaux graphes: caterpillar, hajos, hanoi, sierpinski, sunlet, load
	    - labeling pour: hanoi, sierpinski
	    - aide sur toutes les options (nécessitant au moins un paramètre)
              et non plus seulement pour les graphes
	    - nouvelle famille d'options: -vcolor deg/degr/pal
	    - correction d'un bug pour l'aide dans le cas de commande
	      préfixe (ex: pal & paley)

v2.0 septembre 2010:

	    - nouvelles options: -vcolor degm/list/randg, -xy unique/permutation,
	      -check bfs, -algo iso/sub
	    - l'option -xy round p admet des valeurs négatives pour p.
	    - les options "load file" et "-xy load file" permettent la
              lecture à partir de l'entrée standard en mettant
              file="-", la lecture de famille de graphes, et supporte les commentaires.
	    - les formats list/matrix/smatrix utilisent un espace
	      linéaire O(n+m) contre O(n²) auparavant.
	    - les sommets sur le bord (graphes géométriques) ne sont plus coupés
	      (bounding-box (bb) plus grandes).
	    - nouveaux graphes: kpage, outerplanar n (=kpage n 1), rng, nng
	      fritsch, soifer, gray, hajos (qui avait été définit mais non
	      implémenté !), crown, moser, tietze, flower_snark, markstrom,
	      clebsch, robertson, kittell, rarytree, rbinary, poussin, errera
	    - les graphes de gabriel (et rng,nng) dépendent maintenant de -norm.
	    - "wheel n" a maintenant n+1 sommets, et non plus n.
	    - aide en ligne améliorée avec "?". Ex: gengraph tutte ? / -visu ?
	    - les options -help et ? permettent la recherche d'un mot clef.
	      Ex: gengraph -help planaire / ? arbre
	    - description plus compacte de tutte (et des graphes à partir d'un tableau)
	    - correction d'un bug pour rpartite (qui ne marchait pas)

v2.1 octobre 2010:

	    - nouvelles options:
	      -check degenerate/gcolor/edge/dfs/ps1/paths/paths2/iso/sub/minor/isub
	      -filter minor/sub/iso/vertex/edge/degenerate/ps1
	      -filter degmax/degmin/deg/gcolor/component/radius/girth/diameter
	      -filter cut-vertex/biconnected/isub/all/minor-inv/isub-inv/sub-inv
            - suppression de -algo iso/sub: l'option -algo est réservée à la mis
	      au point de -check
	    - extension de -label b à b=2 qui force l'affiche des noms
              sous forme d'entiers même avec -permute.
	    - correction d'un bug pour house (qui ne marchait pas)
	    - nouveau graphe: windmill

v2.2 novembre 2010:

            - gestion des graphes orientés: lecture d'un fichier de
              graphe (ou d'une famille avec arcs et arêtes)
	    - nouvelles options: -(un)directed, -(no)loop, -check twdeg/tw,
	      -filter tw/id/hyperbol/rename
	    - permet l'affichage de la "value" (p) dans l'option -filter
	    - nouveau graphe: aqua
	    - correction du graphe tutte-coexter et suppression du
              graphe levi (qui en fait était le graphe de tutte-coexter).
	    - généralisation de l'option "load" à load:id family

v2.3 décembre 2010:

            - nouvelles options: -check ps1bis/edge, -filter ps1bis/tw2
	      -filter minus/minus-id/unique/connected/bipartite/forest
	      -check ps1ter
	    - remplacement de atof()/atoi() par strtod()/strtol() qui
	      sont plus standards.
	    - remplacement de LONG_MAX par RAND_MAX (=2^31-1) dans les
              expressions faisant intervenir random() qui est de type
              long mais qui est toujours dans [0,2^31[, même si
              sizeof(long)>4. Il y avait un bug pour les architectures
              avec sizeof(long)=8.
	    - nouveau graphe: cylinder
	    - suppression de la variante "load:id" au profit de la
              forme plus générale "file:range" valable pour load, -filter, etc.

v2.4 janvier 2011:

            - correction d'un bug dans -filter minus-id
	    - correction d'un bug dans rpartite (incorrect à partir de r>5 parts)
	    - correction d'un bug dans whexagon (nb de sommets incorrects)
	    - nouvelles options: -check ps1x/girth, -filter ps1c/ps1x
	    - renomage: ps1bis -> ps1b, ps1ter -> ps1c
	    - nouveau graphe: mycielski
	    - la graphe grotzsch est maintenant défini à partir du graphe
	      mycielski (la définition précédante était fausse)
	    - bug détecté: td-delaunay 500 -check gcolor -format no -seed
              7 | grep '>6' qui donne jusqu'à 7 couleurs; le nb de
              couleurs affichées dans -check gcolor est erroné

v2.5 mars 2011:

	    - nouveaux graphes: line-graph, claw

v2.6 juin 2011:

	    - amélioration du test -filter ps1: détection de cliques et d'arbres

v2.7 octobre 2011:

	    - nouvelle option: -check bellman (pour les géométriques seulement)
	    - ajout des champs xpos,ypos à la structure "graph".
	    - nouveaux graphes: linial, linialc, cube, diamond, theta0,

v2.8 novembre 2011:

	    - nouveaux graphes: ggosset, gosset, rplg, wiener-araya, headwood4
	    - correction d'un bug pour "-xy seed k n" lorsque k=1.
	    - nouvelles options: -check maincc, -maincc (non documentée)

v2.9 février 2013:

	    - nouveau graphe: frucht, halin
	    - correction d'un bug pour "-check gcolor" qui ne
	      renvoyait pas le nombre correct de couleurs, et qui de
	      plus n'utilisait pas l'heuristique du degré minimum.
	    - correction d'un bug pour "permutation -label 1"

v3.0 octobre 2013:

	    - nouveaux graphes: rig, barbell, lollipop
	    - généralisation de l'option -filter forest
	    - nouvelles options: -apex, -filter isforest, -filter istree, -filter cycle
	    - correction d'un bug dans -filter vertex
	    - amélioration de l'aide lors d'erreurs de paramètre comme:
              "-filter F vertex" au lieu de "-filter F vertex n"
	    - amélioration de l'option -header

v3.1 décembre 2013:

	    - nouveaux graphes: bpancake
	    - légère modification des labels des sommets des graphes pancake, 
	      gpstar et pstar
	    - nouvelles options: -xy grid, -xy vsize
	    - modification de la taille des sommets pour dot permettant de tenir
	      compte de -xy scale.

v3.2 mai 2014:

            - amélioration du test ps1b (ajoût de règle et réduction
	      du nombre d'indéterminées dans graphes des conflits)

v3.3 juillet 2014:

            - modification importante du code pour -check ps1
            - modification des graphes linial et linialc
	    - nouvelles options: -check kcolor, -vcolor kcolor, -len, -check kcolorsat

v3.4 février 2015:

            - documentation et mise au point de l'option -maincc
	    - correction d'un bug lors de la combinaison de "load file" et de "-vcolor pal grad"
	    - correction d'un bug dans la fonction SortInt() qui affectait "-vcolor deg"
	    - correction d'un bug avec l'option -label 1 pour certains graphes (outerplanar ...)
            - création du script dot2gen.awk pour convertir le format dot en format standard
	    - nouvelles options: -fast, -caption
	    - introduction du groupement d'arêtes/arcs i-(j k ...) dans le format standard
	      (il reste un bug si ce format est lu depuis l'entrée standard)

v3.5 mars 2015:

	    - correction d'un bug pour le dégradé de couleurs avec "-vcolor pal grad"
	    - nouvelles options: -check ncc/connected, -check routing scenario [...] cluster
	    - nouvelle variante de graphe: loadc file
	    - nouveaux graphes: octahedron, turan, hexahedron, tetrahedron, deltohedron,
	      trapezohedron, antiprism, flip, associahedron, shuffle
	    - changement de nom (ajoût du suffixe "hedron") pour: isoca, dodeca, cubocta,
	      rdodeca

v3.6 juin 2015:

            - nouvelles options: -version, -variant, -check info, -xy mesh,
	      -check routing tzrplg, -check routing dcr
	    - nouveaux graphes: percolation, hgraph, cricket, moth, bull, expander
	    - correction de bug dans "-help ?", dans "-check girth" qui donnait -1 pour
	      un cycle de taille n, dans butterfly (mauvais nombre de paramètres)
	    - vérification que le nombre de sommets n'est pas négatif
	      pour plusieurs graphes dont tree, kout, etc. ce qui
	      pouvait provoquer des erreurs
	    - vérification du format d'entrée pour load/loadc
	    - l'option -check maincc n'affiche plus le graphe initial
	    - description du format des familles de graphes dans l'aide
	    - affiche plus de messages d'erreurs: lecture d'un graphe au mauvais
	      format, mauvaise combinaison de d'options, ...

v3.7 juillet 2015:

            - nouvelle implémentation des mots de Dyck, qui sont
              maintenant uniformes. En conséquence les graphes
              aléatoires tree, arboricity, rarytree, rbinary, outerplanar,
              kpage … sont générés de manière uniformes.
	    - nouveaux graphes: treep (et simplification de halin),
	      ygraph, ringarytree (et simplification de arytree,
	      binary, wheel), netgraph, egraph, rgraph (=fish),
	      généralisation de barbell, tadpole (=dragon), pan,
	      banner, paw, theta0 (redéfinition), fan, gem, chess,
	      knight, antelope, camel, giraffe, zebra, utility,
	      zamfirescu, hatzel, web, bdrg, fdrg, regular, cubic, plrg
	    - nouvelles options: -check radius, -check diameter
	    - correction d'un bug si combinaison d'options -check ncc -format list
	      (mauvaise gestion de la variable CHECK)
	    - introduction de caractères UTF8 mathématiques dans l'aide

v3.8 novembre 2015:

            - nouveaux graphes: ladder, matching, d-octahedron, johnson
	    - correction d'un bug pour le graphe kpage (introduit à v3.7)

v3.9 février 2016:

	    - renomage de l'option "-xy scale" en "-xy box"
	    - correction d'un bug dans rbinary (mauvais alias/définition)
	    - correction d'un bug (introduit à v3.6) dans la fonction
              max(double,double) au lieu de fmax() qui affectait certains
              graphes et options géométriques (rng, -xy grid, percolation, ...)
            - correction d'un bug concernant rarytree lorsque b>2
	    - correction d'un bug dans les statistiques pour -check routing
	    - généralisation du graphe rarytree (augmentation du degré de la racine)
	    - nouveaux graphes: herschel, goldner-harary, rbinaryz,
	      point, empty, apollonian, dyck, cross, tgraph, bidiakis, gear,
	      centipede, harborth, sunflower, planar, squaregraph, polygon
	    - modification de certains graphes (cage, ring, gabriel,
              nng, rng) afin que le test d'adjacence ne dépende plus de N
              mais de PARAM[0] par exemple
	    - introduction du format %SEED pour l'option -caption

v4.0 mars 2016:

	    - nouveaux graphes: pat, star-polygon, convex-polygon
	    - nouvelles options: -check kindepsat, -xy circle, -xy polar,
	      -xy unif, -xy convex, -xy ratio, -xy zero
	    - aide permettant les préfixes comme dans -check routing cluster

v4.1 avril 2016:

	    - nouvelles options: -xy convex2, -check routing hdlbr/bc
	    - nouveaux graphes: kstar, split, cactus, squashed
	    - suppression de -check paths2 qui donnait toujours comme -check paths
	    - option -check bellman apparaît dans l'aide

v4.2 mai 2016:

	    - nouvelles options: -check routing agmnt, -format vertex,
	      -check routing hash mix, -xy unif, -xy polygon
	    - amélioration de l'option -check info
	    - prise en compte de -xy ratio dans -xy unif et -xy seed
	    - affichage de l'écart type dans les stats affiché par -check routing
	    - affichage des erreurs sur stderr plutôt que stdout
	    - nouveau graphe: suzuki

v4.3 juin 2016:

	    - nouveaux graphes: triplex, jaws, starfish
	    - suppression d'un bug (Abort trap: 6) pour -format dot<type>
	    - modification de l'initialisation du générateur aléatoire qui pouvait
              faire comme -seed 0 sur certains systèmes où clock() est toujours nulle
	    - ajoût de variantes pour -check routing cluster
	    - nouvelles options: -xy cycle, -xy disk, -check stretch, -xy surface
	    - modification de l'option -norm (-norm 2 -> -norm L2, etc.)
	    - renomage de -xy polar en -xy disk

v4.4 juillet 2016:

	    - nouvelle option: -check simplify
	    - nouveaux graphes: schlafli, doily, fork (=tgraph)
	    - suppression d'un bug pour gosset (mauvais paramétrage)

v4.5 août 2016:

	    - modification du terminateur de séquence pour bdrg et fdrg: -1 devient '.'
	    - refonte du prototype des fonctions d'adjacence: adj(i,j) -> adj(Q)
	    - désactivation des options -apex, -star (et donc de caterpillar)
	    - finalisation de l'implémentation de fdrg (et donc de regular et cubic)
	    - redéfinition des graphes: netgraph, egraph, sunlet, cross, tgraph, ygraph
	    - nouveaux graphes: comb, alkane (et ses nombreuses variantes), banana
	      rlt, circle
	    - l'option -fast est effective pour fdrg et bdrg
	    - suppression d'un bug pour -xy mesh
	    - correction du graphe "interval" qui renvoyait en fait un "circle"
	    - génération d'une aide html à partir du source: gengraph.html
	    - nouvelle option: -norm poly p

v4.6 septembre 2016:

	    - nouvelle option: -check routing scenario until s
	    - nouveaux graphes: uno, unok, behrend

v4.7 janvier 2017:

	    - dans -check dfs/bfs, détection d'une source invalide
	    - dans -check dfs, calcule et affichage la hauteur des sommets
	    - ajoût d'un paramètre pour unok

v4.8 mars 2017:

	    - calcul dans -check stretch du stretch max. minimum
	    - correction d'un bug dans -xy convex qui pouvait produire des ensembles
	      non convexes et des points en dehors du cercle de rayon 1
	    - nouveaux graphes: ngon

v4.9 juin 2017:

	    - correction d'un bug pour l'option -xy box et amélioration
	      du dessin de la grille pour -xy grid
	    - généralisation de -check bellman aux graphes non valués
            - renomage des options: -dotfilter -> -dot filter,
	      -len -> -dot len, -filter hyperbol -> -filter hyper
	    - nouvelles options: -norm hyper, -xy hyper, -dot scale,
	      -label b pour b=3 et b<0, -check volm
	    - nouveaux graphes: hudg, hyperbolic

v5.0 août 2017:

	    - nouveaux graphes: helm, haar
	    - nouveau format html

v5.1 août 2018:

            - redéfinition (plus simple) du graphe de Turán
	    - redéfinition de bidiakis comme graphe cage
	    - redéfinition de centipede comme graphe comb (et sans -star)
	    - simplification de bellman avec optimisation pour
              utilisation multiples comme dans -check stretch
	    - amélioration de détails dans l'aide html (blocs "!!!" et "Ex:")
	    - changement des paramètres (maintenant avec un . final)
	      pour: grid, aqua, rpartite, cage, ring, ggosset
	    - orientation corrigée avec -directed pour les graphes (et
              leurs composés) utilisant une représentation implicite:
              kout, ktree, kpath, kpage, hyperbolic, cactus, planar,
              rarytree, apollonian, expander, polygon
            - orientation supportée pour cage et ring (possibilité de cordes<0)
            - nouveaux graphes: margulis, collatz, syracuse, mst, farkas,
	      kakutami_[3|5|7]x+1 (3 graphes), [w|u][psl|dis][d] (8 graphes)
            - redéfinition de l'option -loop avec suppression de -noloop
	    - inversion des lignes/colonnes dans uno et unok
	    - redéfinition du cuboctahedron à partir de linial
	    - aide sur le graphe chvatal qui était abscente
	    - format xy: affichage coordonnées entières si elles le sont
	    - bug corrigé pour -label b avec b<0: affiche exclusif centré ou pas
	    - bug corrigé pour -xy zero et -xy bord apparu à la v49
	    - définitions des graphes oubliés mobius-kantor et dragon
	    - utilisation d'une version uniforme pour remplacer random()%k
	    - nouvelle option: -dot scale auto

v5.2 juin 2019:

            - nouveaux graphes: dart, kite, domino, hourglass, antenna,
	      parachute, parapluie, klein
	    - nouvelles abréviations pour les graphes alkane et option
	      -label 1 activée par défaut, correction d'un bug pour le
	      graphe methane
	    - chargement conditionnel des scripts js dans le format html
	    - nouvelle option: -visuh, -check subdiv
	    - correction d'un bug pour unok, introduit à la version v5.1
	    - correction d'un bug pour -check stretch (Bellman-Ford
              avec appels multiples)
	    - correction d'un bug pour nb_edges() introduit à la
	      version v5.1 et qui affectait par exemple -check edges
	    - correction bug dans la détection de séquence graphique
	      qui pouvait affecter fdrg, regular et cubic

v5.3 janvier 2021:

            - nouveaux graphes: knng, rectree, odd, biggs, biggs-smith
	    - redéfinition de nng à partir de knng
	    - renommage de headwood et headwood4 en heawood et heawood
	    - nouvelle option: -check prune, -dot dir

v5.4 février 2023:

            - nouveaux graphes: tree_fibo, tree_part, tree_binom
	    - nouvelles options: -dot attr, -check ball
	    - génération rapide (-fast) pour tous les graphes basés
	      sur une k-orientation et unification pour ceux basés sur
	      load (soit au total +15 graphes)
	    - correction d'un bug pour arboricity n k, introduit à la
	      version v5.1, qui fixait k=1
	    - ajoût du synonyme -check span pour -check sub
	    - ajoût de l'aide pour -check isub