Allgemeine Graphen enthalten ungerichtete Kanten und gerichtete Bögen in beliebiger Mischung. Sie eignen sich gut für eine einheitliche Darstellung der Graphentheorie. In a-Wegen in allgemeinen Graphen dürfen Bögen in beliebiger Richtung durchlaufen werden. Bei f-Wegen ist der Durchlauf nur vom Anfangsknoten zum Endknoten gestattet. k-facher Zusammenhang wird definiert durch gegenseitige Erreichbarkeit auf mindestens k unabhängigen Wegen. Maximale k-zusammenhängende Untergraphen heißen k-Komponenten, wenn die Wege keine gemeinsamen inneren Knoten haben, und k-Linienkomponenten, wenn sie keine gemeinsamen Kanten/Bögen haben.

Gesucht ist die Zerlegung eines allgemeinen Graphen in k-Komponenten und k-Linienkomponenten für k=1,2,... sowohl für a-Wege als auch für f-Wege. Für k>3 ist der Satz von Menger die Basis der Zerlegungsalgorithmen. k-Linienkomponenten lassen sich in polynomieller Zeit finden. Bei k-Komponenten ist offen, ob sie in polynomieller Zeit gefunden werden können.