Mes débuts avec les graphes
Qu'est-ce qu'un graphe ?
C'est une structure mathématique servant à modéliser diverses situations.
Elle est constituée d'un ensemble d'éléments appelés sommets, et d'une relation entre ces éléments. Elle est représentée par une figure où les sommets sont représentés
par des points et la relation par des arcs liant ces points.
Un graphe peut être utilisé pour modéliser le plan de circulation d'une ville. Les sommets correspondent aux carrefours, les arcs aux rues, éventuellement en sens
unique, reliant ces carrefours. Le graphe est dit "fortement connexe" si on peut aller, par un chemin, de n'importe sommet à n'importe quel autre : ce qui est une
propriété indispensable pour la circulation urbaine, même si le chemin est long !
Mais les sommets peuvent aussi correspondre à des individus, et les arcs aux attractions exercés par les individus les uns sur les autres : nous voilà dans la
psychologie de groupe !
On appelle successeur d'un sommet x, un sommet y tel qu'il existe un arc (x,y) liant y à x. On appelle degré intérieur d'un sommet x le nombre de successeurs de x.
On a des définitions analogues pour prédécesseur d'un sommet et degré extérieur d'un sommet.
Si, pour deux sommets reliés, il y a deux arcs dans chaque sens, on l'indique par une ligne sans flèche et on parle d'"arêtes" plutôt que d'arcs. C'est le cas si
on veut modéliser un réseau routier : les sommets correspondent aux villes, les arêtes aux routes reliant ces villes. Si l'on s'intéresse aux arcs d'un graphe
avec la précision de l' "orientation", on dit que le graphe est orienté (en anglais : directed graph ou digraph). Si l'on s'intéresse seulement au fait que les
paires de sommets soient reliées ou non sans se préoccuper du sens, on dit que le graphe est non orienté (en anglais : graph). On considère alors les arêtes.
Ma thèse de troisième cycle (1964 - 1966) dirigée par Claude Picard a eu pour sujet l'utilisation de l'information locale dans un graphe orienté, par exemple
le degré des successeurs des sommets, pour la recherche de chemins de longueur maximale. J'expérimente alors mes idées grâce à des programmes informatiques écrits
en ALGOL. Je les fais tourner sur l'un des premiers ordinateurs existants : l'Eliott 803, installé dans l'embryon du futur Institut de programmation de Paris,
l'Institut Blaise Pascal, impasse du Maroc dans le 18ème. On utilise alors des bandelettes perforées dont on surveille le grignotage têtu avec attention. Parfois,
les résultats sont complètement inattendus, cela peut être du à la température trop élevée du local ! L'Eliott ne supporte pas le dépassement de 20°.
Un algorithme efficace de recherche de cycles hamiltoniens pour les graphes de Dirac et pour les graphes planaires triadiques est cité par Claude Picard au congrès
de Rome, 1966 (un graphe est dit "planaire" si on peut le représenter dans un plan, donc le dessiner sur une feuille de papier, de sorte que deux arêtes quelconques
ne se rencontrent pas ailleurs qu'aux extrémités. Il est triadique si toutes les plus petites "faces" sont des triangles.)
Je soutiens ma thèse en juin 1966
("Algorithmes d'orientation progressive des graphes", Faculté des Sciences de l'université de Paris ; jury : président René de Possel ; examinateurs : Claude-François Picard, Marcel-Paul Schützenberger): J'ai l'honneur d'"initier" le président à la théorie des graphes.
Graphes fccm
Après ma thèse de troisième cycle, je commence l'étude sur les circuits dans les graphes orientés. Un circuit est un chemin dont l'extrémité
terminale coïncide avec l'origine. Le point de départ de l'étude est le problème de la suppression des circuits par suppression d'un nombre minimal d'arcs,
proposé par Claude Picard. En particulier, à partir de 1968, je mets en évidence, et caractérise, les graphes fortement connexes c-minimaux (fccm), c'est-à-dire
graphes fortement connexes ayant un nombre minimal de circuits élémentaires. Mon premier Compte-rendu à l'Académie des Sciences paraît en mars 1968.
C'est une manière de protéger rapidement une découverte ; j'en suis très fier. Le résultat essentiel est le suivant : un graphe fortement connexe G a le minimum
de circuits si et seulement si il a un graphe partiel "arbre de circulation" H tel qu'en ajoutant à H un arc quelconque de G non dans H on obtienne un circuit.
(Graphe partiel de G : graphe G' qui a tous les sommets de G et tel que tout arc de G' est dans G ; arbre : graphe connexe sans cycle). De plus en inversant
tous les arcs de G qui ne sont pas dans H, on obtient un graphe sans circuit qui a le minimum de co-circuits. Pour obtenir ces résultats, j'utilise entre autres
les travaux de Paul Camion sur les modules unimodulaires et les généralise aux digraphoïdes de W.T.Tutte et G.J.Minty. Plus tard l'étude de ces graphes sera étendue
aux matroïdes orientés par Michel. Las Vergnas. Claude Berge propose mon article intitulé "Graphes fortement connexes c-minimaux et graphes sans-circuit
co-minimaux", au Journal of Combinatorial Theory, revue internationale, qui l'accepte. Il paraîtra en 1971 : 10(3) 237-244. Entre-temps j'ai trouvé une autre
caractérisation des graphes fccm, ce qui donne un nouveau "CRAS" :
Unicité de certains chemins dans des graphes fortement connexes, C.R.Acad.Sci.Paris Sér. A 272 (1971) 710-713.
qui peut se résumer ainsi : un graphe fortement connexe G est fccm si et seulement si, pour toute paire de sommets x et y, s'il existe plusieurs chemins x..y, alors
il n'existe qu'un seul chemin y..x. Je m'intéresse au cas particulier des tournois fccm (un tournoi est un graphe complet antisymétrique : chaque joueur rencontre
tous les autres une seule fois, (x,y) est un arc si x bat y) ; cette étude fait l'objet d'un article dans la Revue d'Automatique, Informatique et Recherche
Opérationnelle :
Sur certains tournois, RAIRO Oper.Res., 6ème année, R-1 (1972) 27-36.
Tous ces résultats sont publiés en français, ce qui est courant à l'époque, mais réduit la portée des découvertes. Ainsi, quelques années plus tard, des scientifiques
américains, avec Frank Harary, posent des questions relativement aux graphes, dont les réponses sont déjà dans mes travaux. Je dois revenir sur ceux-ci dans
l'article :
On signed digraphs with all cycles negative, Discrete Appl.Math. 20 (1988) 83-85.
Je rassemble mes résultats dans ma thèse d'état que je soutiens en 1971
"Cheminements remarquables dans les graphes : existence, obtention, conservation", Université Paris VI, jury : président : F.Ville ; examinateurs : Claude Berge, Claude-François Picard, Jean-Claude Simon. La thèse complémentaire porte sur "les traitements de liste".
Outre les travaux évoqués ci-dessus, ma thèse contient d'autres recherches et résultats, en particulier sur les graphes minimaux équivalents au sens des possibilités
de cheminement. Je reprendrai ces derniers plus tard dans :
On the minimal equivalent digraphs of digraphs with a tree structure, Scientia, A, 3 (1989), 15-22.
Certains résultats de ma thèse sont enseignés dans un DEA informatique de Paris VI. Elle donne lieu d'autre part à des résultats complémentaires, comme ceux de
François Sterboul.
Etude structurelle des graphes sans circuit et des graphes fortement connexes
Michel Chein, professeur, m'ayant contacté à propos d'un problème évoqué dans ma thèse, nous commençons en 1973 une étude structurelle des graphes sans circuit et
des graphes fortement connexes, en particulier : établissement des bases pour une étude systématique des invariants liés aux cheminements dans les graphes sans circuit
et algorithmes de partition des arcs, rapports entre l'approche de D.E.Knuth et celle de R.D.Luce pour les graphes fortement connexes, caractérisation des 2-arêtes
connexes minimaux. Ces études et celles qui suivent viennent de problèmes pratiques tels que la distribution du courrier postal, la vulnérabilité d'un réseau
électrique, l'allocation des registres dans un ordinateur. Ils conduisent à explorer un graphe d'une manière optimale ou à tester toutes sortes de connectivités
d'un graphe (qualités des liaisons entre les sommets): combien peut-on supprimer de sommets ou d'arcs d'un graphe sans nuire à ses propriétés de cheminement ?
ou bien encore à définir un ordre optimal dans le graphe. Le mathématicien s'éloigne allègrement de ces applications pratiques et sa curiosité s'aventure
joyeusement dans des spéculations abstraites où il tente de répondre aux questions qu'il s'est lui-même posées. Les résultats figurent en particulier dans les
articles suivants dont les auteurs sont Michel Chein et moi-même :
Bases de chemins et indices de recouvrement dans les graphes sans circuit, C.R.Acad.Sci.Paris Sér. A 276 (1973) 1489-1491
Invariants liés aux chemins dans les graphes sans circuit, Proceed. Colloq. Inter.Theory Comb. Roma 1973, Atti dei conveigni Lincei 17, tomo 1, (1976), 287-308
A note on top-down and bottom-up analysis of strongly connected digraphs, Discrete Math.16 (1976) 309-311
Path number of k-graphs and symmetric digraphs, Proceed. 7th Southeastern Conf.on Comb.,Graph th. and Comp., Bâton-Rouge 1976, Congr.Numer. 17 (1976)
Utilitas Math.Pub.Inc.,Winnipeg, 203-216
Minimally two-edge connected graphs, Journal of Graph Theory 3 (1979) 15-22
Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Math. 16 (1979), 183-187.
Avec d'autres chercheurs : Olivier Cogis, Michel Habib, Pierre Martin, Gabriel Petolla, nous étudions des problèmes d'ordonnancement en informatique (sauts, allocation
optimale de registres, couplages particuliers) :
Some results about the number of jumps in acircuit digraphs, Proceed. 5th Southeastern Conf.on Comb.,Graph th. and Comp., Florida Atl. Univer. 1974,
Congr.Numer. 10 (1974) Utilitas Math.Pub.Inc.,Winnipeg, 267-279
Register allocation invariants in dags, Proceed. 6th Southeastern Conf. on Comb.,Graph th. and Comp., Florida Atl. Univer.1975, Congr.Numer. 14 (1975)
Utilitas Math.Pub.Inc.,Winnipeg, 133-145
Atomes dans les graphes orientés
Lors d'un enseignement en DEA, j'oriente mes recherches sur la k-connexité et la k-arc connexité, en étudiant en particulier les travaux de Mader (
je dirige les travaux de Dalmazzo : nombre de branches suppressibles dans les graphes fortement connexes minimaux, nombre maximal d'arcs des graphes k-arc
fortement connexes minimaux; et de Rix : recherche d'un graphe partiel t-minimal) ; puis sur la criticalité et minimalité : passage du cas non orienté au
cas orienté. Cette dernière étude me conduit à publier :
On critically and minimally k-vertex (arc) strongly connected digraphs, Proceed. 5th Hungarian Colloq. on Comb., Keszthely, june 1976, 193-204
J'y introduis la notion d'atomes pour les graphes orientés étendant ainsi celle de Watkins pour les graphes non orientés. L'étude des propriétés des atomes sera
poursuivie par Y.O. Hamidoune (Thèse de doctorat d'état, "Contribution à l'étude de la connectivité d'un graphe", 3 juin 1980), et utilisée encore en 1996 dans
Meng Jixiang, Connectivities of minimal Cayley coset digraphs, Appl.math.-JCU, 11B (1996), 497-500
Diagnostique de Paraphrase
Lors de mon congé (1988-1989) pour recherche et conversion thématique sur le projet : "traitement du langage naturel, représentation des connaissances et réseaux sémantiques",
je participe au groupe "Diagnostic de Paraphrase" avec Daniel Kayser, Nelly Darcel, Bernard Levrat du LIPN, en liaison avec Catherine Fuchs, professeur de
linguistique à l'Université de Caen. L'opération de recherche consiste à mettre en évidence des transformations élémentaires conditionnées par des restrictions
sur le contexte ou sur les choix possibles parmi les significations potentielles d'un mot donné. Nous publions :
An account of Paraphrase using Elementary Transformations,E.C.A.I.-90, Stockholm, août 1990
Graphes conceptuels
Je reviens aux graphes en participant au projet "Graphes Conceptuels" (1991-1996). Les différentes réalisations utilisant les graphes conceptuels permettent
de considérer ceux-ci comme un outil de modélisation et un langage de spécification pour les bases de données, ou encore un langage de représentation de
connaissances permettant de construire des systèmes à bases de connaissances, ou enfin un modèle bien adapté au traitement informatique de la langue naturelle.
Ce projet a entrepris en particulier de faire la synthèse des travaux actuels et la comparaison avec d'autres modèles comme les réseaux sémantiques,
afin d'obtenir une extension du modèle de base. Brigitte Biebow et moi-même publions :
A comparison between conceptual graphs and KL-ONE, ICCS 93, Lecture Notes in Artificial Intelligence, 699, Springer Verlag 1993, 75-89(6*)
Noyaux d'un graphe
Autre utilisation des graphes en Intelligence Artificielle. La logique des défauts joue un rôle dans la représentation des connaissances. Je mets en évidence avec
François Lévy une modélisation d'un aspect de cette logique par le noyau d'un graphe :
Default logic and kernel in digraphs, rapport du LIPN, Université Paris-Nord, décembre 1991.
Poursuivant une recherche sur les noyaux, une collaboration avec Jayme L. Szwarcfiter de l'Université Fédérale de Rio de Janeiro conduit à l'article :
J. L. Szwarcfiter, G. Chaty, Enumerating the kernels of a directed graph with no odd circuits, Information Processing letters, Vol.51, n°3, Août 1994
cité dans : Y.Kikouchi, Y.Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, Information Processing letters,
Vol.86, n°2, April 2003
C. Banderier, J-M Le Bars, V. Ravelomanana, Generating functions for kernels of digraphs, Formal Power Series and Algebraic Combinatorics, Vancouver 2004