4 min read

Heuristic algorithm for an upper bound on the travelling salesmen problem 1) Start with a finite set of 3 or more vertices, each pair joined by a weighted edge. 2) Choose any vertex and find a vertex joined to it by an edge of least weight. 3) Find the vertex which is joined to either of the two vertices identified in step (2) by an edge of least weight. Draw these three vertices and the three edges joining them to form a cycle. 4) Find a vertex, not currently drawn, joined by an edge of least weight to any of the vertices already drawn. Label the new vertex vn and the existing vertex to which it is joined by the edge of least weight as vk. Label the two vertices which are joined to vk in the existing cycle as v_k-1 and v_{k 1}. Denote the weight of an edge v_pv_q by w(v_pv_q). If w(v_nv_k-1) – w(v_kv_k-1) < w(v_nv_{k 1}) – w(v_kv_{k 1}) then replace the edge v_kv_k-1 in the existing cycle with the edge vnvk-1 otherwise replace the edge v_kv_{k 1} in the existing cycle with the edge v_nv_{k 1}. See sketch below. 5) Repeat step 4 until all vertices are joined by a cycle, then stop. The cycle of obtained is an upper bound for the solution to the travelling salesmen problem.

2 min read

VERTEX COVERING A subset W of V is called a vertex covering or a vertex cover of G if every edge in G is incident on at least one vertex in W. Trivial vertex covering: A vertex cover of a graph is a subgraph of the graph, V it self is a vetex covering of G. This is known as the trivial vertex covering. Minimal vertex covering: A vertex covering W of G is called a minimal vertex covering if no proper subset of W is a vertex covering of G.

2 min read

Introduction: Cayley’s (1857) classic paper, a great deal of work has been done on enumeration (also called counting) of different types of graphs, and the results have been applied in solving some practical problems. The Pioneers is graphical enumeration theory were Cayley, Redfield and Pólya. Graphical enumeration methods in current use were anticipated in the unique paper by Redfield pubished in 1927 Enumerative techniques will be developed and used for counting certain types of graphs. A thorough exposition of Pólya’s counting theorem, the most powerful tool in graph enumeration. Types of Enumeration

3 min read

ROOTED LABELED TREES: In a rooted graph one vertex is marked as the root. For each of the n^{n – 2} labeled trees we have n rooted labeled trees, because any of the n vertices can be made a root. Therefore, the number of different rooted labeled trees with n vertices is n^{n – 1}. ENUMERATION OF GRAPHS: To obtain the polynomial gP(x) which enumerates graphs with a given number P of points. Let gpq be the number of (p, q) graphs and let all graphs with 4 points ; g4(x) = 1 x 2x² 3x³ 2x⁴ x⁵ x⁶. ENUMERATION OF TREES: To find the number of trees it is necessary to start by counting rooted trees. A rooted tree has one point, its root, distinguished from the others. Let TP be the number of rooted trees with P points.

2 min read

EQUIVALENCE CLASSES OF FUNCTIONS: Consider two sets D and R, with the number of elements | D | and | R | respectively. Let f be a mapping or function which maps each element d from doamin D to a unique image f(d) in range R. Since each of the | D | elements can be mapped into any of | R | elements, the number of different functions from D to R is | R || D |. Let there be a permutation group P on the elements of set D. Then define two mappings f1 and f2 as P-equivalent if there is some permutation π in P such that for every d in D we have f₁(d) = f₂[π(d)] ...(1) The relationship defined by (1) is an equivalence relation can be shown as follows :

2 min read

CONDENSATION: The condensation Gc of a digraph G is a digraph in which each strongly connected fragment is replaced by a vertex and all directed edges from one strongly connected component to another are replaced by a single directed edge. The condensation of the digraph G in Fig. 8.10 is shown in Fig. 8.11. Observations : (i) The condensation of a strongly connected digraph is simply a vertex. (ii) The condensation of a digraph has no directed circuit.

1 min read

CONNECTED DIGRAPHS Strongly Connected: A digraph G is said to be strongly connected if there is atleast one directed path from every vertex to every other vertex. Weakly Connected: A digraph G is said to be weakly connected if its corresponding undirected graph is connected but G is not strongly connected.

1 min read

ORIENTATION OF A GRAPH: Given a graph G, if there is a digraph D such that G is the underlying graph of D then D is called an orientation of G. The digraphs in Fig. 8.1(b) and Fig. 8.1(c) are two different orientations of the graph in Fig. 8.1(d). UNDERLYING GRAPH If D is a digraph, the graph obtained from D by ‘removing the arrows’ from the directed edges is called the underlying graph of D. This graph is also called the undirected graph corresponding to D. The underlying graph of the digraph in Fig. 8.1(b) is shown in Fig. 8.1(d). The graph in Fig. 8.1(d) is the underlying graph of the digraph shown in Fig. 8.1(c).

6 min read

TRANSVERSAL THEORY Transversal: If E is a non empty finite set, and if F = (S1, ..... Sm) is a family of (not necessarily distinct) nonempty subsets of E, then a transversal of F is a set of m distinct elements of E, one chosen from each set Si. Suppose that E = {1, 2, 3, 4, 5, 6} and Let S1 = S2 = {1, 2}, S3 = S4 = {2, 4}, S5 = {1, 4, 5, 6} Then it is impossible to find five distinct elements of E, one from each subset Si ; In otherwords, the family F = (S1, ....., S5) has no transversal. The subfamily F′ = (S1, S2, S3, S4, S5) has a transversal. For example, {1, 2, 3, 4, 5}. Partial transversal: A transversal of a subfamily of F a partial transversal of F. For example, {1, 2, 3, 4}, here F has several partial transversal, such as, {1, 2, 3, 6}, {2, 3, 6}, {1, 5}, and φ. We note that any subset of a partial transversal is a partial transversal.

4 min read

GROUP DEFINITION: The non-empty set A together with a binary operation, denoted by the just a position α1α2 for α1, α2 in A, constitutes a group whenever the following four axioms are satisfied Axiom (i) (closure) : For all α1, α2 in A, α1α2 is also an element of A. Axiom (ii) (associativity) : For all α1, α2, α3 in A, α1(α2α3) = (α1α2) α3 Axiom (iii) (identity) : There is an element i in A such that iα = αi = α for all α in A Axiom (iv) (inversion) : If axiom (iii) holds, then for each α in A, there is an element denoted α^{– 1} such that αα^{– 1} = α^{– 1}α = i. PERMUTATION: A one-one mapping from a finite set onto itself is called a permutation. PERMUTATION GROUP: The usual composition of mappings provides a binary operation for permutations on the same set. Whenever a collection of permutations is closed with respect to this composition, Axioms (ii), (iii) and (iv) are automatically satisfied and it is called a permutation group.

2 min read

PARTITIONS: The degrees d1, ..... dP of the points of a graph form a sequence of non-negative integers, whose sum is of course 2q. In number theory, to define a partition of a positive integer n as a list or unordered sequence of positive integers whose sum is n. For example, 4 has five partitions 4, 3 1, 2 2, 2 1 1, 1 1 1 1. The degrees of a graph with no isolated points determine such a partition of 2q. The partition of a graph is the partition of 2q as the sum of the degrees of the points 2q = Σdi. A partition Σdi of n into P parts is graphical if there is a graph G whose points have degree di. If such a partition is graphical then certainly every di ≤ P – 1 and n is even.

1 min read

ARBORESCENCE: A digraph G is said to be an arborescence if (i) G contains no circuit, neither directed nor semi circuit. (ii) In G there is precisely one vertex v of zero in-degree. This vertex v is called the root of the arborescence. An arborescence is shown in Fig. 8.13 below.

2 min read

COVERINGS: A point and a line are said to cover each other if they are incident. A set of points which covers all the lines of a graph G is called a point cover for G, while a set of lines which covers all the points is a line cover. Point covering number and line covering number The smallest number of points in any point cover for G is called its point covering number and is denoted by α0 (G) or α0. Similarly α1 (G) or α1 is the smallest number of lines in any line cover of G and is called its line covering number. For example. α0 (KP) = P – 1 and α (KP) = [(P 1)/2]. A point cover or line cover is called minimum if it contains α0 (respectively α1) dements.

1 min read

CENTROID: In a tree T, at any vertex v of degree d, there are d subtrees with only vertex v in common. The weight of each subtree at v is defined as the number of branches in the subtree. Then the weight of the vertex v is defined as the weight of the heaviest of the subtrees at v. A vertex with the smallest weight in the entire tree T is called a centroid of T. Every tree has either one centroid or two centroids. If a tree has two centroids, the centroids are adjacent. In Fig. 6.6 below, a tree with centroid, called a centroidal tree, and a tree with two centroids, called a bicentroidal tree. The centroids are shown enclosed in circles, and the numbers next to the vertices are the weights.

2 min read

TYPES OF DIGRAPHS Simple Digraphs: A digraphs that has no self-loop or parallel edges is called a simple digraph. The digraph shown in Fig. 8.3(a) is simple, but its underlying graph shown in Fig. 8.3(b) is not simple. A Symmetric Digraphs: Digraphs that have atmost one directed edge between a pair of vertices, but are allowed to have self-loops, are called asymmetric or antisymmetric digraph. For example, the digraph in Fig. 8.4(a), is asymmetric. The digraph in Fig. 8.4(b) is neither symmetric nor asymmetric. The digraph in Fig. 8.4(b) is simple and asymmetric. The digraph in Fig. 8.4(b) is simple but not asymmetric.

1 min read

SEMI-WALK, SEMI-PATH, SEMI-CIRCUIT Semi-Walk: A semi-walk in a digraph D is a walk in the underlying graph of D, but is not a directed walk in D. A walk in D can mean either a directed walk or a semi-walk in D. Semi-path: A semi-path in a digraph D is a path in the underlying graph of D, but is not a directed path in D. A path in D can mean either a directed path or a semi-path in D.

1 min read

EULER DIGRAPHS In a digraph G a closed directed walk (i.e., a directed walk that starts and ends at the same vertex) which transverses every edge of G exactly once is called a directed Euler line. A graph containing a directed Euler line is called an Euler digraph. For example, the graph in Fig. 8.15, is an Euler digraph, in which the walk a b c d e f is an Euler line.

2 min read

ARBORICITY: Any graph G can be expressed as a sum of spanning forests, simply by letting each factor contain only one of the q lines of G. A natural problem is to determine the minimum number of line-disjoint spanning forests into which G can be decomposed. This number is called the arboricity of G and is denoted by r (G). For example. r (K4) = 2 and r (K5) = 3, minimal decompositions of those graphs into spanning forests are shown in Figure 7.6 below.

3 min read

SYMMETRIC GRAPHS: Two points u and v of the graph G are similar if for some automorphism α of G, α(u) = v. A fixed point is not similar to any other point. Two lines x1 = u1v1 and x2 = u2v2 are called similar if there is an automorphism α of G such that α({u1, v1}) = {u2, u2}. A graph is point-symmetric of every pair of points are similar, it is line-symmetric if every pair of lines are similar, and it is symmetric if it is both point-symmetric and line-symmetric. HIGHLY SYMMETRIC GRAPHS: A graph G is n-transitive, n ≥ 1, if it has an n-route and if there is always an automorphism of G sending each n-route onto any other n-route. Obviously a cycle of any length is n-transitive for all n, and a path of length n is n-transitive. We note that not every line-symmetric graph is 1-transitive. Theorem. The line-group and the point-group of a graph G are isomorphism if and only if G has atmost one isolated point and K2 is not a component of G. Proof. Let α′ be the permutation in Γ1(G) which is induced by the permutation α in Γ(G). By the definition of multiplication in Γ1(G), we have

4 min read

Introduction to Matroid: A matroids M consists of a non-empty finite set E and a non-empty collection B of subsets of E, called bases satisfying the following properties B(i) no base properly contains another base B(ii) if B1 and B2 are bases and if e is any element of B1 then there is an element f of B2 such that (B1 – {e}) ∪ {f} is also a base. Note : Any two bases of a matroid M have the same number of elements, this number is called the rank of M.

3 min read

CRITICAL POINTS AND CRITICAL LINES: If H is a subgraph of G, then α0 (H) ≤ α0 (G). In particular this inequality holds when H = G – v or H = G – x for any point v or line x. If α0 (G – v) < α0 (G) then v is called a critical point, if α0 (G – x) < α0 (G) then x is a critical line of G. If v and x are critical, it follows that α0 (G – v) = α0 (G – x) = α0 – 1. LINE-CORE AND POINT-CORE: The line-core C1 (G) of a graph G is the subgraph of G induced by the union of all independent sets Y of lines (if any) such that |Y| = α0 (G).

1 min read

Digraph : A digraph D consists of a finite set V of points and a collection of ordered pairs of distinct points. Any such pair (u, v) is called an arc or directed line and will usually be denoted uv. The arc uv goes from u to v and is incident with u and v. We say that u is adjacent to v and v is adjacent from u. In otherwords, A directed graph or a digraph G consists of a set of vertices V = {v1, v2, .....}, a set of edge E = {e1, e2, .....} and a mapping ψ that maps every edge onto some ordered pair of vertices (vi, vj). For example, Fig. 8.1(a) below shows a digraph with five vertices and ten edges.

2 min read

PERMUTATION GROUP: A collection of m permutations P = {π1, π2, ....., πm} acting on a set A = {a1, a2, ....., ak} forms a group under composition, if the four postulates of a group, that is, closure, associativity, identity, and inverse are satisfied. Such a group is called a permutation group. The number of permutations m in a permutation group is called its order, and the number of elements in the object set on which the permutations are acting is called the degree of the permutation group. For example, the set of four permutations {(a) (b) (c) (d), (a c) (b d), (a b c d), (a d c b)} acting on the object set {a, b, c, d} forms a permutaion group. CYCLE INDEX OF A PERMUTATION GROUP: For a permutation group P, of order m, if we add the cycle structures of all m permutations in P and divide the sum by m, we get an expression called the cycle index Z(P) of P. For example, the cycle index of S3, the full symmetric group of degree three, The cycle index of the permutation group is We have six permutations of type (2, 1, 0, 0) on the object set {a, b, c, d} : (a) (b) (c d), (a) (c) (b d), (a) (d) (b c), (b) (c) (a d), (b) (d) (a c), (c) (d) (a b). The cycle index of S4 : Z(S4) =

2 min read

COUNTING UNLABELED TREES The problem of enumeration of unlabeled trees is more involved and requires familiarity with the concepts of generating functions and partitions. ROOTED UNLABELED TREES: Let u_n be the number of unlabeled, rooted trees of n vertices and let un(m) be the number of those rooted trees of n vertices in which the degree of the root is exactly m. Then

2 min read

Algorithm for a lower bound on the travelling salesmen problem An algorithm which produces a lower bound for the travelling salesman problem is as follows. 1 Start with a finite set of vertices, each pair joined by a weighted edge. 2 Choose a vertex vs and remove it from the graph. 3 Find a minimum spanning tree connecting the remaining vertices and calculate its total weight w. 4 Find the two smallest weights, w1 and w2, of the edges incident with vs Then w w1 w2 is a lower bound for the solution to the travelling salesmen problem. For instance, remove vertex a from the graph G. The resulting graph G1 has a minimum spanning tree G2 so the lower bound graph is G3 with total weight 22.

3 min read

Kuratowski’s Theorem: A graph is planar if and only if it has no subgraph homeomorphic to K5 or K_{3, 3}. Proof. Let H be the inner piece guaranteeed by lemma (2) which is both u0 – v0 separating and u1 – v1 separating. In addition, let w0, w0′, w1 and w1′ be vertices at which H meets Z(u0, v0), Z(v0, u0), Z(u1, v1) and Z(v1, u1) respectively. There are now four cases to consider, depending on the relative position on Z of these four vertices.

6 min read

Types of Matroid Bipartite matroid: A bipartite matroid be a matroid, in which each cycle has an even number of elements. Eulerian matroid: A matroid on a set E to be an Eulerian matroid if E can be written as a union of disjoint cycles.

1 min read

COUNTING LABELED TREES Expression can be used to obtain the number of simple labeled graphs of n vertices and n – 1 edges. Some of these are going to be trees and others will be unconnected graphs with circuits. For example, In Figure 6.2 below are all the 16 labeled trees with 4 points. The labels on these trees are understood to be as in the first and last trees shown. We note that among these 16 labeled trees, 12 are isomorphic to the path P4 and 4 to k1, 3. The order of Γ(P4) is 2 and that of Γ(k1, 3) is 6. We observe that since P = 4 here, we have

1 min read

LABELED GRAPHS: All of the labeled graphs with three points are shown in Figure 6.1 below. We see that the 4 different graphs with 3 points become 8 different labeled graphs. To obtain the number of labeled graphs with P points, we need only observe that each of the possible lines is either present or absent.

1 min read

Introduction: A vertex v of a graph G is a cut vertex or an articulation vertex of G if the graph G−v consists of a greater number of components than G. Example. v is a cut vertex of the graph below: (Note! Generally, the only vertex of a trivial graph is not a cut vertex, neither is an isolated vertex.) A graph is separable if it is not connected or if there exists at least one cut vertex in the graph. Otherwise, the graph is nonseparable.

2 min read

Kruskal’s algorithm: Start with a finite set of vertices, each pair joined by a weighted edge. 1 (List all the weights in ascending order) 2 (Draw the vertices and weighted edge corresponding to the first weight in the list provided that, in so doing, no cycle is formed. Delete the weight from the list) 3) Repeat step 2 until all vertices are connected, then stop. The weighted graph obtained is a minimum connector, and the sum of weights on its edges is the total weight of the minimum connector. To construct a minimum spanning tree for the graph of figure 7.1 we proceed thus. The weights are so the steps of Kruskal’s algorithm will give the following :- choose ae, choose ac, reject ce (would form cycle acea), choose bc, reject ab (would form cycle acba), reject be (would form cycle acbea), choose de. All vertices now connected. The total weight is 18

4 min read

NULLITY OF A MATRIX: If Q is an n by n matrix then QX = 0 has a non trial solution X ≠ 0 if and only if Q is singular, that is ; det Q = 0. The set of all vectors X that satisfy QX = 0 forms a vector space called the null space of matrix Q. The rank of the null space is called the nullity of Q. Rank of Q nullity of Q = n When Q is not square but a k by n matrix, k < n. Theorem . (Binet-Cauchy Theorem) If Q and R are k by m and m × k matrices respectively with k < m then the determinant of the product det (QR) = the sum of the products of corresponding major determinants of Q and R. Proof. To evaluate det (QR), let us devise and multiply two (m k) by (m k) partitioned matrices

2 min read

PERMUTATION: On a finite set A of some objects, a permutation π is a one-to-one mapping from A onto intself. For example, consider a set {a, b, c, d}. A permutation π₁ = takes a into b, b into d, c into c, and d into a. Alternating, we could write π1(a) = b, π1(b) = d, π1(c) = c, π1(d) = a. The number of elements in the object set on which a permutation acts is called the degree of the permutation. For example, the permutation π₁ = is represented diagrammatically by Figure 6.7 below : Permutation can be written as (a b d) (c). The number of edges in a permutation cycle is called the length of the cycle in the permutation.

1 min read

Cut Set: A cut set of a connected graph G is a set S of edges with the following properties The removal of all edges in S disconnects G. The removal of some (but not all) of edges in S does not disconnects G.

3 min read

PARALLEL EDGES: Two (directed) edges e and e′ of a digraph D are said to be parallel if e and e′ have the same initial vertex and the same terminal vertex. In the digraph in Fig. 8.2 the edges e6 and e7 are parallel edges whereas the edges e1 and e9 are not parallel. e1 and e6 are parallel edges in the underlying graph. INCIDENCE: In a digraph every edge has two end vertices, one vertex from which it begins and the other vertex at which it terminates. If an edge e begins at a vertex u and terminates at a vertex v, we say that e is incident out of u and incident into v. Here, u is called the initial vertex and v is called the terminal vertex of e. For example, in the digraph in Fig. 8.2, the edge e1 is incident out of the vertex v1 and incident into the vertex v2, v1 is the initial vertex and v2 is the terminal vertex of the edge e1. For a self-loop in a digraph, the initial and terminal vertices are one and the same. In Fig. 8.2 the edge e3 is a self-loop with v3 as the initial and terminal vertex.

2 min read

HAND SHAKING DILEMMA: In a digraph D, the sum of the out-degree of all vertices is equal to the sum of the in-degrees of all vertices, each sum being equal to the numbe of edges in D. For example, the digraph in Fig. 8.1, we note that the digraphs has 6 vertices and 9 edges and that the sums of the out-degrees and in-degrees of its vertices are DIRECTED WALK, DIRECTED PATH, DIRECTED CIRCUIT

3 min read

Introduction: A graph G consists of a set of objects V = {v1, v2, v3, ......} called vertices (also called points or nodes) and other set E = {e1, e2, e3, .......} whose elements are called edges (also called lines or arcs). The set V(G) is called the vertex set of G and E(G) is the edge set. Usually the graph is denoted as G = (V, E) Let G be a graph and {u, v} an edge of G. Since {u, v} is 2-element set, we may write {v, u} instead of {u, v}. It is often more convenient to represent this edge by uv or vu. If e = uv is an edge of a graph G, then we say that u and v are adjacent in G and that e joins u and v. (We may also say that each that of u and v is adjacent to or with the other). For example : A graph G is defined by the sets V(G) = {u, v, w, x, y, z} and E(G) = {uv, uw, wx, xy, xz}.

2 min read

Directed graph: A directed graph or digraph G consists of a set V of vertices and a set E of edges such that e ∈ E is associated with an ordered pair of vertices. In other words, if each edge of the graph G has a direction then the graph is called directed graph. In the diagram of directed graph, each edge e = (u, v) is represented by an arrow or directed curve from initial point u of e to the terminal point v. Figure 1(a) is an example of a directed graph.

1 min read

OUTER PLANAR GRAPHS: A planar graph is said to be outer planar if i(G) = 0. For example, cycles, trees, K4 – x. (a) Maximal outer planar graph: An outer planar graph G is maximal outer planar if no edge can be added without losing outer planarity. For example,

1 min read

REGION: A plane representation of a graph divides the plane into regions (also called windows, faces, or meshes) as shown in figure below. A region is characterized by the set of edges (or the set of vertices) forming its boundary. Note that a region is not defined in a non-planar graph or even in a planar graph not embedded in a plane. For example, the geometric graph in figure below does not have regions.

1 min read

SUBDIVISION GRAPHS: A subdivision of a graph is a graph obtained by inserting vertices (of degree 2) into the edges of G. For the graph G of the figure below, the graph H is a subdivision of G, while F is not a subdivision of G. INNER VERTEX SET: A set of vertices of a planar graph G is called an inner vertex set I(G) of G. If G can be drawn on the plane in such a way that each vertex of I(G) lies only on the interior region and I(G) contains the minimum possible vertices of G. The number of vertices i(G) of I(G) is said to be the inner vertex number if they lie in interior region of G.

2 min read

BASIC TERMINOLOGIES Loop : An edge of a graph that joins a node to itself is called loop or self loop. i.e., a loop is an edge (vi, vj) where vi = vf. Multigraph: In a multigraph no loops are allowed but more than one edge can join two vertices, these edges are called multiple edges or parallel edges and a graph is called multigraph.

2 min read

TYPES OF GRAPHS: Some important types of graph are introduced here. Null graph: A graph which contains only isolated node, is called a null graph. i.e., the set of edges in a null graph is empty. Null graph is denoted on n vertices by Nn. N4 is shown in Figure (13), Note that each vertex of a null graph is isolated.

3 min read

Handshaking Lemma: The sum of the degrees of the vertices in a graph is twice the number of edges. If G = (v, E) be an undirected graph with e edges. Then i.e., the sum of degrees of the vertices is an undirected graph is even. Proof : Since the degree of a vertex is the number of edges incident with that vertex, the sum of the degree counts the total number of times an edge is incident with a vertex. Since every edge is incident with exactly two vertices, each edge gets counted twice, once at each end. Thus the sum of the degrees equal twice the number of edges.

2 min read

Introduction: A graph is a non-empty finite set V of elements called vertices together with a possibly empty set E of pairs of vertices called edges. Degree of a Vertices: The number of edges incident on a vertex vi with self-loops counted twice (is called the degree of a vertex vi and is denoted by degG(vi) or deg vi or d(vi). The degrees of vertices in the graph G and H are shown in Figure 4(a) and 4(b).

2 min read

N-cube: The N-cube denoted by Qn, is the graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position. The graphs Q1, Q2, Q3 are displayed in Figure 18. Thus Qn has 2n vertices and n . 2n – 1 edges, and is regular of degree n. Problem 1.. Determine whether the graphs shown is a simple graph, a multigraph, a pseudograph.

4 min read

DIRAC’S THEOREM: Let G be a graph of order p ≥ 3. If deg v ≥ p/2 for every vertex v of G, then G is hamiltonian. Proof. If p = 3, then the condition on G implies that G ≅ k3 and hence G is hamiltonian. We may assume, therefore, that p ≥ 4. Let P : v1, v2, ....... vn be a longest path in G (see Figure). Then every neighbour of v1 and every neighbour of vn is on P. Otherwise, there would be a longer path than P. Consequently, n ≥ 1 p/2 . There must be some vertex vi where 2 ≤ i ≤ n, such that v1 is adjacent to vi and vn is adjacent to vi – 1. If this were not the case, then whenever v1 is adjacent to a vertex vi, the vertex vn is not adjacent to vi – 1. Since atleast p/2 of p – 1 vertices different from vn are not adjacent to vn. Hence, deg vn ≤ (P – 1) – p/2 < p/2 , which contradicts the fact that deg vn ≥ p/2 .

2 min read

THE PROBLEM OF RAMSEY : Prove that at any party with six people, there are three mutual acquaintances or three mutual nonacquaintances. Solution. This situation may be represented by a graph G with six points standing for people, in which adjacency indicates acquaintance. Then the problem is to demonstrate that G has three mutually adjacent points or three mutually nonadjacent ones. The complement G of a graph G also has V(G) as its point set, but two points are adjacent in G if and only if they are not adjacent in G. In Figure 28, G has no triangles, while G consists of exactly two triangles.

2 min read

Scheduling Final Exams : How can the final exams at a university be scheduled so that no student has two exams at the same time ? Solution. This scheduling problem can be solved using a graph model, with vertices representing courses and with an edge between two vertices if there is a common student in the courses they represent. Each time slot for a final exam is represented by a different colour. A scheduling of the exams corresponds to a colouring of the associated graph. For instance, suppose there are seven finals to be scheduled. Suppose the courses are numbered 1 through 7. Suppose that the following pairs of courses have common students : 1 and 2, 1 and 3, 1 and 4, 1 and 7, 2 and 3, 2 and 4, 2 and 5, 2 and 7, 3 and 4, 3 and 6, 3 and 7, 4 and 5, 4 and 6, 5 and 6, 5 and 7, and 6 and 7. In Figure 2.79, the graph associated with this set of classes is shown. A scheduling consists of a colouring of this graph. Since the chromatic number of this graph is 4, four times slots are needed. A colouring of the graph using four colours and the associated schedule are shown in Figure 2.80.

3 min read

The Five colour theorem: Every planar graph is 5-colorable. Proof. We proceed by induction on the number P of points. For any planar graph having P ≤ 5 points, the result follows trivially since the graph is P-colorable. As the inductive hypothesis we assume that all planar graphs with P points, P ≥ 5, are 5-colourable. Let G be a plane graph with P 1 vertices, G contains a vertex v of degree 5 or less. By hypothesis, the plane graph G – v is 5-colourable. Consider an assignment of colours to the vertices of G – v so that a 5-colouring results, when the colours are denoted by Ci, 1 ≤ i ≤ 5. Certainly, if some colour, say Cj, is not used in the colouring of the vertices adjacent with v, then by assigning the colour Cj to v, a 5-colouring of G results. This leaves only the case to consider in which deg v = 5 and five colours are used for the vertices of G adjacent with v. Permute the colours, if necessary, so that the vertices coloured C1, C2, C3, C4 and C5 are arranged cyclically about v, Now label the vertex adjacent with v and coloured Ci by vi, 1 ≤ i ≤ 5 (see Figure 2.100) Let G13 denote the subgraph of G – v induced by those vertices coloured C1 or C3. If v1 and v3 belong to different components of G13, then a 5-coloring of G – v may be accomplished by interchanging the colors of the vertices in the component of G13 containing v1. In this 5-coloring however, no vertex adjacent with v is colored C1, so by coloring v with the color C1, a 5-coloring of G results.

4 min read

GRAPH COLORING Coloring problem Suppose that you are given a graph G with n vertices and are asked to paint its vertices such that no two adjacent vertices have the same color. What is the minimum number of colors that you would require. This constitutes a coloring problem. Partitioning problem Having painted the vertices, you can group them into different sets—one set consisting of all red vertices, another of blue, and so forth. This is a partitioning problem. For example, finding a spanning tree in a connected graph is equivalent to partitioning the edges into two sets—one set consisting of the edges included in the spanning tree, and the other consisting of the remaining edges. Identification of a Hamiltonian circuit (if it exists) is another partitioning of set of edges in a given graph.

4 min read

EULER’S FORMULA: The basic results about planar graph known as Euler’s formula is the basic computational tools for planar graph. Theorem . Euler’s Formula: If a connected planar graph G has n vertices, e edges and r region, then n – e r = 2. Proof. We prove the theorem by induction on e, number of edges of G. Basis of induction : If e = 0 then G must have just one vertex. i.e., n = 1 and one infinite region, i.e., r = 1 Then n – e r = 1 – 0 1 = 2. If e = 1 (though it is not necessary), then the number of vertices of G is either 1 or 2, the first possibility of occurring when the edge is a loop. These two possibilities give rise to two regions and one region respectively, as shown in Figure (2.17) below.

2 min read

OPERATIONS OF GRAPHS Union: Given two graphs G1 and G2, their union will be a graph such that V(G1 ∪ G2) = V(G1) ∪ V(G2) and E(G1 ∪ G2) = E(G1) ∪ E(G2)

2 min read

FLEURY’S ALGORITHM: Let G = (V, E) be a connected graph with each vertex of even degree. Step 1. Select an edge e1 that is not a bridge in G. Let its vertices be v1, v2. Let π be specified by Vπ : v1, v2 and Eπ : e1. Remove e1 from E and v1 and v2 from V to create G1. Step 2. Suppose that Vπ : v1, v2, ...... vk and Eπ : e1, e2, .......ek – 1 have been constructed so far, and that all of these edges and vertices have been removed from v and E to form Gk – 1. Since vk has even degree, and ek – 1 ends there, there must be an edge ek in Gk – 1 that also has vk as a vertex. If there is more than one such edge, select one that is not a bridge for Gk – 1. Denote the vertex of ek other than vk by vk 1, and extend Vπ and Eπ to Vπ : v1, v2, ......, vk, vk 1 and Eπ : e1, e2, ......, ek – 1, ek.

2 min read

GRAPHS ISOMORPHISM: Let G1 = (v1, E1) and G2 = (v2, E2) be two graphs. A function f : v1 → v1 is called a graphs isomorphism if (i) f is one-to-one and onto. (ii) for all a, b ∈ v1, {a, b} ∈ E1 if and only if {f(a), f(b)} ∈ E2 when such a function exists, G1 and G2 are called isomorphic graphs and is written as G1 ≅ G2. In other words, two graphs G1 and G2 are said to be isomorphic to each other if there is a oneto- one correspondence between their vertices and between edges such that incidence relationship is preserve. Written as G1 ≅ G2 or G1 = G2. The necessary conditions for two graphs to be isomorphic are 1. Both must have the same number of vertices 2. Both must have the same number of edges 3. Both must have equal number of vertices with the same degree. 4. They must have the same degree sequence and same cycle vector (c1, ......, cn), where ci is the number of cycles of length i.

4 min read

SUBGRAPH: A subgraph of G is a graph having all of its vertices and edges in G. If G1 is a subgraph of G, then G is a super graph of G1. In other words. If G and H are two graphs with vertex sets V(H), V(G) and edge sets E(H) and E(G) respectively such that V(H) ⊆ V(G) and E(H) ⊆ E(G) then we call H as a subgraph of G or G as a supergraph of H.

3 min read

TRAVELING-SALESMAN PROBLEM: The traveling-salesman problem, stated as follows : ‘‘A salesman is required to visit a number of cities during a trip. Given the distances between the cities, in what order should he travel so as to visit every city precisely once and return home, with the minimum mileage traveled ?’’Representing the cities by vertices and the roads between them by edges. We get a graph. In this graph, with every edge ei there is associated a real number (the distance in miles, say), w(ei). Such a graph is called a weighted graph ; w(ei) being the weight of edge ei. (i.e., A traveling salesman wants to visit each of n cities exactly once and return to his starting point) if each of the cities has a road to very other city, we have a complete weighted grap. For example, suppose that the salesman wants to visit five cities, namely, A, B, C, D and E (see Figure). In which order should he visit these cities to travel the minimum total distance ? To solve this problem we can assume the salesman starts in A (since this must be part of the circuit) and examine all possible ways for him to visit the other four cities and then return to A (starting elsewhere will produce the same circuits). There are a total of 24 such circuits, but since we travel the same distance when we travel a circuit in reverse order, we need only consider 12 different circuits to find the minimum total distance he must travel. We list these 12 different circuits and the total distance traveled for each circuit. As can be seen from the list, the minimum total distance of 458 miles is traveled using the circuit A – B – E – D – C – A (or its reverse).

2 min read

PLANAR GRAPHS: A graph G is said to be planar if there exists some geometric representation of G which can be drawn on a plane such that no two of its edges intersect. The points of intersection are called crossovers. A graph that cannot be drawn on a plane without a crossover between its edges crossing is called a plane graph. The graphs shown in Figure 2.3(a) and are planar graphs. A drawing of a geometric representation of a graph on any surface such that no edges intersect is called embedding.

4 min read

EULERIAN GRAPHS Euler path: A path in a graph G is called Euler path if it includes every edges exactly once. Since the path contains every edge exactly once, it is also called Euler trail. Euler circuit: An Euler path that is circuit is called Euler circuit. A graph which has a Eulerian circuit is called an Eulerian graph.

2 min read

PROBLEM OF SEATING ARRANGEMENT : Nine members of a club meet every day for a dinner. They sit in a round table for a dinner, but no two members who sat together will sit together in future. How long is this possible ? Solution. The seating arrangement can be represented as follows :

3 min read

CONNECTED AND DISCONNECTED GRAPHS: A graph G is said to be a connected if every pair of vertices in G are connected. Otherwise, G is called a disconnected graph. Two vertices in G are said to be connected if there is at least one path from one vertex to the other. In other words, a graph G is said to be connected if there is at least one path between every two vertices in G and disconnected if G has at least one pair of vertices between which there is no path. A graph is connected if we can reach any vertex from any other vertex by travelling along the edges and disconnected otherwise. For example, the graphs in Figure 30(a, b, c, d, e) are connected whereas the graphs in Figure 31(a, b, c) are disconnected.

1 min read

Problem 1. Use adjacency matrix to represent the graphs shown in Figure below Solution. We order the vertices in Figure (1)(a) as v1, v2, v3 and v4. Since there are four vertices, the adjacency matrix representing the graph will be a square matrix of order four. The required adjacency matrix A is

2 min read

HAMILTONIAN GRAPHS: Hamiltonian graphs are named after Sir William Hamilton, an Irish mathematician who introduced the problems of finding a circuit in which all vertices of a graph appear exactly once. Note that an Eulerian circuit traverses every edge exactly once, but may repeat vertices, while a Hamiltonian circuit visists each vertex exactly once but may repeat edges. While there is a criterion for determining whether or not a graph contains an Eulerian circuit, a similar criterion does not exist for Hamiltonian ciruits. In the following figures, hamiltonian path and cycles are shown :

2 min read

Problem . Find the chromatic polynomial and chromatic number for the graph K_{3, 3}. Solution. Chromatic polynomial for K3, 3 is given by λ(λ – 1)5. Thus chromatic number of this graph is 2. Since λ(λ – 1)5 > 0 first when λ = 2. Here, only two distinct colours are required to colour K3, 3. The vertices a, b and c may have one colours, as they are not adjacent. Similarly, vertices d, e and f can be coloured in proper way using one colour. But a vertex from {a, b, c} and a vertex from {d, e, f} both cannot have the same colour. In fact every chromatic number of any bipartite graph is always 2.

1 min read

HOMEOMORPHIC GRAPHS: Two graphs are said to be homeomorphic if and only if each can be obtained from the same graph by adding vertices (necessarily of degree 2) to edges. The graphs G1 and G2 in Figure (2.6) are homeomorphic since both are obtainable from the graph G in that figure by adding a vertex to one of its edges. In Figure 2.7, we show two homeomorphic graphs, each obtained from K5 by adding vertices to edges of K5 (In each case, the vertices of K5 are shown with solid dots).

4 min read

Frequency assignments: Television channels 2 through 13 are assigned to stations in New Delhi so that no two stations within 150 miles can operate on the same channel. How can the assignment of channels be modeled by graph colouring ? Solution. Construct a graph by assigning a vertex to each station. Two vertices are connected by an edge if they are located within 150 miles of each other. An assignment of channels corresponds to a colouring of the graph. Where each colour represents a different channel. Index registers: In efficient compilers the execution of loops is speeded up when frequently used variables are stored temporarily in index registers in the central processing unit, instead of in regular memory. For a given loop, how many index registers are needed ? Solution. This problem can be addressed using a graph colouring model. To set up the model, let each vertex of a graph represent a variable in the loop. There is an edge between two vertices if the variables they represent must be stored in index registers at the same time during the execution of the loop. Thus, the chromatic number of the graph gives the number of index registers needed, since different registers must be assigned to variables when the vertices respresenting these variables are adjacent in the graph.

4 min read

WALKS, PATHS AND CIRCUITS Walk: A walk is defined as a finite alternative sequence of vertices and edges, of the form v_ie_j, v_i 1 e_j 1, v_i 2, ......., ekvm which begins and ends with vertices, such that (i) each edge in the sequence is incident on the vertices preceding and following it in the sequence. (ii) no edge appears more than once in the sequence, such a sequence is called a walk or a trial in G. For example, in the graph shown in Figure 34, the sequences v₂e₄v₆e₅v₄e₃v₃ and v₁e₈v₂e₄v₆e₆v₅e₇v₅ are walks.

2 min read

Decomposition theorem: If G = (V, E) is a connected graph and e = {a, b} ∈ E, then P(Ge, λ) = P(G, λ) P(Ge′, λ). Where Ge denotes the subgraph of G obtained by deleting e from G without removing vertices a and b. i.e., Ge = G – e and Ge′ is a second subgraph of G obtained from Ge′ by colouring the vertices a and b. Proof. Let e = {a, b}. The number of ways to properly color the vertices in Ge = G – e with (atmost) λ colours in P(Ge, λ). Those colourings where end points a and b of e have different colours are proper colourings of G. The colourings of Ge that are not proper colourigns of G occur when a and b have the same color. But each of these colourings corresponds with a proper colouring for Ge′. This partition of the P(Ge, λ) proper colourings of Ge into two disjoint subsets results in the equation P(Ge, λ) = P(G, λ) P(Ge′, λ)

2 min read

DETECTION OF PLANARITY OF A GRAPH : If a given graph G is planar or non planar is an important problem. We must have some simple and efficient criterion. We take the following simplifying steps : Elementary Reduction : Step 1 : Since a disconnected graph is planar if and only if each of its components is planar, we need consider only one component at a time. Also, a separable graph is planar if and only if each of its blocks is planar. Therefore, for the given arbitrary graph G, determine the set.

4 min read

We observe that K4* has four vertices and six edges. Also, every two vertices of K4* are joined by an edge. This means that K4* also represents the complete graph of four vertices. As such, K4 and K4* are isomorphic. In other words, K4 is a self-dual graph. Dual of a subgraph: Let G be a planar graph and G* be its geometric dual. Let e be an edge in G and e* be its dual in G*. Consider the subgraph G – e got by deleting e from G. Then, the geometric dual of G – e can be constructed as explained in the two possible cases. Case (1) : Suppose e is on a boundary common to two regions in G. Then the removal of e from G will merge these two regions into one. Then the two corresponding vertices in G* get merged into one, and the edge e* gets deleted from G*. Thus, in this case, the dual of G – e can be obtained from G* by deleting the edge e* and then fusing the two end vertices of e* in G* – e*.

2 min read

ORE’S THEOREM : If G is a group with p ≥ 3 vertices such that for all non adjacent vertices u and v, deg u deg v ≥ p, then G is hamiltonian. Proof. Let k denotes the number of vertices of G whose degree does not exceed n, where 1 ≤ n ≤ p/2 These k vertices induce a subgraph H which is complete, for if any two vertices of H were not adjacent, there would exist two non adjacent vertices, the sum of whose degree is less than p. This implies that k ≤ n 1. However k ≠ n 1, for otherwise each vertex of H is adjacent only two vertices of H, and if u ∈ V(H) and v ∈ V(G) – V(H), then deg u deg v ≤ n (p – n – 2) = p – 2, which is a contradiction.

1 min read

KURATOWSKI’S GRAPHS: For this we discuss two specific non-planar graphs, which are of fundamental importance, these are called Kuratowski’s graphs. The complete graph with 5 vertices is the first of the two graphs of Kuratowski. The second is a regular, connected graph with 6 vertices and 9 edges. Observations (i) Both are regular graphs (ii) Both are non-planar graphs (iii) Removal of one vertex or one edge makes the graph planar (iv) (Kuratowski’s) first graph is non-planar graph with smallest number of vertices and (Kuratowski’s) second graph is non-planar graph with smallest number of edges. Thus both are simplest non-planar graphs.

1 min read

KÖNIGSBERG’S BRIDGE PROBLEM There were two islands linked to each other to the bank of the Pregel river by seven bridges as shown above.

2 min read

BIPARTITE GRAPH: A graph G = (V, E) is bipartite if the vertex set V can be partitioned into two subsets (disjoint) V1 and V2 such that every edge in E connects a vertex in V1 and a vertex V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2). (V1, V2) is called a bipartition of G. Obviously, a bipartite graph can have no loop. Complete bipartite graph: The complete bipartite graph on m and n vertices, denoted Km, n is the graph, whose vertex set is partitioned into sets V1 with m vertices and V2 with n vertices in which there is an edge between each pair of vertices V1 and V6. Where V1 is in V1 and V2 is in V2. The complete bipartite graphs K_{2, 3}, K_{3, 3,} K_{3, 5} and K_{2, 6} are shown in Figure below. Note that Kr, s has r s vertices and rs edges.

1 min read

Introduction: An abstract graph G can be defined as G = (V, E, Ψ) where the set V consists of the five objects named a, b, c, d and e, that is, V = {a, b, c, d, e} and the set E consists of seven objects (none of which is in set V) named 1, 2, 3, 4, 5, 6 and 7, that is, E = {1, 2, 3, 4, 5, 6, 7} and the relationship between the two sets is defined by the mapping Ψ, which consists of combinatorial representation of the graph. Here, the symbol 1 → (a, c) says that object 1 from set E is mapped onto the (unordered) pair (a, c) of objects from set V.

2 min read

Three utility problem : There are three homes H1, H2 and H3 each to be connected to each of three utilities Water (W), Gas(G) and Electricity(E) by means of conduits. Is it possible to make such connections without any crossovers of the conduits with Utility Problem. Solution:

5 min read

Brooks’ Theorem: We are now prepared to present bounds for the chromatic number of a graph. We give here several upper bounds, beginning with the best known and most applicable. The bound (G) ≤ 1 Δ
(G) holds with equality for complete graphs and odd cycles. By choosing the vertex ordering more carefully, we can show that these are essentially the only such graphs. This implies, for example, that the Petersen graph is 3-colorable, without finding an explicit coloring. To avoid unimportant complications, we phrase the statement only for connected graphs. It extends to all graphs because the chromatic number of a graph is maximum chromatic number of its components. Many proofs are known; we present a modification of the proof by (Melnikov and Vizing 1969). For an alternative proof see (Lov´asz 1975). Theorem. (Brooks’ Theorem) If a connected graph G is neither an odd cycle nor a complete graph, then (G) ≤
Δ(G). Proof. If Δ
(G) ≤ 2, then G is either a path or a cycle. For a path G (other than K1 and K2), and for an even cycle G, (G) = 2 = Δ
(G). According to our assumption G is not an odd cycle. So let Δ(G) ≥ 3. The proof is by contradiction. Suppose the result is not true. Then there exists a minimal graph G of maximum degree
Δ(G) ≥ 3 such that G is not
-Δcolorable, but for any vertex v of G, G − v is
Δ(G − v)-colorable and therefore
Δ-colorable.

2 min read

Cut Matrix: If all the cuts of a nontrivial and loopless graph G = (V,E) are I1, . . . , It, then the cut matrix of G is a t × m matrix Q = (q_ij), where m is the number of edges in G and Example. For the graph

2 min read

Introduction Example: Chromatic number of the graph shown below

2 min read

Introduction: The chromatic number, (G), of a graph G is the minimum number of independent subsets that partition the vertex set of G. Any such minimum partition is called a chromatic partition of V (G). A vertex coloring of G is a map f : V (G) → C, where C is a set of distinct colors; it is proper if adjacent vertices of G receive distinct colors of C; that is, if uv ∈ E(G) then f(u) 6= f(v). Thus (G) is the minimum cardinality of C for which there exists a proper vertex coloring of G by colors of C. Clearly, in any proper vertex coloring of G, the vertices that receive the same color are independent. The vertices that receive a particular color make up a color class. Thus, in any chromatic partition of V (G), the parts of the partition constitute the color classes. This allows an equivalent way of defining the chromatic number. Definition . The chromatic number of a graph G is the minimum number of colors needed for a proper vertex coloring of G. If (G) = k, G is said to be k-chromatic. For example, the chromatic number of the graph in Figure 3.1 is 3.

2 min read

Circuit Matrix: We consider a loopless graph G = (V,E) which contains circuits. We enumerate the circuits of G: C1, . . . ,Cℓ. The circuit matrix of G is an ℓ × m matrix B = (b_ij) where (as usual, E = {e1, . . . , em}). The circuits in the digraph G are oriented, i.e. every circuit is given an arbitrary direction for the sake of defining the circuit matrix. After choosing the orientations, the circuit matrix of G is B = (b_ij) where

4 min read

Euler’s formula for planar graphs . If n, m and f denote respectively the number of vertices, edges and faces in a plane drawing of a connected plane graph G then n– m f = 2. In figure 6.2 we have n= 4, m = 6 and f= 4 satisfying Euler’s formula. Proof of Euler’s formula: A plane drawing of any connected planar graph G can be constructed by taking a spanning tree of G and adding edges to it,one at a time, until a plane drawing of G is obtained.

4 min read

Basic Principles for Calculating Chromatic Numbers: Although the chromatic number is one of the most studied parameters in graph theory, no formula exists for the chromatic number of an arbitrary graph. Thus, for the most part, one must be content with supplying bounds for the chromatic number of graphs. A few basic principles recur in many chromatic-number calculations. Now, we will try to find upper and lower bound to provide a direct approach to the chromatic number of a given graph. Upper bound: Show (G) ≤ k by exhibiting a proper k-coloring of G. Lower bound: Show (G) ≥ k by using properties of graph G, most especially, by finding a subgraph that requires k-colors.

2 min read

Matrix Representation of Graphs: The adjacency matrix of the graph G = (V,E) is an n × n matrix D = (dij), where n is the number of vertices in G, V = {v1, . . . , vn} and d_ij = number of edges between vi and vj . In particular, dij = 0 if (vi, vj) is not an edge in G. The matrix D is symmetric, i.e. DT = D. Example.

5 min read

Brooks’ Theorem: We are now prepared to present bounds for the chromatic number of a graph. We give here several upper bounds, beginning with the best known and most applicable. The bound (G) ≤ 1 Δ
(G) holds with equality for complete graphs and odd cycles. By choosing the vertex ordering more carefully, we can show that these are essentially the only such graphs. This implies, for example, that the Petersen graph is 3-colorable, without finding an explicit coloring. To avoid unimportant complications, we phrase the statement only for connected graphs. It extends to all graphs because the chromatic number of a graph is maximum chromatic number of its components. Many proofs are known; we present a modification of the proof by (Melnikov and Vizing 1969). For an alternative proof see (Lov´asz 1975). Theorem. (Brooks’ Theorem) If a connected graph G is neither an odd cycle nor a complete graph, then (G) ≤
Δ(G). Proof. If Δ
(G) ≤ 2, then G is either a path or a cycle. For a path G (other than K1 and K2), and for an even cycle G, (G) = 2 = Δ
(G). According to our assumption G is not an odd cycle. So let Δ(G) ≥ 3. The proof is by contradiction. Suppose the result is not true. Then there exists a minimal graph G of maximum degree
Δ(G) ≥ 3 such that G is not
-Δcolorable, but for any vertex v of G, G − v is
Δ(G − v)-colorable and therefore
Δ-colorable.

2 min read

Matrices over GF(2) and Vector Spaces of Graphs: The set {0, 1} is called a field (i.e. it follows the same arithmetic rules as real numbers) if addition and multiplication are defined as follows: In this case −1 = 1 and 1−1 = 1. This is the field GF(2). If we think of the elements 0 and 1 of the all-vertex incidence, cut, fundamental cut, circuit and fundamental circuit matrices of a (”undirected”) graph as elements of the field GF(2),

4 min read

COUNTING TREES The subject of graph enumeration is concerned with the problem of finding out how many nonisomorphic graphs possess a given property. The subject was initiated in the 1850’s by Arthur Cayley, who later applied it to the problem of enumerating alkanes Cn H2n 2 with a given number of carbon atoms. This problem is that of counting the number of trees in which the degree of each vertex is either 4 or 1. Many standard problems of graph enumeration have been solved. For example, it is possible to calculate the number of graphs, connected graphs, trees and Eulerian graphs with a given number of vertices and edges, corresponding general results for planar graphs and Hamiltonian graphs have, however, not yet been obtained. Most of the known results can be obtained by using a fundamental enumeration theorem due to Polya, a good account of which may be found in Harary and Palmer. Unfortunately, in almost every case it is impossible to express these results by means of simple formulas. Consider Fig. (3.27), which shows three ways of labelling a tree with four vertices. Since the second labelled tree is the reverse of the first one, these two labelled trees are the same. On the other hand, neither is isomorphic to the third labelled tree, as you can see by comparing the degrees of vertex 3.

4 min read

COMPLETE BINARY TREE If all the leaves of a full binary tree are at level d, then we call a tree as a complete binary tree of depth d. A complete binary tree of depth of 3 is shown in Fig. (3.34). Almost complete binary tree: A binary tree of depth d is said to be almost complete binary tree if (i) each node in the tree is either at level d or d – 1. (ii) for any node in the tree with a right descendant at level d, all the left descendants of this node are also at level d.

4 min read

WEIGHTED TREES AND PREFIX CODES: Consider the problem of using bit strings to encode the letters of the English alphabet (where no distinction is made between lower case and upper case letters). We can represent each letter with a bit string of length five, since there are only 26 letters and there are 32 bit strings of length five. The total number of bits used to encode data is five times the number of characters in the text when each character is encoded with five bits. Is it possible to find a coding scheme of these letters so that, when data are coded, fewer bits are used ? We can save memory and reduce transmittal time if this can be done. Consider using bit strings of different lengths to encode letters. Letters that occur more frequently should be encoded using short bit strings, and longer bit strings should be used to encode rarely occurring letters. When letters are encoded using varying numbers of bits, some method must be used to determine where the bits for each character start and end. For instance, if e were encoded with 0, a with 1, and t with 01, then the bit string 0101 could correspond to eat, tea, eaea, or tt.

3 min read

HALL’S MARRIAGE THEOREM : If G is a bipartite graph with bipartition sets V1 and V2, then there exists a matching which saturates V1 if and only if, for every subset X of V1, | X | ≤ | A(X) |. Proof. It remains to prove that the given condition is sufficient, so we assume that | X | ≤ | A(X) | for all subsets X of V1. In particular, this means that every vertex in V1 is joined to at least one vertex in V2 and also that | V1 | ≤ | V2 |. Assume that there is no matching which saturates all vertices of V1. We derive a contradiction. We turn G into a directed network in exactly the same manner as with the job assignment application. Specifically, we adjoin two vertices s and t to G and draw directed arcs from s to each vertex in V1 and from each vertex in V2 to t. Assign a weight of 1 to each of these new arcs. Orient each edge of G from its vertex in V1 to its vertex in V2, and assign a large integer I > | V1 | to each of these edges.

4 min read

Transport Network: Let N = (V, E) be a loop-free connected directed graph. Then N is called a network, or transport network, if the following conditions are satisfied : (i) There exists a unique vertex a ∈ V with id(a), the in degree of a, equal to O. This vertex a is called the source. (ii) There is a unique vertex z ∈ V, called the sink, where od(z), the out degree of z, equals O. (iii) The graph N is weighted, so there is a function from E to the set of non negative integers that assigns to each edge e = (v, w) ∈ E a capacity, denoted by c(e) = c(v, w). If N = (V, E) is a transport network, a function f from E to the non negative integers is called a flow for N if (i) f(e) ≤ c(e) for each edge e ∈ E, and (ii) for each v ∈ V, other than the source a or the sink z, If there is no edge (v, w), then f(v, w) = 0. Let f be a flow for a transport network N = (V, E) (i) An edge e of the network is called saturated if f(e) = c(e). When f(e) < c(e), the edge is called unsaturated. (ii) If a is the source of N, then val(f) = is called the value of the flow. If N = (V, E) is a transport network and C is a cut-set for the undirected graph associated with N, then C is called a cut, or an a–z cut, if the removal of the edges in C from the network results in the separation of a and z. For example, the graph in Fig. (4.67) is a transport network. Here vertex a is the source, the sink is at vertex z, and capacities are shown beside each edge. Since c(a, b) c(a, g) = 5 7 = 12, the amount of the commodity being transported from a to z cannot exceed 12. With c(d, z) c(h, z) = 5 6 = 11, the amount is further restricted to be no greater than 11.

4 min read

INFIX, PREFIX AND POSTFIX NOTATION OF AN ARITHMETIC EXPRESSION We know that even for fully parenthesised expression a repeated scanning of the expression is still required in order to evaluate the expression. This phenomenon is due to the fact that operators appear with the operands inside the expression. We can represent expressions in three different ways. They are Infix, Prefix and Postfix forms of an expression. Infix notation: The notation used in writing the operator between its operands is called infix notation. The infix form of an algebraic expression is the inorder traversal of the binary tree representing the expression. It gives the original expression with the elements and operations in the same order as they originally occured. To make the infix forms of an expression unambiguous it is necessary to include parentheses in the inorder traversal whenever we encounter an operation. Prefix notation The repeated scanning of an infix expression is avoided if it is converted first to an equivalent parenthesis free of polish notaiton. The prefix form of an expression is the preorder traversal of the binary tree representing the given expression. The expression in prefix notation are unambiguous, so that no parentheses are needed in such expression.

2 min read

Problem . Find a maximum flow in the directed network shown in Fig. (4.74) and prove that it is a maximum. Solution. We start by sending a flow of 2 units through the path sadt, a flow of 3 units through sbet, and a flow of 3 units through scft, obtaining the flow shown on the left in Fig. (4.75). Continue by sending flows of 2 units through sbdt and 2 units through sbft, obtaining the flow shown on the right in Fig. (4.75)

1 min read

For the cycle VYXV, i1R1 i2R2 = E, For the cycle VYZV, i2R2 i5R5 i6R6 = 0, For the cycle VWZV, i3R3 i5R5 i7R7 = 0, For the cycle VYWZV, i2R2 – i4R4 i5R5 i7R7 = 0, The equations arising from Kirchhoff’s first law are :

5 min read

Reachability: A node v in a simple graph G is said to be reachable from the vertex u of G if there exists a from u to v the set of vertices which a path from u to v, the set of vertices which are reachable from a given vertex v is called the reachable set of v and is denoted by R(v). For any subset U of the vertex set V, the reachable set of U is the set of all vertices which are reachable from any vertex set of S and this set is denoted by R(S). For example, in the graph given below : R(v1) = {v2, v3, v4}, R(v2) = {v1, v3, v4} and R({v1, v2}) = {v3, v4}.

2 min read

This time steps 1 and 2 produce the following results. Only node 4 is labeled from node 1, with [4, 1]. Node 5 is the only node labeled from node 4, with [3, 4] step 3 begins with Fig. (4.54). At this point, node 5 could label node 2 using the excess capacity of edge (5, 2). However, node 5 can also be used to label the sink. The sink is labeled [2, 5] and the total flow is increased to 7 units. In step 5, we work back along the path 1, 4, 5, 6, adjusting excess capacities. We return to step 1 with the configuration shown in Fig. (4.55).

3 min read

STORAGE REPRESENTATION OF BINARY TREE: In this section, we discuss two ways of representing a binary tree in computer memory. The first way uses a single array, called the sequential representation of binary tree. The second is called the link representation. Sequential Representation: We can represent the vertices of a binary tree as array elements and access the vertices using array notations. The advantage is that we need not use a chain of pointers connecting the widely separated vertices. Consider the almost complete binary tree shown in Fig. 3.39.

2 min read

INTRODUCTION: A tree is a connected acyclic graph. Kirchhoff developed the theory of trees in 1847, in order to solve the system of simultaneous linear equations which give the current in each branch and arround each circuit of an electric network. In 1857, Cayley discovered the important class of graphs called trees by considering the changes of variables in the differential calculus. Later, he was engaged in enumerating the isomers of saturated hydro carbons Cn H2n 2 with a given number of n of carbon atoms as Tree

2 min read

Hence max l_max = For example,

3 min read

3 min read

ALGORITHMS FOR CONSTRUCTING SPANNING TREES An algorithm for finding a spanning tree based on the proof of the theorem : A simple graph G has a spanning tree if and only if G is connected, would not be very efficient, it would involve the time-consuming process of finding cycles. Instead of constructing spanning trees by removing edges, spanning tree can be built up by successively adding edges. Two algorithms based on this principle for finding a spanning tree are Breath-first search (BFS) and Depth-first search (DFS). BFS algorithm In this algorithm a rooted tree will be constructed, and underlying undirected graph of this rooted forms the spanning tree. The idea of BFS is to visit all vertices on a given level before going into the next level. Procedure : (i) Arbitrarily choose a vertex and designate it as the root. Then add all edges incident to this vertex, such that the addition of edges does not produce any cycle. (ii) The new vertices added at this stage become the vertices at level 1 in the spanning tree, arbitrarily order them. (iii) Next, for each vertex at level 1, visited in order, add each edge incident to this vertex to the tree as long as it does not produce any cycle. (iv) Arbitrarily order the children of each vertex at level 1. This produces the vertices at level 2 in the tree. (v) Continue the same procedure until all the vertices in the tree have been added. (vi) The procedure ends, since there are only a finite number of edges in the graph. (vii) A spanning tree is produced since we have produced a tree without cycle containing every vertex of the graph.

2 min read

Iteration 2 : u = b, the permanent label of b is 1.0 T becomes T–{b} there are three edges incident with b, i.e., bc, bd and be where c, d, e ∈ T. L(c) = min {old L(c), L(b) w(bc)} = min {4.0, 1.0 2.0} = 3.0 L(d) = min {old L(d), L(b) w(bd)} = min {α, 1.0 6.0} = 7.0 L(e) = min {old L(e), L(b) w(be)} = min {α, 1.0 5.0} = 6.0 Thus minimum label is L(c) = 3.0.

1 min read

ROOTED TREE: A rooted tree T with the vertex set V is the tree that can be defined recursively as follows : T has a specially designated vertex v1 ∈ V, called the root of T. The subgraph of T1 consisting of the vertices V – {v} is partitionable into subgraphs. T1, T2, ......, Tr each of which is itself a rooted tree. Each one of these r-rooted tree is called a subtree of v1. Co tree: The cotree T* of a spanning tree T in a connected graph G is the spanning subgraph of G containing exactly those edges of G which are not in T. The edges of G which are not in T* are called its twigs.

4 min read

MATCHING THEORY: A matching in a graph is a set of edges with the property that no vertex is incident with more than one edge in the set. A vertex which is incident with an edge in the set is said to be saturated. A matching is perfect if and only if every vertex is saturated, that is ; if and only if every vertex is incident with precisely one edge of the matching. Let G = (V, E) be a bipartite graph with V partitioned as X ∪ Y. (each edge of E has the form {x, y} with x ∈ X and y ∈ Y). (i) A matching in G is a subset of E such that no two edges share a common vertex in X or Y. (ii) A complete matching of X into Y is a matching in G such that every x ∈ X is the end point of an edge.

2 min read

Shortest Path Algorithm: In many areas like transportation, cartoon motion planning, communication network topology design etc, problems related to finding shortest path algorithms. The shortest path problem is concerned with finding the least cost (that costs minimum) path from an originating node in a weighted graph to a destination node in that graph. Let us consider a graph shown in the Fig. (4.1) in which number associated with each arc represent the weight of the arc. There exist many algorithms for finding the shortest path in a weighted graph. One such algorithm is developed by Dijkstra in the early 1960’s for finding the shortest path in a graph with non-negative weight associated with edge/arc without explicitly enumerating all possible paths. This algorithm is based upon a technique known as dynamic programming.

7 min read

Prim’s algorithm: Let G = (V, E) be a connected graph with | V | = n. To find the adjacency matrix for G. Now proceed according to the following steps : Step 1 : Select a vertex v1 ∈ V and arrange the adjacency matrix of the graph in such a way that the first row and first column of the matrix corresponds to V1. Step 2 : Choose a vertex v2 of V such that (v1, v2) ∈ E. Merge v1 and v2 into a new vertex, call it vmi and drop v2. Replace v1 by vmi in the graph. Find the new adjacency matrix corresponding to this new quotient graph. Step 3 : While merging select an edge from those edges which are going to be removed (or merged with other edge) from the graph. Keep a record of it. Step 4 : Repeat steps 1, 2 and 3 until all vertices have been merged into one vertex. Step 5 : Now construct a tree from the edges, collected at different iterations of the algorithm. The same Prim’s algorithm with little modification can be used to find a minimum spanning tree for a weighted graph. The stepwise algorithm is given below. Let G = (V, E) be graph and S = (Vs, Es) be the spanning tree to be found from G. Step 1 : Select a vertex v1 of V and initialize Vs = {v1} and Es = {} Step 2 : Select a nearest neighbour of vi from V that is adjacent to same vj ∈ Vs and that edge (vi, vj) does not form a cycle with members edge of Es. Set Vs = Vs ∪ {vi} and Es = Es ∪ {(vi, vj)} Step 3 : Repeat step 2 until | Es | = | V | – 1. Theorem 4.5. Prim’s algorithms produces a minimum spanning tree of a connected weighted graph. Proof. Let G be a connected weighted graph. Suppose that the successive edges chosen by Prim’s algorithm are e1, e2, ..., en – 1. Let S be the tree with e1, e2, ..., en – 1 as its edges, and let Sk be the tree with e1, e2, ..., ek as its edges. Let T be a minimum spanning tree of G containing the edges e1, e2, ..., ek, where k is the maximum integer with the property that a minimum spanning tree exists containing the first k edges chosen by Prim’s algorithm. The theorem follows if we can show that S = T. Suppose that S ≠ T, so that k < n – 1. Consequently, T contains e1, e2, ..., ek, but not e_{k 1}. Consider the graph made up of T together with e_{k 1}. Since this graph is connected and has n edges, too many edges to be a tree, it must contain a simple circuit. This simple circuit must contain e_{k 1} since there was no simple circuit in T. Furthermore, there must be an edge in the simple circuit that does not belong to S_{k 1} since S_{k 1} is a tree. By starting at an end point of e_{k 1} that is also an endpoint of one of the edges e1, ..., ek, and following the circuit until it reaches an edge not in Sk 1, we can find an edge e not in S_{k 1} that has an end point that is also an end point of one of the edges e1, e2, ..., ek. By deleting e from T and adding e_{k 1}, we obtain a tree T′ with n – 1 edges (it is a tree since it has no simple circuits).

6 min read

MINIMAL SPANNING TREES Weighted graph: A weighted graph is a graph G in which each edge e has been assigned a non-negative number w(e), called the weight (or length) of e. Figure (4.12) shows a weighted graph. The weight (or length) of a path in such a weighted graph G is defined to be the sum of the weights of the edges in the path. Many optimisation problems amount to finding, in a suitable weighted graph, a certain type of subgraph with minimum (or maximum) weight. Minimal spanning tree: Let G be weighted graph. A minimal spanning tree of G is a spanning tree of G with minimum weight. The weighted graph G of Figure (4.12) shows six cities and the costs of laying railway links between certain pairs of cities. We want to set up railway links between the cities at minimum costs.

3 min read

BINARY SEARCH TREES A binary search tree is basically a binary tree, and therefore it can be traversed in preorder postorder, and inorder. If we traverse a binary search tree in inorder and print the identifiers contained in the vertices of the tree, we get a sorted list of identifiers in the ascending order. Binary trees are used extensively in computer science to store elements from an ordered set such as a set of numbers or a set of strings. Suppose we have a set of strings and numbers. We call them as keys. We are interested in two of the many operations that can performed on this set. (i) ordering (or sorting) the set (ii) searching the ordered set to locate a certain key and, in the event of not finding the key in the set, adding it at the right position so that the ordering of the set is maintained. A binary search tree is a binary tree T in which data are associated with the vertices. The data are arranged so that, ∈ for each vertex v in T, each data item in the left subtree of v is less than the data item in v and each data item in the right subtree of v is greater than the data item in v. Thus, a binary search tree for a set S is a label binary tree in which each vertex v is labelled by an element l(v) ∈ S such that (i) for each vertex u in the left subtree of v, l(u) < l(v), (ii) for each vertex u in the right subtree of v, l(u) > l(v), (iii) for each element a ∈ S, there is exactly one vertex v such that l(v) = a.

4 min read

TREES AND SORTING Decision trees: Rooted trees can be used to model problems in which a series of decisions leads to a solution. For instance, a binary search tree can be used to locate items based on a series of comparisons, where each comparison tells us whether we have located the item, or whether we should go right or left in a subtree. A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these vertices for each possible outcome of the decision, is called a decision tree. The possible solutions of the problem correspond to the paths to the leaves of this rooted tree. The complexity of sorting algorithms: Many different sorting algorithms have been developed. To decide whether a particular sorting algorithm is efficient, its complexity is determined. Using decision trees as models, a lower bound for the worst-case complexity of sorting algorithms can be found. We can use decision trees to model sorting algorithms and to determine an estimate for the worst-case complexity of these algorithms.

3 min read

Postfix / Post-order: Traversing a binary tree using postfix or post-order means to trace the outline of the tree, again starting just to the left of the root node, and going downward. You identify node contents when the trace passes upward on the right side of the node. The root node is always the last node. Here is our example of 2 3: 2 3 One way to interpret this is: Using 2 and 3, add them together. This produces a result which at first looks like just the opposite of prefix/pre-order, but it is not. Notice that the sequence of the values is the same, but the placement of the operator has changed. This becomes more obvious when we perform the same operation on our other expression tree: 6 3 * 1 - One way to interpret this is: using 6 and 3, multiply them, then using 1, subtract. (Still potentially confusing, but it gets better.)

5 min read

Huffman coding: We now introduce an algorithm that takes as input the frequencies (which are the probabilities of occurrences) of symbols in a string and produces as output a prefix code that encodes the string using the fewest possible bits, among all possible binary prefix codes for these symbols. This algorithm, known as Huffman coding. Note that this algorithm assumes that we already know how many times each symbol occurs in the string so that we can compute the frequency of each symbol of dividing the number of times this symbol occurs by the length of the string. Huffman coding is a fundamental aglorithm in data compression the subject devoted to reducing the number of bits required to represent information.

2 min read

TREE TRAVERSAL A traversal of a tree is a process to traverse a tree in a systematic way so that each vertex is visited exactly once. Three commonly used traversals are preorder, postorder and inorder. We describe here these three process that may be used to traverse a binary tree. Preorder traversal The preorder traversal of a binary tree is defined recursively as follows (i) Visit the root (ii) Traverse the left subtree in preorder. (iii) Traverse the right subtree in preorder Postorder traversal The postorder traversal of a binary tree is defined recursively as follows (i) Traverse the left subtree in postorder (ii) Traverse the right subtree in postorder (iii) Visit the root.