loopfreie

Loop-free (loopfrei) describes structures that contain no loops, that is, no edges from a vertex to itself. In graph theory, a loop-free graph has no self-loops; in directed graphs, this means there is no arc that starts and ends at the same vertex. Loop-free is not the same as acyclic: removing self-loops eliminates only edges of length one; cycles of longer length may still exist.

Common terminology: a loop-free graph often coincides with what is called a simple graph when also no parallel edges are present; if parallel edges are allowed, the graph remains loop-free but is no longer simple.

In computer networking, loop-free topologies prevent forwarding loops caused by redundant links. Protocols such as the Spanning Tree Protocol (STP) and its successors create a loop-free subset of the physical network, forming a tree to guarantee a unique path between hosts. In routing, loop-free properties of protocols ensure that packets do not circulate indefinitely.

In algorithms and data structures, loop-free traversal implies that searches do not revisit the same node, typically using visited markers; in graph classes, loop-free is a property that helps ensure termination and correctness in certain procedures.

Examples: an edge from A to A is a self-loop, illustrating a loop; a triangle with edges AB, BC, CA has no self-loops but contains a 3-cycle.