Générateur de graphes - v4.8 - © Cyril Gavoille - Mars 2017

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 (en 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 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 -dotfilter circo -visu
	  gengraph dyck -dotfilter circo -visu
	  gengraph ringarytree 4 2 3 0 -label 1 -visu
	  gengraph arboricity 100 2 -vcolor degr -visu
	  gengraph prime 6 -directed -noloop -visu
	  gengraph aqua 3 3 2 1 -label 1 -dotfilter 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 en texte simple. 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 + 1, et s'il y a i-j (ou i->j), alors il existe une arête (ou un arc) entre les sommets i et j.

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).

       Ex1: 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.

       Ex2: 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:

       Ex2:       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.

       Ex3: [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, certains graphes d'intersections ou les graphes géométriques, 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. Ces trois derniers formats sont donc à éviter. 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 installées: sed, grep, awk, more, sort, dot.

OPTIONS

-help [word], ? [word], or [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 qui sont possibles d'être générée. 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 arêtes. Les boucles peuvent être testées ou pas grâce aux options -loop et -noloop. 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 en effet que i<j. La plupart des graphes vont apparaître comme orientés symétriques.

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

-noloop
-loop

L'option -noloop permet de ne pas produire les boucles des graphes, alors que -loop les autorise. L'option -noloop est celle par défaut pour les graphes non-orientés, et l'option -loop celle par défaut pour les graphes orientés. Ces options doivent être placées après -(un)directed car modifiée par celle-ci.

-not

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

-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. Le sommet et ses arêtes incidentes sont alors supprimés. Si p est un entier <0, alors exactement |p| sommets sont supprimés. 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 adj(i,j) est appliquée sur les noms (i,j) originaux.

-star n [N'EST PLUS EFFECTIF DEPUIS v4.5]

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 opération est appliquée en priorité et ne peut être appliquée qu'une fois par commande. Les options -star et -apex sont incompatibles.

-apex n [N'EST PLUS EFFECTIF DEPUIS v4.5]

Ajoute n sommets universels, donc connectés à tous les sommets du graphe. Cette opération est appliquée en priorité. Les options -star et -apex sont incompatibles.

-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.

-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 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. 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'affiche 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 le graphe "load". Le résultat est une génération du graphe en temps O(n+m) au lieu de O(n²). L'utilisation typique est (voir aussi "loadc"):

       Ex: gengraph load file -fast -delv 0.3 -check ncc
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 (pour l'instant seul le graphe "load" le supporte). Certaines options, comme -not, n'ont alors 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>0 pour contrôler certaines fonctionnalités du générateur. Par exemple, "-variant 1 -check routing cluster -1" permettra de calculer une variante du schéma de routage "cluster".

-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.

-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 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.

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 distance 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. Le graphe doit être géométrique, si bien que le poids de chaque arête correspond à la distance euclidienne entre ses extrémités. L'étirement maximum depuis s est calculé, ainsi qu'un chemin le réalisant.

-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 dfs s

Effectue un parcours en profondeur d'abord de toutes les composantes connexes du graphe généré depuis le sommet s. Le nombre de composantes ainsi que l'arborescence (-1 indique que le sommet n'a pas de père) sont donnés.

-check ncc
-check connected

Donne le nombre de composantes connexes ainsi que le nombre de cut-vertex du graphe. Ces informations sont aussi affichées par -check dfs 0.

-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 hauteur du plus 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 multivalué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 pour le graphe du problème ensemble indépendant de taille k. Les variables i=1 à n sont les variables indiquant si le 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. 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.

Tester l'isomorphisme entre deux cycles de 8 sommets étiquetés aléatoirement prends 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.

-check sub H

Teste si le graphe généré G est un sous-graphe couvrant de H (donc avec le même nombre de sommets). 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 prennant 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 minor H

Teste si le graphe G généré contient H comme mineur. 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.

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ée. 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 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 (s) de routage 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é 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 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. A 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é contenant 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 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ée 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

       Ex1: -filter F vertex '5,7-13,>100'
       Ex2: -filter F vertex '5-10,p'
       Ex3: -filter F edge p
       Ex4: -filter F id 5,7
       Ex5: -filter F vertex p | head -1
L'exemple 1 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).

Pour avoir le maximum/minimum de "value" faire: … -filter … p | grep '^\[' | sort -rnk 3 | head … -filter … p | grep '^\[' | sort -nk 3 | head

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 hyperbol 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 converti au format <type>. - 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 ou dot. Les formats <type> pour dot les plus utilisés 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 -dotfilter. L'affichage des noms de sommets est contrôlé par l'option -label.

Remarque: 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). Ce facteur permet de garder une taille raisonable 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. 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 est combinable avec -vcolor.

-visu

Crée un fichier "g.pdf" permettant de visualiser le graphe. Il s'agit d'un raccourci de l'option "-format dotpdf" qui rajoute également la redirection "> g.pdf" 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.

-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 certain cas de mieux visualiser le graphe. C'est parfois nécessaire pour éviter l'intersection des sommets lorsqu'on utilise -label 1.

-dotfilter filter

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.

-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. 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. Par défaut les noms sont 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[. Comme cette option influence l'option -format dot<type>, l'option -label devant être placée avant -format. L'option -label 1 annule l'option -permute, mais -label 2 ne le fait pas. Attention ! l'option avec b>0 n'a pas d'effet pour les graphes géométriques où les sommets sont des points. Avec une combinaison -pos 0 -label 1 -visu, on peut cependant visualiser les noms de sommets sur un dessin du graphe, dessin qui ne respectera pas les coordonnées des sommets (voir exemple ci-dessous).

       Ex: gengraph petersen -label 1 -width 1
           gengraph petersen -label 1 -format dot | grep label
           gengraph petersen -label 1 -len 2 -visu
           gengraph gabriel 30 -pos 0 - label 1 -visu

-norm ℓ [parameters]

Fixe la norme pour l'adjacence de certains graphes géométriques (udg, gabriel, rng, nng, …). Les valeurs possibles pour ℓ sont L1, L2, Lmax, Lmin, poly p. La norme polygonale de paramètre p d'un vecteur (x,y) ("-norm poly p") est le rayon du cercle inscrit du polygone régulier convexe à p cotés contenant (x,y), le polygone étant orienté de façon à avoir son coté le plus à droit vertical. Ainsi "poly 4" correspond à la norme Lmax. Attention ! la norme "poly p" n'est pas toujours symétrique, lorsque p est impair par exemple. La norme par défaut est L2, la norme Euclidienne.

-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[ × [0,1[, mais cela peut être changé par l'option -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").

-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 redimensionement 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[ × [0,1[. Cette opération est effectuée juste avant la génération des arêtes, en particulier après avoir effectué l'opération -xy noise (voir ci-après) et/ou -xy load. Les positions sont recadrées pour laisser une fine bande vide sur le bord du rectangle. Cette bande a une largeur ≃ a/√n et une hauteur ≃ b/√n où n est le nombre de points.

-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 ligne (et de colonne) de la grille générée doit être au moins 2.

-xy zero

Ajoute l'origine (0,0) au dessin qui est marquée comme 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[ × [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[ × [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).

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[ × [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 de centre (0,0) et de rayon 1 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 ne sont pas 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 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[ × [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[ × [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. Pour la distribution par défaut (-xy unif) par exemple, les points seront aléatoires uniformes dans le rectangle [0,1[ × [0,r[. Si la forme est un cercle (-xy circle), 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-orientié 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 de 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 k 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 1 -10" donnera un cycle à 10 sommets.

ring n k c_k … c_k

Anneaux de cordes à n sommets chacun ayant k cordes de longueur c_1,…,c_k.

cage n k c_1 … c_k

Graphe cubique pouvant servir à la construction de graphes n-cage, c'est-à-dire aux plus petits graphes cubique à 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 sommets. Le i-ème sommet de chaque intervalle, disons le sommet numéro j du cycle, est adjacent au sommet numéro j+c_i du cycle (modulo n). Les valeurs c_i peuvent être positives ou négatives. Cette fonction permet aussi de construire des graphes avec des sommets de degré 4 comme "cage 8 2 0 2" (voir aussi le graphe de Chvátal) ou avec des sommets de degré 2 comme "cage 4 2 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.

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.

ringarytree h k r p

Arbre de hauteur h où chaque noeud interne à exactement k fils, le degré de la racine étant de degré r. Lorsque p>0, un chemin (si p=1) ou un cycle (si p=2) est ajouté entre les sommets de même niveau. Notez que "arytree h 1 r 0" génère une étoile de degré r où chaque branche est de longueur h. Le nom des sommets correspond 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.

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.

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.

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").

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.

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".

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 à n-2 noeuds internes. La numérotation des sommets n'est pas cyclique le long du polygone. Ce graphe n'est pas un graphe géométrique contrairement à sa variante convex-polygon.

       Ex: gengraph polygon 20 -dotfilter circo -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'une 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.

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.

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 connue. Il est connue 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 connue que si l'on parcoure 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).

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,2) 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 k a_1 … a_k

Graphe k-parti complet K_{a_1,…,a_k}. Ce graphe possède n=a_1+…+a_k sommets. Les sommets sont partitionnés en k parts comme suit: part 1 = [0,a_1[, part 2 = [a_1,a_1+a_2[, … part k = [a_1+…+a_{k-1},n[. Les sommets i et j sont adjacents ssi i et j appartiennent à des parts différentes.

ggosset p k d_1 v_1 … d_1 v_k

Graphe de Gosset généralisé. Les sommets sont tous les vecteurs entiers de dimension d = d_1 + … + d_k dont les coordonnées comprennent, pour i=1…k, exactement d_i fois la valeur v_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: 1 2 2 -1 2 0 ou encore 8 2 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 à 2n sommets où le i-ème sommet de la première partie 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.

centipede n

Arbre à 2n sommets et n feuilles en forme de peigne.

fan p q

Graphe 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 à 2n-3 noeuds qui sont codés par les mots de Dyck de longueur 2n-4 (que l'on peut afficher avec -label 1). Le nombre de sommets est donc C(n-2) nombre de Catalan d'ordre n-2. 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.

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 k>0. Le graphe est connexe, et pour k=1, il s'agit d'un arbre.

expander n k

Graphe à n sommets composé de k>0 cycles Hamiltoniens aléatoires. Le degré des sommets varie entre 2 et 2k. Il possède le cycle 0,1,…,n-1,0 comme cycle Hamiltonien, et a la propriété d'expansion à partir de k>3. Plus précisément, avec grande probabilité, les valeurs propres de la matrice d'adjacence du graphe sont ≤ 2√(2k).

comb n

Arbre de 2n sommets en forme de peigne, composé d'un chemin à n sommets avec un sommet pendant à chacun d'eux.

sunlet n

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

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 valeurs 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. Le type "normal" peut être abrégé en "n". L'option "-label 1 -visu" permet de distinguer les atomes C et H.

t topologie n t topologie n C─┐ normal C─ ⋯ ─C n≥1 neo 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 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 n 1) ethane ............. (= alkane n 2) propane ............ (= alkane n 3) butane ............. (= alkane n 4) pentane ............ (= alkane n 5) hexane ............. (= alkane n 6) heptane ............ (= alkane n 7) octane ............. (= alkane n 8) nonane ............. (= alkane n 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.

cuboctahedron

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 rhombicdodé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 cuboctahèdron.

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 de 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 à l'un des sommets commun aux deux triangles.

bull

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

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.

bidiakis

Graphe ou cube de Bidiakis. C'est un graphe planaire cubic à 12 sommets. 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. Il est Hamiltonien et son nombre chromatique est 3.

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 cubic 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 cubic 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 cubic 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.

headwood4

Graphe de Headwood 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.

line-graph n k

Line-graphe 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 [1,k]. Deux sommets sont alors adjacents ssi ils possèdent la même couleur. Ces graphes sont claw-free (sans K_{1,3} induit). Comme les graphes claw-free, les line-graphes connexes avec un nombre pair de sommets possèdent toujours un couplage parfait. On rappel qu'un graphe G est le line-graphe 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. Pour parle parfois de graphe adjoint.

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. 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[. 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. 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 m(m-1)…(m-t+1). Certaines propriétés se déduisent du graphe linialc n t.

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, m≤n. L'adjacence est identique, mais les sommets sont les (2t+1)-uplets (x_1,…,x_{2t+1}) 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 2t+1 m) et donc de De Bruijn (debruijn 2t+1 m). Le nombre de sommets est m(m-1)^{2t} et son degré maximum est 2(m-1). La taille de la clique maximum est 3 si m>2 et t>1. Le nombre chromatique de ce graphe 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.

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 classique est obtenu avec b=3. Il est planaire avec b^n sommets et est 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. A 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>0 branches connectées par une feuille à un unique sommet.

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.

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'est pas 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 (graphe "wheel 2n") et de n sommets chacun connecté deux sommets voisins du bord de la roue. Il est construit à partir du graphe "cage 2n 2 2 0" auquel on ajoute un sommet central.

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 ou w, x_1-…-x_n induit un chemin; et 2) 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).

udg n r

Graphe géométrique aléatoire (random geometric graph) sur n points du carré [0,1[ × [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[ × [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[ × [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.

nng n

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[ × [0,1[. 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).

thetagone n p k w

Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[ × [0,1[. 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

uno n p q

Line-graphe 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 d'entiers aléatoires de [0,p[ × [0,q[, pas nécessairement distinctes. Les sommets (x,y) et (x',y') sont adjacents ssi x=x' ou y=y'. 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 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.

unok n p q kp kq

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 kp sommets par ligne et kq par colonne. Il faut n≤min{p*kp,q*kq} et p, q, kp, kq>0. Si kp<0, alors on fait comme si kp=p, de même pour kq=q s kq<0. Contrairement à uno, deux sommets ont toujours des coordonnées distinctes. Le graphe résultant est de degré au plus kp+kq-2, et est de path-width (et aussi de tree-width) au plus celle du produit de clique K_{kp} × K_{kq} soit environ kp*kq/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 seulement O(n+p+q), dans les cas peu dense par exemple. Si kp ou kq=1, le graphe est une union de cliques, et si kp=kq=2 et n=2p=2q, c'est une union de cycles.

       Ex: gengraph unok 200 100 100 3 2 -visu

ngon p c x

Triangulation d'un polygone régulier. Plusieurs types de triangulations sont produites suivant la valeur des paramètres. 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 pk 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 à n sommets où les degrés des sommets suivent une loi de puissance d'exposant t. L'espérance du degré du sommet i=0…n-1 est w_i=(n/(i+1))^(1/(t-1)). Il s'agit d'une distribution particulière d'un Fixed Degree Random Graph où la probabilité d'avoir l'arête i-j est min{w_i*w_j/S,1} avec S=∑_k w_k. En général il faut prendre le paramètre t comme un réel de ]2,3[, 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-cubic 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 assymptotiquement 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 cubic aléatoire asymptotiquement uniforme, à condition que n soit pair. 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₂.

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 n 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.

       Ex: gengraph aqua 3 3 2 1 -label 1 -dotfilter dot -visu

GRAPHES COMPOSÉS :

mesh p q (= grid 2 p q)

Grille 2D de p x q sommets.

hypercube d (= grid d 2 … 2)

Hypercube de dimension d.

path n (= grid 1 n)

Chemin à n sommets.

cycle n (= ring n 1 1)

Cycle à n sommets.

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

Tore à p x q sommets.

stable n (= ring n 0)
empty n (= ring n 0)

Stable à n sommets.

clique n (= -not ring n 0)

Graphe complet à n sommets.

bipartite p q (= rpartite 2 p q)

Graphe biparti complet K_{p,q}.

utility (= rpartite 2 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é).

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 0)

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

hexahedron (= cube)

Hexaèdre: cube composé de 6 faces carrées.

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 line-graphe de K_n. En fait, tout sous-graphe induit de J(n,2) est un line-graphe. J(4,2) est l'octaèdre, J(5,2) le complément du graphe de Petersen.

turan n r (= rpartite r ⎣ n/r⎦ … ⎣ n/r⎦)

Graphe de Turán à n sommets. Il s'agit qu'un graphe r-parti complet de n sommets avec (n mod r) parts de ⎡ n/r⎤ sommets et r-(n mod r) parts de ⎣ n/r⎦ sommets. Il faut n≥r>0. Il est régulier lorsque r divise n. Il possède ⎣ (1-1/r)n^2⎦ arêtes. C'est le graphe sans clique de taille r+1 ayant le plus grand nombre d'arêtes. Lorsque n=2r, il s'agit du "cocktail party graph". Lorsque n=6 et r=3, c'est l'octaèdre.

claw (= rpartite 2 1 3)

Graphe biparti complet K_{1,3}.

star n (= rpartite 2 1 n)

Arbre (étoile) à n feuilles et de profondeur 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 1 n-r -star r, r=random()%n)

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.

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".

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.

random n p (= -not ring n 0 -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 me générer en utilisant "fdrg 3 3 3 1 .".

sunflower n (= cage 2n 2 2 0)

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. C'est le graphe de Hajós pour n=3.

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 à 5 sommets dont trois feuilles en forme de T.

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 line-graphe 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 2)

Graphe de Möbius-Kantor. Graphe cubique à 16 sommets de genre 1. Il est Hamiltonien, de diamètre 4 et de maille 6.

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).

headwood (= cage 14 2 5 -5)

Graphe de Headwood. C'est un graphe cubique à 14 sommets, de maille 6 et de diamètre 3. C'est le plus petit graphe dont le nombre de croisements (crossing number) est 3.

franklin (= cage 12 2 5 -5)

Graphe de Franklin. C'est un graphe cubique à 12 sommets, de maille 4 et de diamètre 3.

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

Graphe de Dyck. C'est un graphe cubique 3-connexe biparti à 32 sommets. C'est le seul graphe cubic à 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 6 5 7 -7 7 -7 5)

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

mcgee (= cage 24 3 12 7 -7)

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

tutte-coexter (= cage 30 6 -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) (d impair) ou 2*S(d,k) (d pair) avec S(d,k)=∑_{i=0}^(k-1) (d-1)^i.

gray (= cage 54 6 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 3x3x3 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.

grotzsch (= mycielski 4)

Graphe de Grötzsch. C'est le plus petit graphe sans triangle de nombre chromatique 4. 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 2 0".

house (= -not grid 1 5)

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

wagner (= ring 8 2 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 2 1 n/2)

Échelle de Möbius, graphe cubic à 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. Lorsque n≥5, le graphe n'est plus planaire, et pour n=8, il s'agit du graphe de Wagner.

ladder n (= grid 2 2 n)

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

cube (= crown 4)

Hypercube de dimension 3, graphe planaire cubic à 8 sommets où toutes les faces sont des rectangles.

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 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+1 sommets, graphe planaire 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 profondeur 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, le degré de 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.

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.

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 à 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.

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

Triangulation de Delaunay utilisant la distance triangulaire (TD=Triangular Distance). Il s'agit d'un graphe planaire défini à partir d'un ensemble de n points aléatoires du carré [0,1[ × [0,1[. 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'un seul axe dirigé vers la droite, alors qu'il y en a deux 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[ × [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[ × [0,1[. 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[ × [0,1[. 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.

point n (= ring n 0 -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[ × [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 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 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 cubic 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. Graphe aléatoire à n sommets dont la distribution des degrés suit une loi en puissance d'exposant t>0, 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 dans par Lu'01.

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 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 SortInit() 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, 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