Discrete Mathematics
Discrete Mathematics is a branch of mathematics that is concerned with “discrete” mathematical structures instead of “continuous”. Discrete mathematical structures include objects with distinct values like graphs, integers, logic-based statements, etc. In this tutorial, we have covered all the topics of Discrete Mathematics for computer science like set theory, recurrence relation, group theory, and graph theory.
Table of Contents
Tree (Discrete Mathematics)
In discrete mathematics, a tree is a type of graph that is made up of nodes (also called vertices) and edges. The nodes represent the individual elements of the tree, while the edges connect them. One key characteristic of a tree is that it has a unique starting point, called the root, and every other node can be reached by following a path of edges from the root. Additionally, a tree has no cycles, meaning that there is no path in the tree that starts and ends at the same node. Trees are commonly used to model hierarchical relationships, such as the organization of a company or the structure of a file system.
Paths and Circuits
A path in a graph is a succession of adjacent edges, with no repeated edges, that joins two vertices. Definition. A circuit is a path which joins a node to itself.
Recurrence Relations
A recurrence relation for the sequence
is an equation that expresses a_n in terms of one or more of the previous terms of the sequence, namely, a_0,a_1,…,a_(n-1) for all integers n, n≥n_0, where n_0 is a nonnegative integer. A sequence is called a solution of recurrence relation if terms satisfy the recurrence relation.
Mathematical Induction
Principle of Mathematical Induction The principle of mathematical induction is stated as follows: If a proposition or statement S(n) for each positive integer n is such that 1) S(1) is true i.e., S(n) is true for n=1 and 2) S(k+1) is true whenever S(k) is true for any positive integer k, then S(n) is true for all positive integers.