Terminology

A GRAPH is a relational structure made up of vertices and edges. The edges of a graph express the relationships among the vertices.

An edge that connects a vertex to itself is a LOOP. example

Two vertices are ADJACENT if there is an edge joining them. (If a vertex has a loop, the vertex is adjacent to itself.) example

The DEGREE of a vertex is the total number of edges at that vertex. (A loop adds 2 to the degree of a vertex.) example

A vertex with degree 0 is an ISOLATED vertex. example

A PATH in a graph is a route among vertices along the graph’s edges such that no edge is used more than once. (Paths are specified by listing adjacent vertices from the beginning of the path to the end of the path.) example

A path that starts and ends at the same vertex is called a CIRCUIT. example

A graph is CONNECTED if any two of its vertices can be joined by a path. A graph that is not connected is DISCONNECTED. The resulting ‘pieces’ of a disconnected graph are called COMPONENTS of the graph.

If erasing an edge of a connected graph would cause the graph to be disconnected, that edge is called a BRIDGE.

A path that contains every edge of a connected graph exactly once is called an EULER PATH.

An Euler path that starts and ends at the same vertex is called an EULER CIRCUIT.

A LINE DRAWING is the name often given to a graph in which the vertices are not shown (the edges just connect directly) and the edges are all line segments.

wpe1.jpg (7794 bytes)

For all practical purposes, you can just think of a line drawing as a graph whose vertices are so small that you can't see them.

A line drawing has a UNICURSAL TRACING if it can be traced without lifting the pencil or retracing any line.
A unicursal tracing is CLOSED if the tracing starts and ends at the same point.
A unicursal tracing is OPEN if the tracing starts and ends at different points.

Back