-
Notifications
You must be signed in to change notification settings - Fork 81
What are edges in graph theory
Graph Edge
For an undirected graph, an unordered pair of nodes that specify a line joining these two nodes are said to form an edge. For a directed graph, the edge is an ordered pair of nodes. The terms "arc," "branch," "line," "link," and "1-simplex" are sometimes used instead of edge (e.g., Skiena 1990, p. 80; Harary 1994). Harary (1994) calls an edge of a graph a "line."
The following table lists the total number of edges in all graphs of given classes on n nodes.
graph | Sloane | n=1, 2, ... |
---|---|---|
graph | A086314 | 0, 1, 6, 33, 170, 1170, 10962, 172844, 4944024, ... |
labeled graph | A095351 | 0, 1, 12, 192, 5120, 245760, 22020096, ... |
labeled tree | A053506 | 0, 1, 6, 48, 500, 6480, ... |
planted tree | A055544 | 0, 1, 2, 6, 16, 45, 120, 336, 920, 2574, 7190, 20262, ... |
rooted tree | A095350 | 0, 1, 4, 12, 36, 100, 288, 805, 2288, 6471, 18420, 52426, ... |
tree | A095349 | 0, 1, 2, 6, 12, 30, 66, 161, 376, 954, 2350, 6061, 15612, 41067, ... |
A graph consists of vertices and edges between vertices. Think of connect the dots. The dots are the vertices, and the arcs between them are the edges. If you want to abstract that way, a graph can be thought of as a 2-tuple of sets. G=(V,E). V is called the vertex set and E is the edge set. In the case of directed graphs, you have a map ϕ:E→V×V. In the case of an undirected graph, you have a map ϕ:E→V2 where V2={{v,w}:v,w∈V}.
An edge connecting a vertex to itself is called a loop. In the graph below, the loop is the edge that connects vertex 1 to itself.