Discrete Structure

by CHIA YIN JIAN

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic^[1] – do not vary smoothly in this way, but have distinct, separated values.^[2]^[3] Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets^[4] (finite sets or sets with the same cardinality as the natural numbers). However, there is no exact definition of the term "discrete mathematics."^[5]Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.

Below are some example about what I had learnt in UTM.

Function

DS 2.jpg

A function or mapping (Defined as f:X→Y) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function ‘f’.

Function ‘f’ is a relation on X and Y such that for each x∈X, there exists a unique y∈Y such that (x,y)∈R. ‘x’ is called pre-image and ‘y’ is called image of function f.

Graph

Ds 1.jpg

Graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called an arc or line).^[1] Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

Types of Graphs

Though there are a lot of different types of graphs in discrete mathematics, there are some that are extremely common. Some of those are as follows:

Null graph: Also called an empty graph, a null graph is a graph in which there are no edges between any of its vertices.
Connected graph: A graph in which there is a path of edges between every pair of vertices in the graph. Mary's graph is a connected graph, since there is a way to get from every city on the map to every other city.
Disconnected graph: A graph in which the path of edges does not always connect every vertex.
Bipartite graph: A graph that can be split into two sets of vertices such that edges only go between sets, not within them.
Weighted graph: A graph in which weights, or numerical values, are assigned to each of the edges. Mary's graph is a weighted graph, where the distances between the cities are the weights of the edges.
Directed graph: A graph in which the edges are directed by arrows, indicating that the relationship, represented by the edge, only applies from one vertex to the other, but not the other way around. In other words, if a directed edge has an arrow from A to B, A is related to B, but B is not related to A.
Undirected graph: A graph whose edges are not directed. Mary's graph is an undirected graph, because the routes between cities go both ways.
Simple graph: An undirected graph in which there is at most one edge between each pair of vertices, and there are no loops, which is an edge from a vertex to itself.
Multi-graph: A graph in which there are multiple edges between any pair of vertices or there are edges from a vertex to itself, also called a loop.
Planar graph: A graph that can be drawn so that all of the edges of the graph do not cross each other.
Nonplanar graph: A graph that is not a planar graph. In other words, a graph that cannot be drawn without at least one pair of its edges crossing.