Pfadfamilien

Pfadfamilien, or path families in English, are a concept in graph theory. In a graph G = (V, E), a Pfadfamilie F is a collection of simple paths in G. Each path is a sequence of distinct vertices v1, v2, ..., vk with consecutive vertices joined by edges. In directed graphs, the paths respect edge directions and are called directed or s-t paths when endpoints are specified.

Path families are studied with various constraints. A vertex-disjoint path family is one in which the paths do not share any vertices (except possibly endpoints, depending on the exact formulation). An edge-disjoint path family requires that no edge is used by more than one path. A path cover is a path family whose union of vertex sets equals V(G), i.e., every vertex lies on some path in the family. In directed graphs, one often considers s-t path families, where each path starts at a designated source s and ends at a designated target t.

Key problems related to Pfadfamilien include the disjoint paths problem, which asks whether there exist k pairwise disjoint paths connecting specified pairs of terminals, and the maximal packing version, which seeks the largest possible number of disjoint paths under given constraints. The theories of Menger and related results connect disjoint path questions to cut sizes in graphs and underpin many algorithmic approaches in network design and routing.

Applications of path families appear in network routing, VLSI circuit design, and routing problems where non-overlapping paths are required for reliability or physical constraints. Pfadfamilien provide a unifying framework for analyzing how many independent routes a graph can support between specified endpoints, and they interface with topics such as flows, matroids, and combinatorial optimization.