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. Two vertices are ADJACENT if there is an edge joining
them. (If a vertex has a loop, the vertex is adjacent to itself.) The DEGREE of a vertex is the total number of edges at
that vertex. (A loop adds 2 to the degree of a vertex.) A vertex with degree 0 is an ISOLATED vertex. 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.) A path that starts and ends at the same vertex is called a
CIRCUIT. 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. 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. |