Graph Theory: Paths and Circuits

Isomorphism

Two graphs are thought of as equivalent and are called isomorphic if they have identical behavior in terms of graph theoretic properties.

Two graphs G and G' are said to be isomorphic to each other if there is one-to-one correspondence between their vertices and between their edges such that the incidence relationship is preserved.

In other words suppose that edge e is incident on vertieces v₁ and v₂ in G; then corresponding edge e' in G' must be incident on the vertices v₁' and v₂' that correspond to v₁ and v₂ respectively.

Two isomorphic graphs must have:

1. The same number of vertices.

2. The same number of edges.

3. And equal number of vertices with a given degree.

These conditions are by no means sufficient. Finding simple and efficient criteria for detection of isomorphism is still actively pursued and is an important unsolved problem in graph theory.

Subgraph

Graph Theory: Introduction

Your browser does not support the canvas element.

Graph Definition

Graph is a collection of edges and vertices.

G = (V, E)

V is set of vertices and E is set of edges.

Each edge is identified with pair of vertices (v_i, v_j).

Vertices associated with edge ek are called the end vertices of e_k.

A vertex is also referred to as node, junction, point.

Other terms used for an edge are a branch, a line, an element.

Loop

An edge having the same vertex as both its end vertices is called as self loop or simply a loop.

Parallel Edges

Edges having same pair of vertices as their end veritices are called parallel edges.

Simple Graph

A graph that has neither self loops nor parallel edges is called simple graph.

Incidence

When a vertex v_i is n end vertex of some edge e_j, v_i and e_j are said to be incident to each other.

Adjacent

Two non-parallel edges are said to be adjacent if they are incident on a common vertex.

Two vertices are said to be adjacent if they are the end vertices of the same edge.

Degree of a vertex

The number of edges incident on a vertex v_i with self lopps counted twice is called the defree d(v_i) of vertex v_i.

Degree of vertexd is sometimes also referred to as its valency.

Hand Shaking Theorm

Since each edge contributes two degrees, the sum of the degrees of all vertices in graph G is twice the number of edges in G.

Sum(deg(v_i)) { for i = 1 to n } = 2 . e

n = number of vertices.

e = number of edges.

Theorm 1.1

The number of vertices of odd degree in a graph is always even.

sum of degrees of all vertices = sum of degrees of vertices with even degrees + sum of degrees of vertices with odd degree

Left Hand Side is even number. The first term in Right Hand Side is even number. So the second term in RHS also needs to be an even number. Hence the theorm.

Regular Graph

A graph in which all vertices are of equal degree is called a regular graph.

Isolated vertex

A vertex having no incident edge is called an isolated vertex. Isolated vertices are vertices with zero degrees.

Pendant Vertex

A vertex of degree one is called a pendant vertex or an end vertex.

Edges in series

Two adjacent edges are said to be in series if their common vertex is of degree two.

Null Graph

A graph without any edges is called a null graph. Every vertex in a null graph is an isolated vertex.

Prefix and Suffix sums puzzle

This is a problem related to prefix and suffix sums. Before mentioning the actual problem, let me first explain what are prefix and suffix sums.

What is mean by prefix sum? 
Consider an example for sequence of 3 integer numbers: 5  -2  7
The prefix numbers are: 5  3  10
These are generated as follows:
   5  (5+ (-2))   (5 + (-2) + 7)
= 5       3             10

What are suffix sums? 
For the same above example of 3 integer numbers, the suffix sums are: 7  5  10
These are generated as follows:
   7       (7 + (-2))    (7 + (-2) + 5)
= 7            5               10

Problem: 
Determine the number of different possible sequences of integers that can generate given prefix and suffix sums.

For example, following are all the prefix and suffix sums in some random order:
3  5  7  10  5  10

Since the count of above numbers is 6, the original sequence of numbers has to be 3. So the task is to find out how many different sequences of 3 integer numbers can result in same values of above mentioned prefix and suffix sums?

For this particular example, following are all possible sequences of 3 integer numbers whose prefix and suffix sums are: 3  5  7  10  5  10

5  -2  7
7  -2  5
3   2  5
5   2  3

The count of all possible integer sequences is 4 and hence the answer is 4 for this particular example.

In general, the problem can be stated as: Find out the count of sequences of n integer numbers whose prefix and suffix sums are equal to the given 2*n integer numbers mentioned in random order.

Algorithm

Let us consider sequence of n numbers as follows:

x1  x2  x3  . . .  xn

The prefix sums are:

x1  (x1+x2)  (x1+x2+x3)   (x1+x2+x3+x4)    . . .   (x1+x2+x3+...xn)

= n.x1 + (n-1).x2 + (n-2).x3 + . . . xn

Similarly, the suffix sums are:

xn  (xn+x(n-1))   (xn+x(n-1)+x(n-2))   (xn+x(n-1)+x(n-2)+x(n-3))   . . .   (xn+x(n-1)+x(n-2)+x(n-3)...x1)

= n.xn + (n-1).x(n-1) + (n-2).x(n-2) + . . . x1

If we add all prefix and suffix sums, the combined term becomes:

n.x1 + (n-1).x2 + (n-2).x3 + . . . xn
+
  x1 +     2.x2 +     3.x3 + . . . n.xn

= (n+1)x1 + (n+1)x2 +  (n+1)x3  + . . . (n+1)xn

= (n+1)(x1+x2+x3+...+xn)

= (n+1) . sum(x)

The value for sum(x) can be determined as follows:

sum(x) = (sum of all prefix and suffix sums) / (n+1)

Note that sum(x) may not be always the largest value especially if any of numbers in original list (x1 to xn) contains negative values. We can use above formula to determine the value of sum(x) in all cases, whether original sequence contains +ve or -ve numbers, it doesn't matter, the formula will give us the correct sum(x) value.

For example, consider following example with suffix and prefix sums (in some random order):

5  3  10  7  5  10

Sum of all above numbers is: 40 and n=3 so the sum of original numbers is 40/(3+1) = 10

I generated above prefix and suffix sums using 5  -2  7. There are other possible sequences that can result in same prefix and suffix sums, but their sum has to be 10.

Note that 10 appears twice. If sum(x) does not appear twice in given prefix and suffix sums, then, it is an invalid input and no solution is possible. So the result in such case is zero.

Remove the two sum(x) numbers from the list, and arrange the remaining numbers in ascending order:

3  5  5  7

Notice that addition of first and last numbers is also sum(x). Similarly, the addition of second and last but one is also sum(x). This is the case for all such pairs. If it is not, then, solution is not possible and the result is zero.

Why is this so? How can we draw such a conclusion?

Consider the original sequence: 5  -2  7
following table shows prefix and suffix sums for each of the position as follows:

Original numbers                       : 5  -2  7
Prefix sums(up to the position)   : 5   3  10
Suffix sums(up to next position) : 5   7  0
Addition of prefix & suffix sum  : 10  10 10

In above table, in each column, the value for prefix and suffix sums mentioned are for the two sub-lists of the original sequence. The addition of these two sub-lists equals the addition of all numbers from the entire list.

For example:
at position 1, the two sub-lists are: (5) (-2 7)
at position 2, the two sub-lists are: (5, -2) (7)
and at position 3, the two sub-lists are: () (5 -2 7)

The first sub-list is the prefix sum at that particular position, second sub-list is the suffix sum. Their sum must equal sum(x). Basically, it does not matter at which position the list of numbers is split in two parts; the sum of two sub-lists always must equal to the sum of entire list. Hence the proof.

Hence for each prefix sum there must exist one suffix sum such that their addition is equal to sum(x). If this is not the case, then, solution is not possible. And the answer is zero in such case.

So in above example, there are 2 pairs of prefix and suffix sums: (3 7) and (5 5).

One particular sequence of prefix sums uniquely defines sequence of original numbers. So to compute the number of original sequences, we need to determine the number of possible sequences of prefix sums.

For the given example, following are all possible permutations:

                                                Case 1           Case 2          Case 3          Case 4
Prefix sums                           :   3  5  10         7  5  10        5  3  10        5  7  10
Suffix sum up to next position :   7  5   0          3  5   0        5  7   0         5  3   0
original numbers                     :   3  2   5         7  -2  5        5  -2  7         5  2   3

For this example, the answer i.e. the count for different possible sequences is 4.

The prefix sums can be generated by permuting in following manner:

1. From the pair of prefix and suffix sum that adds to sum(x), any number can be prefix sum. So if these are different numbers, then, the possibilities are doubled.

2. We can arrange (n-1) prefix sums in any order. If all the prefix sum values are different, then, we will have (n-1)! number of counts for prefix sums. But if some prefix sums are repeated, then, the count can be obtained by using npr formula.

In general, there exists (n-1) pairs of prefix and suffix sums that add exactly to sum(x). Out of these, if any pair repeats, then we maintain a count of how many times that pair repeats. Let us say we have got "k" different pairs of prefix and suffix sums with counts as n1, n2, n3, . . . , nk where k is the number of unique pairs. And let us say "u" as the number of pairs containing different values for prefix and suffix sum, then the formula for count is:

     (n-1)! * 2 ^ u
________________________
(n1! * n2! * n3! . . . nk!) 

For above example:
n = 3
k = 2
n1 = 1 (pair: (3 7) appears once)
n2 = 1 (pair: (5 5) appears once)
u = 1 because there is only one pair (3 7) that has prefix sum != suffix sum.

Hence the count becomes:

(3-1)! * 2 ^ 1
________________   =  2*2 / 1  = 4
(1! * 1!)