# Group theory and their type in Discrete Mathematics

In this article, we will learn about the **group and the different types of group in discrete mathematics**.

Submitted by Prerana Jain, on August 14, 2018

### Semigroup

An algebraic structure **(G, *)** is said to be a semigroup. If the binary operation ***** is associated in **G** i.e. **if (a*b) *c = a *(b*c) a,b,c e G**. For example, the set of **N** of all natural number is semigroup with respect to the operation of addition of natural number.

Obviously, addition is an associative operation on **N**. similarly, the algebraic structure **(N, .)(I, +)** and **(R, +)** are also semigroup.

### Monoid

A group which shows property of an identity element with respect to the operation ***** is called a monoid. In other words, we can say that an algebraic system **(M,*)** is called a monoid if **x, y, z E M**.

**(x *y) * z = x * (y * z)**

And there exists an elements **e E M** such that for any **x E M**

**e * x = x * e = x** where **e** is called identity element.

### Closure property

The operation **+** is closed since the sum of two natural number is a natural number.

### Associative property

The operation **+** is an associative property since we have **(a+b) + c = a + (b+c) a, b, c E I**.

### Identity

There exist an identity element in a set **I** with respect to the operation **+**. The element 0 is an identity element with respect to the operation since the operation **+** is a closed, associative and there exists an identity. Since the operation **+** is a closed associative and there exists an identity. Hence the algebraic system **( I, +)** is a **monoid**.

## Group

A system consisting of a non-empty set **G** of element **a, b, c** etc with the operation is said to be group provided the following postulates are satisfied:

**1. Closure property**

For all a, b E G => a, b E G i.e G is closed under the operation ‘.’

**2. Associativity**

(a,b).c = a.(b.c) a, b, c E G. i.e the binary operation ‘.’ Over g is associative.

**3. Existence of identity**

There exits an unique element in G. Such that e.a = a = a.e for every a E G. This element e is called the identity.

**4. Existence of inverse**

For each a E G , there exists an element a^-1 E G such that a. a^-1 = e = a^-1.a the element a^-1 is called the inverse of a .

### Commutative Group

A group **G** is said to be abelian or commutative if in addition to the above four postulates the following postulate is also satisfied.

**5. Commutativity**

a.b = b.a for every a, b E G.

### Cyclic Group

A group **G** is called cyclic. If for some **aEG**, every element **xEG** is of the form **a^n**. where **n** is some integer. Symbolically we write **G = {a^n : n E I}**. The single element a is called a generator of **G** and as the cyclic group is generated by a single element, so the cyclic group is also called **monogenic**.

### Subgroup

A non- empty subset **H** of a set group **G** is said to be a subgroup of **G**, if **H** is stable for the composition ***** and **(H, *)** is a group. The additive group of even integer is a subgroup of the additive group of all integer.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions