Additional Material for Chapter 1

Additional Material F1

Graphs with the maximum numbers of links

There are two extremes to the number of links in a graph with a finite number of nodes. One extreme is no links, which makes every node isolated. Any graph of isolated nodes is of little interest. The other extreme exists when every pair of nodes in the graph has a link joining them. (Any more links would force some pair of nodes to have two links between them.) Such a graph is called complete.
(*) Using motion in a complete graph it is possible to go from any node to any other node by going along exactly one link.

The adjacent figure shows graphs A1, A2, A3, A4 and A5 that have 1,2,3,4 and 5 nodes respectively. Focus attention on A4. Each node in graph A4 has degree 3 (three links contact any node).Adding all these contacting links gives 3+3+3+3 = 12. But A4 shows only 6 links, because 3+3+3+3 counts each link twice (each link has two ends.)

The number of links in A4 = (3 + 3 + 3 + 3)/2 = 4x3/2 = 6 In A5 each fo the 5 nodes has degree 4. Add all degrees and divide by 2: The number of links in A5 = (4 + 4 + 4 + 4 + 4)/2 = 5x4/2 = 10 For a complete graph with N nodes, the number of links = ( (N-1) + (N-1) + ... + (N-1) )/2 = N(N-1)/2

The number of links in a complete graph with N nodes = N(N-1)/2.

Long and short graphical array for a ugraph

The adjacency list ## can be written as an long graphical array: [ (1),2,3, (2),1,3,4,5, (3),1,2,6, (4),2,5,7, (5),2,4, (6),3, (7),4, (8), (9),10, (10),9] In each cluster the (leading integer) is first and represents a node, while the remaining integers in that cluster are secondary integers and are neighbors of that node.

The above array can be translated into a sequence of edges:

1-2 1-3 2-1 2-3 2-4 2-5 3-1 3-2 3-6 4-2 4-5 4-7 5-2 5-4 6-3 7-4 8-0 9-10 10-9 Rearranging this sequence so that the same edge is repeated (except for the pseudo-link 8-0):

      1-2  2-1    1-3  3-1    2-3  3-2    2-4  4-2    2-5  5-2    3-6  6-3    4-5  5-4    4-7  7-4    8-0    9-10  10-9

Now delete the second linked nodes of each pair:

   1-2   1-3   2-3   2-4   2-5   3-6   4-5   4-7   8-0   9-10

This last sequence of edges (without the pseudo-link) can be written as a short graphical array:

S   (1),2,3,   (2),3,4,5,   (3),6,   (4),5,7,   (9),10

S has all the links of Fig 1.2a, yet no link is repeated. Excluding the pseudo-link, S gives the exact number of links. But in S not all the integer labels on nodes appear in parentheses. The node numbers 5,6,7,10 are not listed as leading integers of any clusters because their neighbors have lower numbers.

Difficulty with determining equivalence of two graphs

Even high speed super computers could not solve the problem in a person's lifetime for some pair of graphs with many nodes in them by testing all of the permutations to see if any produces a graphical equivalence.

Even for some pair of Ugraphs with only 25 nodes each, the checking of all the permutations for graphical equivalences is incredibly numerous. To see this, notice that the number of permutations is 25! = (approximately) 1.55x10²⁵. Suppose the computer can check 1 billion (10⁹) permutations each second. There are 3.15x10⁷ seconds in each year. This means that the computer can check

3.15x10⁷ x 10⁹ = 3.15x10¹⁶ permutations for graphical correspondences in a year. Therefore, the number of years to check all permutations are 1.55x10²⁵/3.15x10¹⁶ = 4.9x10⁸ = almost half a billion years. Could a computer doing 1 trillion checkings a second be certain to accomplish the task in a lifetime?

Number of links in a complete Ugraph

In a graph with N nodes suppose each node is linked to every other node. That linkage requires N-1 links, since the node is not linked to itself. Doing this for all N nodes produces a sum of N products N-1 + N-1 + ... + N-1. which is equal to the single product N(N-1). But the sum, and hence the single product, counts every link twice. Therefore the actual number of links is MAXL(N) = N(N-1)/2. This is called the closed formula for computing the number of links in a complete graph of N nodes.

*** To derive another formula, notice a pattern in the increase of the number of links when a new node is included in a complete graph of N nodes to get a complete graph of N+1 nodes: N = 1 to N+1 = 2     A1 to A2     0 + 1 = 1;
N = 2 to N+1 = 3     A2 to A3     1 + 2 = 3;
N = 3 to N+1 = 4     A3 to A4     3 + 3 = 6;
N = 4 to N+1 = 5     A4 to A5     6 + 4 = 10; The pattern of red numbers is clear. It increases by 1 when N increases by 1. In fact it is always the same as N: increase = N The increase always equals N because N new links are needed to attach it to the N nodes already in the old graph. Therefore, the formula MAXL(N+1) = MAXL(N) + increase becomes MAXL(N+1) = MAXL(N) + N This is an iteration formula which can be proven by induction given L(1)=0, or by substitution of the formula MAXL(N) = N(N-1)/2 into it.
The computer can use iteration formula repeatedly to calculate the maximum number MAXL(N) of links for any number N of nodes, as easily as the closed formula MAXL(N) = N(N-1)/2 that is prefered for calculation by hand or calculator.

Construction of a path in a connected graph that visits every node once and only once

By definition the links of a Ugraph are bidirectional. However, motion along a path has a single direction. Since motion will be fundamental to this discussion, a premature use of direction along some links will be used before more detailed discussions about Digraphs in Chapter 3.

The computer controls a robotic bug . It directs the bug to visit all the nodes in a connected Ugraph. There must be a first node which marks the start of the journey of the bug about the graph, and a last node when the bug has finished the task.

During the journey the bug most often enters a node from some link and goes out of that node along a different link. The task is simple for traversing all the nodes in the linear graph in the adjacent figure from left to right.

The journey is more complicated if some nodes have more than one way out (degree 3 or higher). In each of those nodes a decision must be made: which exit to select. In the chapter 4 the computer will use numbers assigned to all the links to be used for the choice of exits from nodes. In this discussion the numerical labels assigned to each node will be used. In the full adjacency array a list of all of its adjacenct neighbors after each (node). The following method can be used: when the bug is in a node with more than one exit, the computer which sees only (the equivalent to) the long adjacency array selects the neighbor with the lowest label number and the bug exits along the link that leads to that neighbor.

Three common problems arise and additional parts will be added to this method to produce a universal solution:
  (a) while trying to visit all nodes the bug may visit some nodes more than once;
  (b) by choosing every time a neighbor with the smallest label number the bug may traverse an endless loop;
  (c) after moving along a path through nodes, the bug may enter a node with no other way out.

The computer can prevent the bug from entering any node more than once, by remembering what nodes have been visited. It puts a mark by the label number if the node has been visited. In the adjacent figure the nodes already visited are colored yellow. The computer bug has already visited nodes 5 and 7 during travels in another part of the graph (not shown).The bug has moved along through nodes 2 and 3 and has entered node 4, coloring the nodes as it enters. The unvisited neighbor of node 4 with the lowest number label is nod 8. The bug exits node 4 and goes to 8. Then node 8 will become yellow. The computer will actually put a mark by label 8. The avoiding of nodes already visited solves problems (a) and (b).

There are two types of nodes with no exits: (1)a leaf (node of degree 1) has an entrance but no exit, and (2) all the neighbors of a node have already been visited. Both problems are solved by allowing the bug to back up until it finds a node with one or more unvisted neighbors. Therefore, a bug must allowed to back up into a visited node, but not go forward into a visited node. With this agreement, no node will be visited more than once.

This backing up procedure has a problem. When the bug is in the last node, then all nodes have been visited. Backing up will take the bug all the way back to the first node where it entered the graph. The computer cleverly created an "artificial node" not part of the graph, and assigned it the prohibited number label 0 (zero). The artificial node is linked artificially with the first node where the bug entered the graph. Since all nodes of the graph have been visited, the bug in the first node will back up into the artificial node. The computer detects the label 0 and terminates the program.

The computer may list all the visited nodes. The list should be a permutation of all the label numbers, that is, a permutation of 1,2,...,n, where n = number of nodes.

Two comments should be made. The choice of the neighbor of a (node) with the smallest label number may be changed to the choice of the neighbor that has not yet been visited and has the largest label number. The printout of all the visited nodes will be another permutation of 1,2,...,n. Other systematic selections of neighbors will produce new permutations.

The above procedure of a travelling bug can be extended to Ugraphs that are not connected. After the bug has visited all nodes in a component it backs up into the zero node, the computer checks to see if any node in the graph has not yet been visited. If any exist it selects the unvisited node with the smallest label number, attaches the zero node to it and the bug enters that node. By this method all the nodes of the graph will be visited. More useful is the printing out all the nodes in each component separately. In this way the computer reveals all the components of the graph.

Input Data from a Ugraph for the Computer

The adjacent drawing shows a graph PLUTO. The following steps create and place the defining information about the graph into the computer.

Step 1. Create an adjacency list for the graph.
The long adjacency list for it is   (1),2,3
  (2),1,3,4,5
  (3),1,2,5
  (4),2,5,6
  (5),2,3,4,6
  (6),4,5,7
  (7),6
Removing the red numbers produces the short adjacency list. The black numbers are needed for the input. The red numbers may or may not be included.

Step 2. Click on the link Computer (InputDataU) to go to a list of executable computer programs. There, click on the program InputDataU to start the program. (The U means that the input-data is from a Ugraph.)

Step 3. Answer the questions from the computer.
Where is the input-data for the Ugraph?
If it will be typed in on the (K)eyboard, type K (it will be typed in )
If it is already in the GraphData (F)ile, type F
K <--- ans.
Not exceeding 10 characters, input name of graph PLUTO <--- ans.
Input number of nodes: 7 <--- ans.
Input every neighbor with higher natural number after each (node):
(1),2,3 <--- ans.
(2),3,4,5 <--- ans.
(3),5 <--- ans.
(4),5,6 <--- ans.
(5),6 <--- ans.
(6),7 <--- ans.
(7), <--- no ans.

During the conversation about (node) and their neighbors, the computer prints out the(node), and the numbers (neighbors) and commas after it are typed in as answers.

The computer prints out the following information about the graph:
Ufile PLUTO 7 Nodes 10 Links
The array of degrees:
(1)2 (2)4 (3)3 (4)3 (5)4 (6)3 (7)1

The long adjacency array is:
(1),2,3, (2),1,3,4,5, (3),1,2,5, (4),2,5,6, (5),2,3,4,6, (6),4,5,7, (7),6,

The short adjacency array is:
(1),2,3, (2),3,4,5, (3),5, (4),5,6, (5),6, (6),7, (7), Change data? if YES then press Y key. Pressing any other letter key means NO n [U "PLUTO", (1),2,3, (2),3,4,5, (3),5, (4),5,6, (5),6, (6),7, (7)]

The computer stores the input-data including the brackets [ ] in a text file. If the graph is used again, the input data can be retrieved from the file (ans. F instead of K).