Graphes d'agencement

malavita

Bonjour,

de ce que j'en ai compris un "graphe d'agencement" est un graphe orienté tel qu'entre deux sommets il existe au plus une arête, sans cycle.
Dans un tel graphe une racine est un sommet auquel n'arrive aucune arête.
Pour représenter un tel graphe, je procéderais de la façon suivante: je classerais les sommets en fonction de leur "rang", le rang étant défini de la façon suivante:
-un racine a pour degré 0
-un sommet A, qui n'est pas une racine, a pour degré 1+rang(A,r(G)), où r(G) est le sous graphe de G obtenu en supprimant les racines et les arêtes partant de ces racines.

J'ai par contre quelques doutes sur la terminologie que j'utilise, ainsi que sur ma définition. Cette dernière est elle suffisante pour affirmer qu'un graphe "d'agencement" possède une racine.

Bonne soirée

F.

GaBuZoMeu

Tu ne supposes pas que le graphe est fini ?

malavita

Si bien sûr...

GaBuZoMeu

Cela va peut-être sans dire, mais cela va beaucoup mieux en l'écrivant !
Autre question : quand tu dis "sans cycle", est-ce que l'orientation des flèches joue un rôle dans la définition de cycle ?

malavita

Oui, je pense. Une flèche signifiant suivant le contexte: "la tache A est réalisé avant B" ou "le dossier A contient le dossier B".