Die zweite Gruppe struktureller Validierungen, die ausgeführt werden, sind so genannte Graphprüfungen. Mit diesen Prüfungen wird sichergestellt, dass der Flussgraph ein gerichteter zusammenhängender azyklischer Graph ist. Zu den Validierungen zählen:
- Der Workflow muss ein 'zusammenhängender' Graph sein. Dies bedeutet, dass jede Aktivität auf mindestens einem Weg von der Startaktivität zur Endaktivität erreichbar sein muss.
- Der Workflow muss einen azyklischen Digraph bilden. Dies bedeutet, dass es keinen Weg durch den Workflow geben darf, der zweimal auf dieselbe Aktivität trifft. Bei dieser Validierung wird nach Zyklen gesucht, die nur von Übergängen erstellt wurden. Zyklen, die mit Schleifenbeginn- und Schleifenendaktivitäten erstellt wurden, sind in jeder Hinsicht gültig.
- Jeder Untergraph der Instanz innerhalb des Workflow-Graphs muss richtig beendet werden. Das bedeutet, dass beim Starten von der Startaktivität alle möglichen Wege durch den Workflow an der Endaktivität enden müssen.