Graph

Sage

Un graphe peut être orienté ou non.

Il y a aussi un traitement en Sage des graphes bipartites

Les graphes non orientés d'abord

Un graphe, c'est un "ensemble" de sommets (vertex en anglais, pluriel vertices) et un "ensemble" d'arêtes (edge en anglais) reliant deux sommets (on verra que l'on peut associer à une arête une information : label).

Graph est une classe.

On peut soit :

  1. créer une graphe vide et rajouter sommets et arêtes au fur et à mesure par appel de méthodes ;
  2. ou créer un graphe via un constructeur qui accepte un dictionnaire donnant pour chaque sommet la liste de ses voisins ;

Première méthode. Graphe vide.

g = Graph (); # appel d'un constructeur sans paramètres qui crée un graphe vide, sans sommets, sans arêtes. On pourra ajouter sommets et arêtes

Quelques premières méthodes (on les trouve décrites ici) :

  • g.order() # qui donne le nombre de sommets du graphe g
  • g.size() # qui donne le nombre d'arêtes du graphe g
  • g.add_vertex(1) # on ajoute le sommet 1 (il ne doit pas déjà exister)
  • g.add-vertices ([2,3,4,5]) ; # 4 sommets viennet se rajouter. Cette méthode accepte une liste
  • g.add_edge (1,2) ; # on ajoute une arête qui relie les sommets 1 et 2 (on aurait pu avec le même effet écrire g.add_edge (2, 1), car le graphe est non orienté
  • g.add_edges ([(1,3), (1,4), (4,5)]) # liste de tuples. On rajoute d'un seul coup 3 arêtes
  • g.delete_vertex(1) g.delete-vertices ([2,3,4,5]) g.delete_edge (1,2) g.delete_edges ([(1,3), (1,4), (4,5)]) # 4 méthodes pour retirer sommets et arêtes
  • g.vertices () # rend la liste des sommets du graphe g (pas un ensemble)[1,2,3,4,5]
  • g.edges () # rend la liste des arêtes du graphe g (pas un ensemble) avec une information supplémentaire pour chaque arête, l'étiquette (label) [(1,2, None) (1,3, None), (1,4, None), (4,5, None)]
  • g.set-edge-label (1,2, "pompidou") La méthode pour positionner une ériquette
Le mieux pour obtenir la liste complète et la documentation sur les méthodes (près de 250!!!) est d'utiliser l'aide en ligne de l'interpréteur de Sage.

Deuxième méthode. Création d'un graphe à l'aide d'un dictionnaire

g = Graph ( {

1 : [2, 3, 4]

4 : [5]

})

Les graphes orientés

On les appelle digraphe (directed graph)

dg = digraph() # un digraphe vide

Toutes les opérations que l'on a indiqué ci-dessous fonctionnent, à la différence près que l'on n'a plus des arêtes, mais des arcs :

dg.add_edge(2,3) # rajoute un arc qui va du sommet 2 au sommet 3. Cela ne crée pas un arc qui va de 3 vers 2

Il y a plein de sous-classes correspondant à des types ou familles de graphes particuliers (près de 70)

Module graphs

Exemple

p = graphs.PetersenGraph() ;


Pour plus d'informations


» Glossaire de Sage