B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

Fig.4

Note : In many cases, when the graphical representation is so oriented that all the arrow heads point in one direction (upward, downward, left to right or right to left). A ^{graphical representation} in which all the arrowheads point upwards, is known as Hasse diagram.

Example 4: `Let A = {1, 2, 3, 4, 6, 9} and relation R defined on A be “ a divides b”. Hasse diagram for this relation is as follows:
Note : The reader is advised to verify that this relation is indeed a partial order relation. Further, arrive at the following Hasse diagram from the diagraph of a relation as ^{per the} rules defined earlier.



Fig.5

	^1	0	1	1	^1
	0	1	1	1	1  
M R	 ^0	0	1	1	^
	0 0	 0	 0	 0	  1
Solution :

Example 5 : Determine the Hasse diagram of the relation on A = {1,2,3,4,5} ^{whose M}R ^{is given below :}




Reflexivity is represented by 1 at diagonal place. So after removing reflexivity R is R = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5)}

Remove transitivity as

^{1, 3} ^{3, 4}<sup> R

remove</sup> ^{1, 4}^{ R}

^{2, 3} ^{3, 5}^{ R remove} ^{2, 5}^{ R and so on.}

R  _1, 3_, _2, 3_, _3, 4_, _3, 5_ The Hasse Diagram is
Example 6 :
Determine matrix of partial order whose Hasse diagram is given as follow -



Solution :
Here A = [1, 2, 3, 4, 5)
Write all ordered pairs (a, a)  a  A i.e. relation is reflexive.
Then write all ordered pairs in upward direction. As (1, 2)  R & ^{(2,4)  R } ^{1, 4}^{ R since} R is transitive.
^{ R } ^{1,1, 2,2, 3,3, 4,4, 5,5, 1,2, 2,4, 2,4, 1,4 , 1,3, 3,5, 1,5}
The matrix M_R can be written as -


^{1 1}


0
_ 1

M  ^0 0

R _


0
_ 0

^_0 0

^{1 1 1}


0


0 1 _

1 0 1^

0


0 1 _

0 0 1^_

Now, we shall have a look at certain terms with reference to posets.
Definition : Let (A, ) be a partially ordered set. Elements a, b  A, are said to be comparable, if a  b

or b  a.

E.g. In example 4, 2 and 4 are comparable, whereas 4 and 9 are not comparable.
Definition : Let (A,  ) be a partially ordered set. A subset of A is said to be a chain if every two elements in the subset are related.
Example 7: In the poset of example 4, subsets {1, 2, 4}; {1, 3, 6};{1, 2, 6} and {1, 3, 9} are chains.
Definition : A subset of a poset A is said to be anti-chain, if no two elements of it are related.
Example 8: In the poset of example 4, subsets {2, 9}; {3, 4}; {4, 6, 9}are anti-chains.
Definition : A partially ordered set A is said to be totally ordered if it is chain.
Example 9: Let A = {2, 3, 5, 7, 11, 13, 17, 19} and the relation defined on A be .

Then poset (A, ) is a chain.

CLOSURE PROPERTIES

Consider a given set A and let R be a relation on A. Let P be a property of such relations, such as being reflexive or symmetric or transitive. A relation with property P will be called a P-relation. The P-closure of an arbitrary relation R on A, written P (R), is a P-relation such that

R ⊆ P (R) ⊆ S

for every P-relation S containing R. We will write

reflexive (R),symmetric(R), and transitive(R) for the reflexive, symmetric, and transitive closures of R.

Generally speaking, P (R) need not exist. However, there is a general situation where P (R) will always exist. Suppose P is a property such that there is at least one P-relation containing R and that the intersection of any P-relations is again a P-relation. Then one can prove that

P (R) = ∩(S | S is a P -relation and R ⊆ S)

Thus one can obtain P (R) from the “top-down,” that is, as the intersection of relations. However,

one usually wants to find P (R) from the “bottom-up,” that is, by adjoining elements to R to obtain P (R). This we do below.

Reflexive and Symmetric Closures

The next theorem tells us how to obtain easily the reflexive and symmetric closures of a relation. Here

A = {(a, a) | a ∈ A} is the diagonal or equality relation on A.

Theorem: Let R be a relation on a set A. Then:

1. R ∪ A is the reflexive closure of R.

2. 
   R ∪ R⁻¹ is the symmetric closure of R.
   

In other words, reflexive(R) is obtained by simply adding to R those elements (a, a) in the diagonal which do not already belong to R, and symmetric(R) is obtained by adding to R all pairs (b, a) whenever (a, b) belongs to R.

EXAMPLE 10 Consider the relation R = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)} on the

set A = {1, 2, 3, 4}.

Then

reflexive(R) = R ∪ {(2, 2), (4, 4)} and symmetric(R) = R ∪ {(4, 2), (3, 4)}

Transitive Closure

Let R be a relation on a set A. Recall that R²= R◦R and Rⁿ= The following theorem applies:

Theorem : R∗ is the transitive closure of R.

R^n1 ◦R. We define

Suppose A is a finite set with n elements. We show

R∗= R ∪ R²∪ . . . ∪ Rⁿ This gives us the following theorem:

Theorem : Let R be a relation on a set A with n elements. Then

transitive (R) = R ∪ R²∪ . . . ∪ Rⁿ

EXAMPLE 11 Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}.

Then:

R²= R ◦R = {(1, 3), (2, 3), (3, 3)} and R³= R²◦R = {(1, 3), (2, 3), (3, 3)}

Accordingly,

transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

MAXIMAL, MINIMAL ELEMENTS AND LATTICES:
In this section, we discuss certain element types in the poset and hence a special kind of poset, Lattice.
To understand these types, we shall refer to the following figures,

i.e. Fig.6 and Fig.7.

g

_b d

_b e

a Fig. 7
Fig. 6

Definition : Let (A, ) be a poset. An element a  A is called a maximal element, if for no b  A, a  b, a  b. E.g. In Fig. 4, j and k are maximal elements.

Definition : Let (A, ) be a poset. An element a  A is called a minimal element, if for no

b  A, a  b, b  a. E.g. In Fig. 4.6, a, b and e are minimal elements.

Definition : Let a, b be two elements in the poset (A, ). An element c  A, is said to be an upper bound of a, b if a  c and b  c. E.g. In Fig 7, f₁ h are upper bounds of b and d.

Definition : Let a, b be two elements in the poset (A, ). An element c  A, is said to be a least upper bound of a, b if a  c and b  c and if d is an upper bound of a, b, then c  d. E.g. In Fig 2, f is a least upper bound of b and d.

Definition : Let a, b be two elements in the poset (A, ). An element c  A, is said to be a lower bound of a, b if c  a and c  b. E.g. In Fig 6, f, g are lower bounds of h and i.

Definition : Let a, b be two elements in the poset (A, ). An element c  A, is said to be a greatest lower bound of a, b if c  a and c  b and if d is a lower bound of a, b, then d  c. E.g. In Fig 4, c is a greatest lower bound of e and g.

Definition : A poset (A, ) is said to be a lattice, if every two elements in A have a unique least upper bound and a unique greatest lower bound.
E.g. Fig. 6 is not a lattice, because j and k are two least upper bounds of h and i, whereas Fig. 7 is a lattice.

Graph Theory

Graphs with Basic Terminology

The fundamental concept of graph theory is the graph, which (despite the name) is best thought of as a mathematical object rather than a diagram, even though graphs have a very natural graphical representation. A graph – usually denoted G(V,E) or G = (V,E) – consists of set of vertices V together with a set of edges E. Vertices are also known as nodes, points and (in social networks) as actors, agents or players. Edges are also known as lines and (in social networks) as ties or links. An edge e = (u,v) is defined by the unordered pair of vertices that serve as its end points. Two vertices u and v are adjacent if there exists an edge (u,v) that connects them. An edge e = (u,u) that links a vertex to itself is known as a self-loop or reflexive tie. The number of vertices in a graph is usually denoted n while the number of edges is usually denoted m.

As an example, the graph depicted in Figure 1 has vertex set V={a,b,c,d,e.f} and edge set E = {(a,b),(b,c),(c,d),(c,e),(d,e),(e,f)}.

d

a b


Figure 1.

When looking at visualizations of graphs such as Figure 1, it is important to realize that the only information contained in the diagram is adjacency; the position of nodes in the plane (and therefore the length of lines) is arbitrary unless otherwise specified. Hence it is usually dangerous to draw conclusions based on the spatial position of the nodes. For example, it is tempting to conclude that nodes in the middle of a diagram are more important than nodes on the peripheries, but this will often – if not usually – be a mistake.

When used to represent social networks, we typically use each line to represent instances of the same social relation, so that if (a,b) indicates a friendship between the person located at node a and the person located at node b, then (d,e) indicates a friendship between d and e. Thus, each distinct social relation that is empirically measured on the same group of people is represented by separate graphs, which are likely to have different structures (after all, who talks to whom is not the same as who dislikes whom).

Every graph has associated with it an adjacency matrix, which is a binary nn matrix A in which a_ij = 1 and a_ji = 1 if vertex vi is adjacent to vertex vj, and aij = 0 and aji = 0 otherwise. The natural graphical representation of an adjacency matrix is a table, such as shown in Figure 2.

	a	b	c	d	e	f
a	0	1	0	0	0	0
B	1	0	1	0	0	0
c	0	1	0	1	1	0
D	0	0	1	0	1	0
e	0	0	1	1	0	1
f	0	0	0	0	1	0

Figure 2. Adjacency matrix for graph in Figure 1.

Examining either Figure 1 or Figure 2, we can see that not every vertex is adjacent to every other. A graph in which all vertices are adjacent to all others is said to be complete. The extent to which a graph is complete is indicated by its density, which is defined as the number of edges divided by the number possible. If self-loops are excluded, then the number possible is n(n-1)/2. If self-loops are allowed, then the number possible is n(n+1)/2. Hence the density of the graph in Figure 1 is 6/15 = 0.40.

A clique is a maximal complete subgraph. A subgraph of a graph G is a graph whose points and lines are contained in G. A complete subgraph of G is a section of G that is complete (i.e., has density = 1). A maximal complete subgraph is a subgraph of G that is complete and is maximal in the sense that no other node of G could be added to the subgraph without losing the completeness property. In Figure 1, the nodes {c,d,e}

together with the lines connecting them form a clique. Cliques have been seen as a way to represent what social scientists have called primary groups.

hile not every vertex in the graph in Figure 1 is adjacent, one can construct a sequence of adjacent vertices from any vertex to any other. Graphs with this property are called connected. Similarly, any pair of vertices in which one vertex can reach the other via a sequence of adjacent vertices is called reachable. If we determine reachability for every pair of vertices, we can construct a reachability matrix R such as depicted in Figure 3. The matrix R can be thought of as the result of applying transitive closure to the adjacency matrix A.

d

a

Figure 3.

A component of a graph is defined as a maximal subgraph in which a path exists from every node to every other (i.e., they are mutually reachable). The size of a component is defined as the number of nodes it contains. A connected graph has only one component.

A sequence of adjacent vertices v₀,v₁,…,v_n is known as a walk. In Figure 3, the sequence a,b,c,b,a,c is a walk. A walk can also be seen as a sequence of incident edges, where two edges are said to be incident if they share exactly one vertex. A walk in which no vertex occurs more than once is known as a path. In Figure 3, the sequence a,b,c,d,e,f is a path. A walk in which no edge occurs more than once is known as a trail. In Figure 3, the sequence a,b,c,e,d,c,g is a trail but not a path. Every path is a trail, and every trail is a walk. A walk is closed if v_o = v_n. A cycle can be defined as a closed path in which n >=

3. 
   The sequence c,e,d in Figure 3 is a cycle. A tree is a connected graph that contains no cycles. In a tree, every pair of points is connected by a unique path. That is, there is only one way to get from A to B.
   

The length of a walk (and therefore a path or trail) is defined as the number of edges it contains. For example, in Figure 3, the path a,b,c,d,e has length 4. A walk between two vertices whose length is as short as any other walk connecting the same pair of vertices

is called a geodesic. Of course, all geodesics are paths. Geodesics are not necessarily unique. From vertex a to vertex f in Figure 1, there are two geodesics: a,b,c,d,e,f and a,b,c,g,e,f.

The graph-theoretic distance (usually shortened to just “distance”) between two vertices is defined as the length of a geodesic that connects them. If we compute the distance between every pair of vertices, we can construct a distance matrix D such as depicted in Figure 4. The maximum distance in a graph defines the graph’s diameter. As shown in Figure 4, the diameter of the graph in Figure 1 is 4. If the graph is not connected, then there exist pairs of vertices that are not mutually reachable so that the distance between them is not defined and the diameter of such a graph is also not defined.

a	B	c	d	e	f	G
a	0	1	2	3	3	4	3
b	1	0	1	2	2	3	2
c	2	1	0	1	1	2	1
d	3	2	1	0	1	2	2
e	3	2	1	1	0	1	1
f	4	3	2	2	1	0	2
g	3	2	1	2	1	2	0

Figure 4. Distance matrix for graph in Figure 3.

The powers of a graph’s adjacency matrix, A^p, give the number of walks of length p

between all pairs of nodes. For example, A², obtained by multiplying the matrix by

itself, has entries

a ² that give the number of walks of length 2 that join node v_i to node

ij
v_j. Hence, the geodesic distance matrix D has entries d_ij = p, where p is the smallest p


ij
such that a ^p > 0. (However, there exist much faster algorithms for computing the

distance matrix.)

The eccentricity e(v) of a point v in a connected graph G(V,E) is max d(u,v), for all u  V. In other words, a point’s eccentricity is equal to the distance from itself to the point farthest away. The eccentricity of node b in Figure 3 is 3. The minimum eccentricity of all points in a graph is called the radius r(G) of the graph, while the maximum eccentricity is the diameter of the graph. In Figure 3, the radius is 2 and the diameter is

3. 
   A vertex that is least distant from all other vertices (in the sense that its eccentricity
   

equals the radius of the graph) is a member of the center of the graph and is called a central point. Every tree has a center consisting of either one point or two adjacent points.
Directed Graphs

As noted at the outset, the edges contained in graphs are unordered pairs of nodes (i.e., (u,v) is the same thing as (v,u)). As such, graphs are useful for encoding directionless relationships such as the social relation “sibling of” or the physical relation “is near”. However, many relations that we would like to model are not directionless. For example, “is the boss of” is usually anti-symmetric in the sense that if u is the boss of v, it is unlikely that v is the boss of u. Other relations, such as “gives advice to” are simply non-symmetric in the sense that if u gives advice to v, v may or may not give advice to u.

To model non-symmetric relations we use directed graphs, also known as digraphs. A digraph D(V,E) consists of a set of nodes V and a set of ordered pairs of nodes E called arcs or directed lines. The arc (u,v) points from u to v.

d a b e c f

Figure 5a

d a b e c f

Figure 5b

Digraphs are usually represented visually like graphs, except that arrowheads are placed on lines to indicate direction (see Figure 5). When both arcs (u,v) and (v,u) are present in a digraph, they may be represented by a double-headed arrow (as in Figure 5a), or two separate arrows (as shown in Figure 5b).

In a digraph, a walk is a sequence of nodes v_o,v₁,…v_n in which each pair of nodes v_i, v_i+1 is linked by an arc (v_i,v_i+1). In other words, it is a traversal of the graph in which the flow of movement follows the direction of the arcs, like a car moving from place to place via one-way streets. A path in a digraph is a walk in which all points are distinct. A semiwalk is a sequence of nodes v_o,v₁,…v_n in which each pair of nodes v_i, v_i+1 is linked by either the arc (v_i,v_i+1) or the arc (v_i+1,v_i). In other words, in a semiwalk, the traversal need not respect the direction of arcs, like a car that freely goes the wrong way on one-way streets. By analogy, we can also define a semipath, semitrail, and semicycle.

Another way to think of semiwalks is as walks on the underlying graph, where the underlying graph is the graph G(V,E) that is formed from the digraph D(V,E’) such that (u,v)  E if and only if (u,v)  E’ or (v,u)  E’. Thus, the underlying graph of a digraph is basically the graph formed by ignoring directionality.

A digraph is strongly connected if there exists a path (not a semipath) from every point to every other. Note that the path from u to v need not involve the same intermediaries as the path from v to u. A digraph is unilaterally connected if for every pair of points there is a path from one to the other (but not necessarily the other way around). A digraph is weakly connected if every pair of points is mutually reachable via a semipath (i.e., if the underlying graph is connected).

A strong component of a digraph is a maximal strongly connected subgraph. In other words, it is a subgraph that is strongly connected and which is as large as possible (there is no node outside the subgraph that is strongly connected to all the nodes in the subgraph). A weak component is a maximal weakly connected subgraph.

The number of arcs originating from a node v (i.e., outgoing arcs) is called the outdegree of v, denoted od(v). The number of arcs pointing to a node v (i.e., incoming arcs) is called the indegree of v, denoted id(v). In a graph representing friendship feelings

among a set of persons, outdegree can be seen as indicating gregariousness, while indegree corresponds to popularity. The average outdegree of a digraph is necessarily equal to the average indegree.

The adjacency matrix A of a digraph is an n × n matrix in which a_ij = 1 if (v_i,v_j)  E and a_ij = 0 otherwise. Unlike the adjacency matrix of an undirected graph, the adjacency matrix of a directed graph is not constrained to be symmetric, so that the top right half need not equal the bottom left half (i.e., a_ij <> a_ji). If a digraph is acyclic, then it is possible to order the points of D so that the adjacency matrix upper triangular (i.e., all positive entries are above the main diagonal).

Some notations

K_n : the complete graph on n vertices. C_n : the n-cycle graph.

K_m,n : the complete bipartite graph on m+n vertices and mn edges.. K_1,n : the star graph on n+1 vertices.

mK_n : m disjoint copies of K_n.

Paths and Circuits

• 
  chain : A sequence of vertices ^{[v0,v1,v2 ,...vl ]} is a chain of length l in G if
  

^vi1^vi ^{ E or v}i^vi1 ^{ E for i=1,2, ...,l.}

• 
  path : A sequence of vertices ^{[v0,v1,v2 ,...vl ]} is a path from v₀ to v_l of length l
  

^{in G if v}i1^vi ^{ E}

for i=1,2, ...,l.

• 
  simple path: It does not include the same edge twice.
  

• 
  elementary path(or chain): A path or chain in G is called elementary if no vertex occurs more than once.
  
• 
  connected graph : A graph G is connected if between any two vertices there exists a path in G joining them.
  
• 
  strongly connected graph : A graph G is strongly connected if for any two vertices x
  

and y there exists a path in G from x to y.

• 
  elementary cycle(circuit) : A cycle ^{[v0,v1,v2 ,...vl ,v0]} is a elementary cycle if
  

v_i  v_j for ij.

• 
  chordless cycle : A simple cycle ^{[v0,v1,v2 ,...vl ,v0]} is chordless if v_i v_jE for
  

i and j differing by more than 1 mod l+1.

• 
  Theorem : In a (directed or undirected) graph with n vertices, if there is a path from vertex v₁ to vertex v₂, then there is a path of no more than n-1 edges from v₁ to vertex v₂.
  
• 
  bipartite graph : An undirected graph G=(V,E) is bipartite if its vertices can be partitioned into two disjoint stable sets V=S₁+S₂.
  

complete bipartite graph : A bipartite graph G=(S₁,S₂,E) is complete if for every xS₁ and yS₂ we have xyE, i.e., every possible edge that could exist does exist. Eulerian Paths and Circuits

• L. Euler, the father of the graph theorysolved the K^önigsberg’s bridge problem, 1736

• 
  Eulerian path problem : a path that traverses each edge in the graph once and only once.
  
• 
  Theorem: An undirected graph possess an Eulerian path if and only if it is connected and has either zero or two vertices of odd degree.
  

Proof. () Suppose that the graph possess an Eulerian path. It must be connected.
When the eulerian path is traced, we observe that every time the path meets a vertex, it goes through two edges which are incident with the vertex and have not been traced before.

Thus, except for the two vertices at the ends of the path, the degree of any vertex in the graph must be even.

() omitted.

• 
  Theorem: An undirected graph possess an Eulerian circuit if and only if it is connected and has no vertices of odd degree.
  
• 
  Theorem : An directed graph possess an Eulerian circuit if and only if it is connected and the incoming degree of every vertex is equal to its outgoing degree.
  
• 
  An directed graph possess an eulerian path if and only if it is connected and the incoming degree of every vertex is equal to its outgoing degree with the possible exception of two vertices. For these two vertices, the incoming degree of one is one larger than its outgoing degree, and the incoming degree of the other is one less than its outgoing degree.
  

Hamiltonian Paths and Circuits

• Hamiltonian path : A path that passes through each of the vertices in a graph exactly once.

• 
  No simple necessary and sufficient condition is known for graph to have a Hamiltonian path or circuit.
  
• 
  Theorem : Let G be a linear graph of n vertices. If the sum of the degrees for each pair of vertices in G is n - 1 or larger, then there exists a hamiltonian path in G.
  

Proof. (1) G is connected:

Suppose G has two or more disconnected components. Let v₁ be a vertex in one component that has n₁ vertices and v₂ be a vertex in another component that has n₂ vertices.

Since the degree of v₁ is at most n₁ - 1 and the degree of v₂ is at most n₂ -1, the sum of their degrees is at most n₁ + n₂ - 2 < n - 1, contradicts to the assumption.

2. Construct a hamiltonian path:

   • 
     Let there be a length p-1 (p < n) path, (v₁, v₂, v₃, …, v_p). Both v₁ and v_p are adjacent only to the vertices that are in the path.
     
   • 
     There is a cycle containing exactly the vertices v₁, v₂, v₃, …, v_p.
     
     • 
       Assume v₁ is adjacent to ^v_i1 ^,v_i2 ^{, ...,v}_ik , where 1 < i_j < p.
       
     • 
       If v_p is adjacent to one of ^v_{i1 1} ^,v_{i2 1} ^{, ...,v}_{ik 1} ^, then we have the cycle.
       
     • 
       If v_p is not adjacent to any one of ^v_{i1 1} ^,v_{i2 1} ^{, ...,v}_{ik 1} ^, then
       

v_p is adjacent to at most p-k-1 vertices. Contradicts to the assumption.

• 
  Pick a vertex v_x that is not in the cycle. Because G is connected, there is a vertex v_k that is not in the cycle with an edge between v_x and v_k for some v_k in
  

{v₁, v₂, v₃, …, v_p}.

• 
  We now have the path (v_x, v_k, v_k+1, …, v_j-1, v_p, v_p-1, …,v_j, v₁, v₂, v₃, …, v_k-1), which contains p edges.
  

• Repeat the foregoing construction until we have a path with n - 1 edges.

• 
  Theorem : There is always a hamiltonian path in a directed complete graph.
  

Proof. Let there be a length p-1 (p < n) path, (v₁, v₂, v₃, …, v_p). Let v_x be a vertex that is not included in this path, and there is no edge from v_x to v₁. However, (v₁, v_x)  G.

Suppose that (v_x, v₂) is also an edge in the path. Replace the edge (v₁, v₂) in the original path with the two edges (v₁, v_x) and (v_x, v₂) so that the vertex v_x will be included in the argument path.

If there is no edge from v_x to v₂, then there must be an edge (v₂, v_x) in the path and we can repeat the argument.

If we find that it is not possible to include vertex v_k in any augment path by replacing an edge (v_k, v_k+1) in the original path with two edges (v_k, v_x) and (v_x, v_k+1)with 1  k  p-1, then we conclude that there must be an edge (v_p, v_x) in the graph.

We can repeat the argument until all vertices in the graph are included in the argumented path.

• 
  There is no general method of solution to the problem of proving the non-existence of a hamiltonian path or circuit in a graph.
  

Planar Graphs

• planar graph : A graph is said to be planar if it can be drawn on a plane is such a way that no edges cross one another, except, of course, at common vertices.

• 
  Region : A region of a planar graph is defined to be an area of the plane that is bounded be edges and is not further divided into subareas. A region is said to be finite if this area is finite, and is said to be infinite if its area is infinite. Clearly, a planar graph has exactly one infinite region.
  
• 
  Theorem : For a connected planar graph,v - e + r = 2 (Euler’s formula)
  

where v, e, and r are the number of vertices, edges, and regions of the graph, respectively.

• 
  Application of Euler’s formula : In any connected planar graph that has no loops and has two or more edges,e  3v -6.
  

• 
  Theorem (Kuratowski): A graph is planar if and only if it does not contain any subgraph that is isometric to o either K₅ or K_3,3.
  
• 
  Tree: A part of a graph that is connected and contains no cycles.
  

• 
  Theorem: A connected graph possesses a tree iff there is exactly one path in between every pair of vertices.
  
• 
  Theorem: A tree with n vertices has exactly n – 1 vertices.
  

• 
  Spanning Tree: A tree containing all the vertices with exactly n – 1 edges.
  

• 
  There are two algorithms namely Kruskal’s and Prim’ algorithms to find the MST.
  

Unit III

GROUP THEORY

OBJECTIVES:

After going through this unit, you will be able to know:

• 
  Binary Operation
  
• 
  Definition of Group, semi group, Monoid
  

• Permutation groups

• 
  Cosets and Lagrange's theorem
  
• 
  Homomorphism, Isomorphism and Automorphism of Groups
  

• Rings, integral domains and field.

INTRODUCTION:

In this chapter, we will study, binary operation as a function, and two more algebraic structures, semigroups and groups. They are called an algebraic structure because the operations on the set define a structure on the elements of that set. We also define the notion of a hornomorphism and product and quotients of groups and semigroup.
BINARY OPERATION
A binary operation on a set A is an everywhere defined function ^{f : A  A  A , generally the operation is denoted by *} on A, then a  b  A a, b  A.
Properties of binary operation : Let  be a binary operation on a set A, Then  satisfies the following properties, namely

• 
  Closure property
  
• 
  Associative property
  
• 
  Identity Property
  
• 
  Inverse property
  
• 
  Commutative property etc.