UniversitySurf.net
Votre portail e-Learning
CultureMATH
ENSup. et Minist. EN
Séminaire MaMuX
Mathématiques, musique et relations avec d'autres disciplines

# Graphes - Graphs

## GROUPES - GROUPS

<http://www.info.univ-angers.fr/pub/gh/mmm/wreparb/rep_txt.htm>

## PAGES WEB

Jean-Paul Davalan.
A toolkit for graph editors and graph algorithms
<http://www.fmi.uni-passau.de/Graphlet/>
Programming the Graphlet graph editor
<http://www.fmi.uni-passau.de/Graphlet/graphscript/index.html>
AGD is based on LEDA, so you may need to download LEDA as well
Hamiltonian cycle and path problems, their generalizations and variations.
by Joseph Culberson.
<http://web.cs.ualberta.ca/~joe/Coloring/index.html>
Here are the archives for the book "Graph Coloring Problems" by Tommy R. Jensen and Bjarne Toft (Wiley Interscience 1995), dedicated to Paul ErdÃ¶s.
ABACUS is a software system which provides a framework for the implementation of branch-and-bound algorithms using linear programming relaxations that can be complemented with the dynamic generation of cutting planes or columns (branch-and-cut, branch-and-price, branch-and-cut-and-price).
<http://www.informatik.uni-koeln.de/ls_juenger/projects/abacus.html>
Hamiltonian cycle and path problems, their generalizations and variations.
Jonathan Gross Jay Yellen
<http://www.graphtheory.com/>
MathÃ©matiques pour l'Informatique, algorithmique, combinatoire, automates, langages formels, grammaires de graphes.
<http://dept-info.labri.u-bordeaux.fr/HBib/Graphe.html> <http://www.keck.caam.rice.edu/tsp/> <http://www.stetson.edu/~efriedma/mathmagic/1000.html>
What is the least number of crossings a straight-edge drawing of the complete graph on top of a set of n points in the plane obtains?
<http://dist.ist.tugraz.at/cape5/>

<http://theory.lcs.mit.edu/~karger/> <http://www.cs.elte.hu/~frank/> <http://seclab.cs.ucdavis.edu/~hoagland/>
Open questions
<http://www.cs.uwa.edu.au/~gordon/> <http://www.maths.man.ac.uk/~cwalkden/> <http://www.cs.concordia.ca/~chvatal/>
Ramsey Numbers, Regular Graphs of Given Degree and Girth, Large Regular Graphs of Given Degree and Diameter, Graphs Drawings, Combinatorial Geometry, Asymmetric Covering Codes,
<http://isu.indstate.edu/ge/>
<http://rw4.cs.uni-sb.de/~sander/html/>

## EXERCICES - EXERCISES

Wlodek Bryc and Stephan Pelikan
<http://math.uc.edu/onex/compare.html>

## ALGORITHMES

This is a continuously updated catalog of approximability results for NP optimization problems. The compendium is also a part of the book Complexity and Approximation.
Algorithms  for Combinatorial Enumeration Problems
Yasuko Matsui
<http://dmawww.epfl.ch/roso.mosaic/kf/enum/comb/combenum.html>
par Didier MÃ¼ller LycÃ©e cantonal de Porrentruy
<http://www.apprendre-en-ligne.net/graphes/>

## PROBLÈMES - PROBLEMS

<http://www.vuse.vanderbilt.edu/~spin/open.html>
by Tommy R. Jensen and Bjarne Toft

## DEMOS

Recherche du plus court chemin. Algorithme de Dijkstra.
ComplÃ©ter ou modifier P0, M et k.
L'exemple est identique Ã  celui des Graphes probabilistes Les donnÃ©es sont celles de l'activitÃ© 12 p. 278 du livre. Tous les calculs peuvent Ãªtre effectuÃ©s hors connexion, les calculs sont effectuÃ©s par le navigateur qui interprÃ¨te le programme Ã©crit en javascript et contenu dans la page.
Peut aussi servir Ã  calculer un puissance quelconque de n'importe quelle matrice carrÃ©e.
Entrer le graphe en s'inspirant de l'exemple.

## EXEMPLES - EXAMPLES

DOT and DOTTY are graph layout products from AT&T Bell Labs. DOT is a Unix filter that takes a DOT language file specifying the objects in a directed graph and output a optimal (in some sense) layout of the objects in one of a number of formats including Postscript and Maker Interchange Format (MIF).
Form Interface for DOT This service is only intended for demonstration purposes.
<http://seclab.cs.ucdavis.edu/~hoagland/Dot.html>
Michel Couprie, Gilles Bertrand programmes C pour manipuler des graphes,
<http://www.esiee.fr/%7Ecoupriem/Graphestp3/graphestp3.html> <http://www.di.ens.fr/~granboul/enseignement/mmfai/algo2001-2002/tp7/>
Exemple de fichier PostScript, tableau, graphe et diagramme de GANTT

## DICTIONNAIRES GLOSSAIRES - DICTIONARIES

<http://www-math.cudenver.edu/~wcherowi/courses/m4408/glossary.htm>

## LOGICIELS - SOFTWARES

<http://130.179.24.217/G&G/G&G.html>
A highly portable collection of programs and data is now available to researchers who study combinatorial algorithms and data structures.
The programs are intended to be interesting in themselves as examples of literate programming.
<ftp://labrea.stanford.edu/pub/sgb/>
s a software package for graphs, digraphs, combinatorial designs, and their automorphism groups.
<http://kohlrabi.cs.umanitoba.ca/G&G/G&G.html>
Joseph Culberson
<http://www.cs.ualberta.ca/~joe/Coloring/Colorsrc/index.html> <http://www-leibniz.imag.fr/GRAPH/francais/logiciels.html> <http://www.research.att.com/sw/tools/graphviz/>
Commercial
<http://www.tomsawyer.com/glt/>
is a system dedicated to the visualization of huge graphs. It manages graphs with a number of elements(node and edges) up to 500.000 on a personal computer(PIII 600, with 256mo).
<http://www.tulip-software.org>

## PROGRAMMES

Jean-Paul Davalan

## OUTILS - TOOLS

Graph est un ensemble d'outils permettant de manipuler des graphes et plus particuliÃ¨rement de les visualiser.
Graphdot01 est un outil trÃ¨s simple permettant d'obtenir une image Ã  partir d'une description d'un graphe orientÃ©.
Il est constituÃ© de classes Ruby et d'1 programme Ruby permettant d'y accÃ©der, il n'est pas nÃ©cessaire de connaÃ®tre Ruby pour utiliser ce programme.
<http://patrick.davalan.free.fr/graph/> <http://www.ics.uci.edu/~eppstein/gina/gdraw.html> <http://rw4.cs.uni-sb.de/~sander/html/gsvcg1.html>
This toolbox contains Matlab code for several graph and mesh partitioning methods, including geometric, spectral, geometric spectral, and coordinate bisection. It also has routines to generate recursive multiway partitions, vertex separators, and nested dissection orderings; and it has some sample meshes and mesh generators.
John R. Gilbert Shang-Hua Teng
<http://www.cerfacs.fr/algor/Softs/MESHPART/>
is a family of programs for partitioning unstructured graphs and hypergraphs and computing fill-reducing orderings of sparse matrices. The underlying algorithms used by METIS are based on the state-of-the-art multilevel paradigm that has been shown to produce high quality results and scale to very large problems.
George Karypis, Rajat Aggarwal, Kirk Schloegel, Vipin Kumar, Shashi Shekhar
<http://www-users.cs.umn.edu/~karypis/metis/>
an application for phylogenetic tree drawing
This is a perl module for reading treefiles in the phylip format and generating PNG files with a graphical representation of the tree. It requires the GD.pm perl module for graphics drawing by Lincoln Stein
<http://csb.stanford.edu/gough/tree.html>
Sandiway Fong
Mac OS X 10.2 (or later)
Given two terms, wnconnect is a program that finds and reports all possible connections between them in WordNet, a popular and freely-available synset (synonym set) network with semantic relations. WordNet is from Princeton University, see http://www.cogsci.princeton.edu/~wn/.
<http://linguistics.arizona.edu/~sandiway/wnconnect/>
Tamar Barzuza,Itsik Pe'er
Graph Realization is the problem of constructing a tree from a set of its edge-labeled paths. More formally, Given subsets P1,..Pn of {0,..,m-1}, find a tree T=(V,E) with E={0,..,m-1} such that every Pi is a path in T, or determine that no such tree exists.
Graph Realization was first defined by Tutte [2]. Several polynomial algorithms for the problem were introduced in [1,3,4]. Graph Realization recently came back to awareness in computational molecular biology, in problems related to haplotype inference under the perfect phylogeny model [5].
<http://www.cs.tau.ac.il/~rshamir/greal/>

## SOURCES

<http://web.cs.ualberta.ca/~joe/Theses/HCarchive/main.html>

## JAVA

Kenji Ikeda
Simplex Twophase Dijkstra Prim Kruskal Ford-Fulkerson
<http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/main/index.shtml>
histoire des algorithmes de dÃ©composition modulaire. (Depuis 1972).
<http://www.liafa.jussieu.fr/~fm/DMJava/Graphe.html>

## PERL

Mkfunctmap is a Perl script that produces a graphical map of functions and function calls in a C program that was written by James Hoagland. Only those calls made to functions within the
<http://seclab.cs.ucdavis.edu/~hoagland/mkfunctmap.html>

## TESTS COMPÉTITIFS - BENCHMARKS

BHOSLIB: Benchmarks  with Hidden Optimum Solutions for Graph Problems
(Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring)
Maximum Independent Set (MIS) and Minimum Vertex Cover (MVC), Maximum Clique and Vertex Coloring, Forced Satisfiable CSP and SAT Benchmarks of Model RB, Pseudo-Boolean (0-1 Integer Programming) Benchmarks
<http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm>

## THÈSES - THESIS

Aspects algorithmiques et combinatoires  des realiseurs des graphes plans maximaux
par Bonichon Nicolas
<http://147.210.235.3/proprietes.html?numero_ordre=2627>
Vincent BarrÃ© - Univ. du Maine - Informatique [autre lien]
(Ãcrit en 1996 avant la dÃ©monstration de la conjecture forte des graphes parfaits
<http://volvo.univ-lemans.fr/~barre/articles/these/these.html>
Dans cette thÃ¨se nous nous intÃ©ressons Ã  l'existence de chemins, cycles et arbres dans les tournois et dans le dernier chapitre, nous considÃ©rons le cÃ´tÃ© algorithmique du problÃ¨me.
<http://www-sop.inria.fr/sloop/personnel/Frederic.Havet/publi/these.html>

## LIVRES - BOOKS

Jerry Spinrad  A draft of my book
(December 9, 1997) in postscript is here. Vanderbilt University Nashville, TN 37235, USA
<http://www.vuse.vanderbilt.edu/~spin/research.html>
Reinhard Diestel
<http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/index.html>

## SUJETS - SUBJECTS

Vasek ChvÃ¡tal
<http://www.cs.concordia.ca/~chvatal/perfect/spgt.html>

## DOCUMENTS - PAPERS

<http://www.univ-orleans.fr/SCIENCES/LIFO/Members/pecher/publications/publicationsFrancais.html> <http://www.cs.concordia.ca/~chvatal/publ.html>
by Russell Easterly October 7, 1999
<http://www.wolfenet.com/~logiclab/VertexCover.txt>
by Russell Easterly February 1 2000
<http://www.wolfenet.com/~logiclab/VertexNeighbor.htm> <ftp://ftp.brunel.ac.uk/maths/pub/> <ftp://riogrande.cs.tcu.edu/pub/morgenstern/>
Neil Robertson; Daniel P. Sanders; Paul Seymour; Robin Thomas
Dans cet article, on examine d'abord le concept de relation d'appartenance et sa signification thÃ©orique. Ensuite, on dÃ©finit le concept de place et celui de rÃ©seau de places, dont on analyse les propriÃ©tÃ©s algÃ©briques.
<http://www.erudit.org/erudit/socsoc/v31n01/pizarro/pizarro.htm>
<http://www.combinatorics.org/Surveys/ds1.ps> <http://arXiv.org/list/math.CO/recent>
Stanislaw Radziszowski (The El. J. of Combinatorics).
<http://www.combinatorics.org/Surveys/index.html>
A Survey of Venn Diagrams Frank Ruskey
<http://www.combinatorics.org/Surveys/ds5/VennGraphEJC.html>

## RÉSUMÉS - ABSTRACTS

<http://www-leibniz.imag.fr/DMD/sem/1996/bondy.html>

## JOURNAUX - LETTERS

<http://pauillac.inria.fr/~cheno/#lettre> <http://www.cs.brown.edu/publications/jgaa/> <http://isu.indstate.edu/ge/journals.html> <http://www.combinatorics.org>
maintained by Daniel P. Sanders
<http://www1.cs.columbia.edu/~sanders/graphtheory/writings/journals.html> <http://www.emba.uvm.edu/~jgt/~jgt/>

## COURS - COURSES

Groupe IREM de Luminy 2002
<http://www.irem.univ-mrs.fr/productions/polygraph.ps>
D. Sarni - L. Lemarchand
<http://fastnet.univ-brest.fr/~lemarch/Cours/Graphes_IUP2/graphes/graphes.html>
<http://pczenith.univ-mlv.fr/~jf/POLY/algo/algo2.html>
<http://wwwdim.uqac.ca/~rboudrea/inf211/notes.html>
Jean-Philippe Javet - Gymnase de Morges (Suisse) (~ lycÃ©e) Cours correspondant en France Ã  un niveau Term-ES (sp. maths) ou BTS (info. de gestion).
<http://www.gymnase-morges.info/math/javmath/polycopie/th_graphe.pdf>
filiÃ¨re GÃ©nie Informatique par Pierre Lopez
voir aussi les pages sur : ordonnancement, satisfaction, optimisation, contraintes
<http://www.laas.fr/~lopez/cours/GRAPHES/Spedago.html>
Gordon Royle Department of Computer Science The University of Western Australia.
<http://www.cs.uwa.edu.au/~gordon/remote/cs300/lectures/index.html#graphs> <http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/gcompcours.html>

## TUTORIELS - TUTORIALS - TUTORS

<http://www.info.univ-angers.fr/pub/gh/mmm/webarbl/arblang.htm>
Chris K. Caldwell (C) 1995
Graph Theory Tutorials
<http://www.utm.edu:80/departments/math/graph/> <http://pauillac.inria.fr/~cheno/>

## MANUELS - MANUALS

Joseph Culberson
<http://www.cs.ualberta.ca/~joe/Coloring/Colorsrc/manual.html> <ftp://ftp.research.att.com/dist/drawdag/dotdoc.ps.Z>
AGD offers a broad range of existing algorithms for two-dimensional graph drawing and tools for implementing new algorithms. It is a product of a cooperation of groups in Halle, KÃ¶ln, SaarbrÃ¼cken, and Wien, and originated from the DFG-funded project "Design, Analysis, Implementation, and Evaluation of Graph Drawing Algorithms" in 1995-2000. Currently, AGD is further developed by the groups in KÃ¶ln and Wien.
The AGD is available as library and/or within a complete easy-to-use demo program. It is publically (free) available for academic use.
The Boost web site provides free peer-reviewed portable C++ source libraries. The emphasis is on libraries which work well with the C++ Standard Library. One goal is to establish "existing practice" and provide reference implementations so that the Boost libraries are suitable for eventual standardization. Some of the libraries have already been proposed for inclusion in the C++ Standards Committee's upcoming C++ Standard Library Technical Report.
<http://www.boost.org/index.htm> <http://www.boost.org/libs/graph/doc/table_of_contents.html>

## CONFÉRENCES - MEETINGS

Thirty-first Southeastern International Conference  on Combinatorics, Graph Theory, and Computing
March 13-17, 2000
<http://www.math.fau.edu/CGTC/cgtc31/se31.html>

## ABONNEMENTS - MAILING LISTS

<http://www.lsoft.com/SCRIPTS/WL.EXE?SL2=1141&R=1569&N=GRAPHNET@LISTSERV.NODAK.EDU>
ist is for informal, collegial discussion of the latest research advances, and especially newsworthy cutting-edge or breakthrough developments, in the hardest problems in computation and mathematics. Topics are the famous and most difficult unsolved theoretical problems currently facing computer scientists and theoretical mathematicians.
<http://groups.yahoo.com/group/theory-edge/>

<liens_math.html>
Maurice Diamantini ENSTA / LMA / OC
Ce site a pour but de proposer quelques URL concernant le thÃ¨me trÃ©s large de la Recherche OpÃ©rationnelle, l'optimisation combinatoire et quelques disciplines associÃ©es.
<http://www.ensta.fr/~diam/ro/>
Part of Geometry in Action, a collection of applications of computational geometry. David Eppstein, Theory Group, ICS, UC Irvine.
<http://www.ics.uci.edu/~eppstein/gina/gdraw.html>

Advertising :   If you see a reference in one of the files that is not linked, and you know of a link address to the appropriate document, please send me mail, and I will include the link in the document. Thanks very much in advance.
Avertissement :    Le classement par catégories est approximatif. Certains liens se retrouvent dans des rubriques différentes et sur plusieurs pages. Les commentaires sont généralement des courts extraits des pages référencées. Il est possible que certains liens nécessitent une mise à jour.
Tous commentaires ou remarques sont les bienvenus, vous pouvez les adresser à :

Les mises à jour demandées sont réalisées dès que possible et, sauf si c'est nécessaire, aucun message de réponse n'est expédié. Merci de m'écrire.