An edge is a fundamental element in graph theory that represents a connection, relationship, or link between two nodes in a graph. Edges act as the connective tissue of graphs, defining how different entities relate to or interact with each other. In its simplest form, an edge is depicted as a line or arc connecting two nodes, though it can carry additional information such as weight, direction, or other attributes.
Edges can exist in several forms, with the two main categories being directed (one-way connections) and undirected (two-way connections). In directed graphs, edges are typically represented as arrows showing the flow or relationship direction, while in undirected graphs, they appear as simple lines. Edges can also carry weights, which might represent distances, costs, strengths of relationships, or other quantitative measures that describe the nature of the connection.
The characteristics of edges play a crucial role in graph algorithms and analysis. Edge properties such as weight, capacity, or type influence path-finding algorithms, network flow calculations, and connectivity analysis. Multiple edges can exist between the same pair of nodes (creating parallel edges or multi-edges), and edges can even connect a node to itself (forming self-loops or loops), though some graph types specifically prohibit these features.
Common alternative names for edges include:
The terms "edge" and "arc" are the most widely used, with "edge" being the standard term in most contexts and "arc" being more commonly used when specifically discussing directed graphs.
