In the previous chapter the idea of a subgraph was introduced. Intuitively, it is part of a bigger graph, some or all of its nodes, and the links for those nodes borrowed from the bigger graph. It is a piece of a bigger graph, without cutting any links in half.
A path is such a part of a bigger ugraph. A path provides a way for motion to go from a node to another node (or to the same node) in the ugraph. In Fig 2.1a a darkened path is shown between nodes A and B. In Fig 2.1b is another path also connecting those two nodes. It is easy to find other paths connecting A and B.
Using only the basic structures of ugraphs it is difficult to give a more precise definition of paths and loops. It is easier using a labeled ugraphs. Using integer labels in Fig 2.1c, the following notation for denoting the path in Fig 2.1a is very obvious in its meaning:
The chain for the
By its very nature a path has no break or interruption. Two nodes in a ugraph are connected if there exists a path between them. Nodes A and B are connected. But nodes A and C in Fig 2.1c are not connected because there can be no path between A and C.
The nodes 1,2,3,4,5,6,7 are connected by paths to each other, even 6 and 7 are connected. The subgraph containing them is called a component of the bigger ugraph. Another component contains nodes 8 and 9 and the edge linking them. The isolated node 10 is a component all by itself. A component containing a given node is the subgraph of all nodes connected to the given node.
If a ugraph has only one component, then every pair of nodes in the ugraph are connected. In that case the ugraph is said to be connected. Intuitively, it is entirely in one piece. For example a complete graph is always connected. (Recall that in a complete ugraph between every pair of nodes there is an edge.)
In Fig 2.1b a loop is part of the path. A path with no loops is called a simple path. The path in Fig 2.1a is simple. A simple path is an extension of the idea of an edge. It has two end points and has no indicated direction.
A loop (also called cycle) is a path that has 3 or more edges and connects some node with itself. In Fig 2.1c 2-4-5-2 is a loop. Graph theory is sensitive to the existence of loops. Loops in drawings can be more complicated than those shown here.
In a ugraph a path has a loop if some integer label is repeated in the chain of labels for that path.
In the chain for the path in Fig 2.1b the integer 4 appears twice (and 2 appears twice). Intuitively speaking, a path with a loop contains some unnecessary edges. The path in Fig 2.1b could be made shorter by omitting the two edges with end point 5 to get 1 - 2 - 4 - 7. This shorter path is simple and still connects A and B. A simple path is somehow "better" than a path with loops.
A path provides motion a way to go about a ugraph. It can go along a path that connects nodes in either direction. The motion is said to traverse the path. 1 -> 2 -> 4 ->7 indicates motion along the path 1 - 2 - 4 - 7 . But traversing a loop can be done indefinitely, going round and round. Refering to Fig 2.1c the notation 2 -> 4 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> 5 ->... indicates perpetual motion along a loop.
As is seen from the this discussion motion along an edge produces an arc (arrow along the edge). Motion along a path produces a sequence of arcs (arrows) indicating how motion has gone.
A directed path is a sequence of arcs (arrows) along some (undirected) path from node A to another node B in a ugraph. Each arrow points to the beginning of the next arrow. More precisely, node A is the tail of the first arc, B is the head of the last arc. Inbetween, the node that is the head of any arc is also the tail of the next arc.
See Fig 2.1e.
The directed path is an extension of the idea of an arc. Its definition here involves only basic structures, and does not involve the integer labels on nodes if they exist.
After a directed path has been created by motion from A to B, it will be useful in sections below to allow the motion to go back along the path to a previous node. The process of going along a path against the directions of the arcs to a previous node is called
The back tracking from B may include part or all of the way toward A, but must stop at a node. The directed path from A will always point to the node where the motion is located. See Fig 2.1g.
A tree is a connected ugraph with no loops.
The idea of a tree is an extension of the idea of a simple path. A single simple path is like a straight pole with the base at the top. However, in most situations the "pole" will have downward slanting branches (paths) coming out of it.
Every tree is in one piece and has a single root. To any node except the root there is a unique simple path between the root and that node. For motion the root usually serves as an entry point to a tree. Then motion can go down along any branch (edge) to any node below. Somewhere each branch stops at a node where no more branches are growing down. That node is called a leaf. A leaf is a node of degree 1.
Of course, it is usually possible to remove other edges from loops to get different spanning trees of the same ugraph. (But the uninteresting discrete graphs provide exceptions.)
A spanning tree of a ugraph is a connected subgraph without any loops. The spanning tree contains all of the nodes of the ugraph (and most often some of the edges).
A ugraph with a spanning tree must be connected, because the tree, by definition, is connected, and the tree contains all of the nodes of the ugraph. The spanning tree is "less complicated" than the entire ugraph. In fact using the spanning tree there is a path between any pair of nodes and that path is simple and unique.
If a ugraph is made up of more than one piece (i.e. has more than one component) then there will be more than one spanning tree involved in order to contain all the nodes.
It seems natural to call any collection of trees a forest. Each tree in a forest is separated from the other trees. Also each tree has its own unique root.
The downward slopes of all edges of a tree suggests direction. If motion starts at a root it goes down (never up) along some edges. But it cannot go past a leaf. In the next section motion will be used to create a tree made up of arcs (arrows along edges). Go to directed trees for a discussion of trees as special digraphs.
Trees have great importance in graph theory and elsewhere. They serve as a popular method for storage and retrival of information (data), for example the way an operating system, such as Windows or DOS, stores files on a computer disk. They are stored in tree-like structures. In these notes there will be a discussion of data trees later.
For clarity visited nodes are colored yellow. Unvisited nodes start out as white. See Fig 2.3a.
The task and its solution may be better understood by discussing a real-life situation. The rooms and corridors of a house follow a simple plan shown in Fig 2.3a. A detective must enter the house through one door and examine cmpletely all of the rooms of a house. Corridors make all rooms accessable. The task concludes with the detective's departure from the house through the same door.
His only way out is to backtrack to the previous
room. Fig 2.3b [2].
He sees an unvisited room (white node) down another corridor and goes down it as far as he can. Fig 2.3b [3].
There are still two unvisited rooms (two white nodes). So again he backtracks through several rooms. Fig 2.3b [4].
He sees the two yet unvisited rooms and goes down the corridors into them. Fig 2.3b [5].
He backtracks again all the way to the top room where he entered the house.
There are no more unvisited rooms (all nodes are yellow). So he backs out of the house (into the green box).
All the rooms have been visited. Remove the arrows and see that all the nodes are yellow. See Fig 2.3a.
Several points have been omitted to make the explanation simple. Instead of painting a room yellow to indicate it was visited, the detective could drop a piece of yellow paper onto the floor. Then he could look down all the corridors to adjacent rooms to find a room without a yellow paper.
In the discussion above the ugraph was a tree, so there were no problems caused by loops. But the method of applying yellow can be extended to the general ugraph, which most likely will have loops. It is easier to work with labeled ugraphs. Transversing a labeled ugraph is discussed in additional material.
==================
Section 2.2 Trees and spanning trees
Sometimes a graph is drawn in a shape that can be recognized. Fig 2.2a shows a ugraph in the form of a tree (more like a bush). Actually the tree is drawn upside down. It is traditional to draw it that way, so the root is on top, and the branches (edges) slant downward.
In the previous section comments were made against loops in a ugraph Motion along paths without loops (simple paths) were "easier" to traverse. In Fig 2.2b is a ugraph with several loops. If the five blue edges are removed then the tree in Fig 2.2a appears. Although some edges were lost, no nodes were lost. The tree in fig 2.2a is a spanning tree of the connected ugraph in Fig 2.2b.
===================
Section 2.3 Traversing a connected ugraph
In the study of graph theory there is a classical problem with an interesting solution. Essentially, the task is for a motion to visit all of the nodes of a ugraph. This process is called traversing the ugraph. The task is made slightly easier if the ugraph is connected (all in one piece). As a by-product the traversing of a connected ugraph will become also be a method for producing a spanning tree of that ugraph.
The method of transversing is simple. Go down corridors until he can go no further. (Since the ugraph is a tree, the node will be a leaf.) He enters from the outside with the symbol of a green box. Then he goes down as far as he can go. He passes through three rooms to do this. See Fig 2.3b [1].