Discrete Maths 2

Contents: Relations Graphs Theory Trees Finite Automata Sample Problems

Relations

Definition of a relation
A relation between elements of two sets are defined using ordered pairs. Since this is a relation between two sets, it is classified as a binary relation. The binary relation of two sets (A and B) is a subset of A × B.

Inverse of a relation
For $\forall x\in A$ and $\forall y\in B$, $(x,y)\in \mathbb{R}\Leftrightarrow (y,x)\in \mathbb{R}^{-1}$.

Characteristics of a relation
One relation may have one or more of the following characteristics:

• Reflexive: if $(a,a)\in R$
• Symmetric: if $(b,a)\in R$, then $(a,b)\in R$
• Antisymmetric: if $((a,b)\in R) \wedge ((b,a)\in R)$, then $a=b$
• Asymmetric: if $(a,b)\in R$, then $(b,a)\notin R$
• Transitive: if $((a,b)\in R) \wedge ((b,c)\in R)$, then $(a,c)\in R$

Types of a relation

• Equivalence Relation: if a relation satisfies the definition of Reflexive, Symmetric and Transitive.
• Partially Ordered Sets: if a relation satisfies the definition of Reflexive, Antisymmetric and Transitive.

Comparability
Suppose R is a partial order relation on a set. If a and b, the elements of that set fulfill either a R b or b R a, then a and b are comparable. Otherwise, a and b are noncomparable. If every pair of elements are comparable, then the partial order is a total order.

Hasse Diagram It is a diagram used to describe partially ordered sets. An element a in the set is called the ... if it fulfills the definition of:

• Maximal: $\forall b \in A$, then $a \succeq b$ or a and b are noncomparable.
• Minimal: $\forall b \in A$, then $a \preceq b$ or a and b are noncomparable.
• Maximum^Unique: $\forall b \in A$, then $a \succeq b$.
• Minimum^Unique: $\forall b \in A$, then $a \preceq b$.

Let B be a sub-set of A, and b as an element in the set B. Element(s) in the set A is called the ... if it fulfills the definition of:

• Upper Bound: $a \succeq b$.
• Lower Bound: $a \preceq b$.
• Least Upper Bound: the lowest of all upper bounds.
• Greatest Lower Bound: the highest of all lower bounds.

Graphs Theory

Definition
Graph G consists of two finite sets: nonempty set of vertices V(G) and set of edges E(G). There are several terms often used:

• Endpoint: vertices associated with an edge.
• Edge-endpoint function: correspondence from edges to endpoints.
• Adjacent^vertex: two or more vertices that are connected by an edge.
• Isolated: vertex with no incident edges.
• Loop: an edge with one endpoint.
• Parallel: two or more distinct edges with the same set of endpoints.
• Adjacent^edge: edges that are incident on the same endpoint.
• Incident: edges that is directly linked to a vertex.
• Degree: of a vertex is equal to the amount of edges it connects to.

Types of Graphs

• Simple Graph: no loops, and no parallel edges.
• Complete Graph: every pair of distinct vertices share an edge.
• Bipartite Graph: an element of a set is only linked to elements of another set.
• Complete Bipartite Graph: an element of a set is only linked to all elements of another set.
• Directed Graph: all edges have its own direction.
• Subgraph: smaller graphs formed from a graph.
• Weighted Graph: all edges have its own weight.
• Connected Graph: if all node can be linked to another node through a sequence of edges.
• Planar Graph: if a graph can be drawn in a way where no edges intersect.
• Isomorphic Graph: graph formed through stretching, or repositioning of a graph. Isormophic graphs mostly share the same:
  
  • Amount of vertices & edges.
  • Degrees of corresponding vertices.
  • Types of possible subgraphs.

Handshaking Theorem
Let G be a graph that consists of vertices v_i and has n edges. The total degree of the graph G is:

$\text{Degree }G=\sum \text{Degree }v_i=2\times n$

Definition Table

	Repeated Edges	Repeated Vertex	Same Start & Finish	At Least 1 Edge
Walk	Allowed	Allowed	Allowed	No
Trail	No	Allowed	Allowed	No
Path	No	No	No	No
Closed Walk	Allowed	Allowed	Yes	No
Circuit	No	Allowed	Yes	Yes
Simple Circuit	No	First & Last	Yes	Yes

Other than above, there are also:

• Euler circuit: exists in a graph where its edges can be traversed once, and the degrees of all vertices are even. The starting and finishing vertex are the same vertice.
• Euler path: exists in a graph where its edges can be traversed once, and only the degrees of the starting and finishing vertices are odd while the rest are even. The starting and finishing vertex are different.
• Hamiltonian Circuit: is a simple circuit that includes all vertex in the graph.
• Hamiltonian Path: is a path that traverses all vertex in the graph exactly once.

Adjacency Matrix of Directed Graph
Let G be a directed graph that has vertices v_n. The adjacent matrix of G is the matrix where its element (a_ij) corresponds to the number of arrows from v_i to v_j.

Adjacency Matrix of Undirected Graph
Let G be a directed graph that has vertices v_n. The adjacent matrix of G is the matrix where its element (a_ij) corresponds to the number of edges that connects v_i to v_j.

Vertex Colouring

• Find the degrees of all vertices, and sort them descendingly.
• Start by assigning a colour to the vertice with the highest degree.
• Colour the next highest degree. If it is adjacent to a vertex with an already used colour, assign a new colour.
• Repeat.

Edge Colouring
The number of colours used will be equal to the highest degree of a vertice in the graph.

• Start by assigning a colour to any edge.
• Colour another edge. If it is adjacent to an edge with an already used colour, assign a new colour.
• Repeat.

Face Colouring

• Start by assigning a colour to any face.
• Colour another face. If it is adjacent to an edge with an already used colour, assign a new colour.
• Repeat.

In a graph, that has V vertices, E edges and F faces:

$V-E+F=2$

Trees

Definition
A graph is called a Tree, if it does not contain any circuits, loops, parallels, and is connected. If it is not connected, it is a Forest.

Types of Trees

• Trivial Trees: only consists of a single vertex.
• Rooted Trees: consists of vertices, and one of them is the Root. Level of a vertex is equal to the amount of edges along the unique path between it and the root, and Height of a rooted tree is the greatest level in that tree.
• Binary Trees: are Rooted Trees where each parents has two children at most. If each of the parents has exactly two children, then it can be called Full Binary Trees.
• Spanning Trees: are subgraphs of a graph, that contains all vertices of that graph and are classified as trees.
• Minimum Spanning Trees: is a spanning tree whose sum of edges are the least possible amount.

Finding Minimum Spanning Tree
In order to find the minimum spanning tree of a graph, Kruskal's or Prim's algorithm can be used:

• Find the edge with the least weight, and mark that edge.
• ^KruskalFind another non-marked edge with the least weight that doesn't create a circuit, and mark it. ^PrimFind another non-marked edge with the least weight, connected to already marked edge(s), doesn't create a circuit, and mark it.
• Repeat.

Finite State Automata

Automaton is a mathematical object that consists of:

• State
• Start State
• End State
• Input Alphabet
• FSA Function / Next-State Function

Sample Problems

Problem 1: Relations
C is the circle relation on R. $\forall x,y \in \mathbb{R}$, $x\text{ C }y \Leftrightarrow x^2+y^2=1$. Check if C fulfills the definition of a reflexive, symmetric, asymmetric, antisymmetric, and transitive.

Checking if C is Reflexive:
$\forall x \in \mathbb{R}, x\text{ C }x\Leftrightarrow x^2+x^2=1\\ $
Counter-example, Let x = 1:
$\begin{align*} x^2+x^2 &= 1\\ 1+1 &= 1\\ 2 &\neq 1 \end{align*}$

∴ C is not Reflexive.

Checking if C is Symmetric:
$\begin{align*} \forall x,y \in \mathbb{R}, x\text{ C }y\Leftrightarrow & x^2+y^2=1\\ y\text{ C }x\Leftrightarrow & y^2+x^2=1\\ &x^2+y^2=y^2+x^2 \end{align*}$

∴ C is Symmetric.

Checking if C is Asymmetric:
Since C is already proven as a Symmetric relation, it is not Asymmetric.

∴ C is not Asymmetric.

Checking if C is Antisymmetric:
By the definition of Antisymmetric, if $(a,b) \in \mathbb{R}$ and $(b,a) \in \mathbb{R}$ (which has been proven previously), then a = b.

Counter-example, let x = 0.6 and y = 0.8:
$\begin{align*} x^2+y^2&=1\\ 0.6^2+0.8^2&=1\\ 0.8^2+0.6^2&=1\\ \end{align*}$

But, $x \neq y$.

∴ C is not Antisymmetric.

Checking if C is Transitive:
Counter-example, let x = 1, y = 0 and z = 1:
$\begin{align*} 1\text{ C }0 \Leftrightarrow 1+0&=1\\ 0\text{ C }1 \Leftrightarrow 0+1&=1\\ 1\text{ C }1 \Leftrightarrow 1+1&\neq 1\\ \end{align*}$

∴ C is not Transitive.

Problem 2: Relations
X is a relation on R. $\forall x,y \in \mathbb{R}$, $x\text{ X }y \Leftrightarrow x>y$.

1. Check if X fulfills the definition of a reflexive, symmetric, asymmetric, antisymmetric, and transitive.
2. Is X a POSet relation? If it is a POSet relation, draw the Hasse diagram for the set $A=\left \{ \frac{3}{4},\frac{4}{3},3,\frac{7}{5},2 \right \}$.

Checking if X is Reflexive:
$\begin{align*} \forall x \in \mathbb{R}, x\text{ X }x\Leftrightarrow &x>x\\ &x\ngtr x \end{align*}$

∴ X is not Reflexive.

Checking if X is Symmetric:
Counter-example, let x = 1 and y = 2:
$\begin{align*} & 1\text{ X }2\Leftrightarrow 1 \ngtr 2\\ & 2\text{ X }1\Leftrightarrow 2 > 1\\ \end{align*}$

∴ X is not Symmetric.

Checking if X is Asymmetric:
Since C is not a Symmetric relation, it is Asymmetric.

∴ C is Asymmetric.

Checking if C is Antisymmetric:
By the definition of Antisymmetric, if $(a,b) \in \mathbb{R}$ and $(b,a) \in \mathbb{R}$ (which has been proven wrong previously), then a = b.

The definition above is in the form of implication: If A then B. If A is false, then the statement (implication) will always be true:

$A$	$B$	$A \rightarrow B$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

∴ X is Antisymmetric.

Checking if X is Transitive:
$\begin{align*} \forall x,y \in \mathbb{R}, x\text{ X }y\Leftrightarrow &x>y\\ \forall y,z \in \mathbb{R}, y\text{ X }z\Leftrightarrow &y>z\\ &x>y>z\\ &x>z\\ \therefore &x\text{ X }z \end{align*}$

∴ X is Transitive.

POSet relation is a relation that fulfills the definition of a Reflexive, Antisymmetric and Transitive. Since X has not been proven as a reflexive relation, X is NOT a POSet relation.

Problem 3: Relations
K is a relation on set $A=\left \{ 1,2,3,4,5,6,7,8,9,10 \right \}$. $\forall x,y \in \mathbb{R}$, $x\text{ K }y \Leftrightarrow x|y$.

1. Prove that K is a POSet relation, and draw the Hasse diagram.
2. Determine the maximal, minimal, maximum, minimum (if exists)!
3. What are the upper bound(s), and lower bound(s) of $B=\left \{ 3,4,5 \right \}$?
4. What are the upper bound(s), and lower bound(s) of $B=\left \{ 6,10 \right \}$?

POSet relation is a relation that fulfills the definition of a Reflexive, Antisymmetric and Transitive. So, K has to be proven to fulfill those definition.

Checking if K is Reflexive:
$\begin{align*} \forall x \in A, x\text{ K }x\Leftrightarrow &x|x \end{align*}$

∴ K is Reflexive.

Checking if K is Symmetric:
$\begin{align*} \forall x,y \in A, x\text{ K }y\Leftrightarrow &x|y\\ y\text{ K }x\Leftrightarrow &y|x \end{align*}$

If $(a|b)\wedge (b|a)$ is false, then $a \neq b$. $(a|b)\wedge (b|a)$ is only true when $a=b$.

∴ K is Antisymmetric.

Checking if K is Transitive:
$\begin{align*} \forall x,y \in A, x\text{ K }y\Leftrightarrow &x|y\\ \forall y,z \in A, y\text{ K }z\Leftrightarrow &y|z\\ \end{align*}$

Let $k,m \in \mathbb{Z}$, so that $m = \frac{y}{x}$, and $k = \frac{z}{y}$. So:
$m = \frac{y}{x}$, and $\begin{align*} \frac{z}{x}&=\frac{z}{y}\times \frac{y}{x}\\ &= k\times m\\ \therefore &\frac{z}{x} \in \mathbb{Z} \end{align*}$

∴ K is Transitive.

Sub-Problem B:
K is proven to be a POSet relation. The hasse diagram for K can be drawn:


From the graph above:

• Maximal: 6, 7, 8, 9, 10
• Minimum: 1

Sub-Problem C:
The upper bounds for the set {3, 4, 5} does not exist. The lower bounds for the set {3, 4, 5} is 1.

Sub-Problem D:
The upper bounds for the set {6, 10} does not exist. The lower bounds for the set {6, 10} is 1 and 2.

Problem 4: Graphs Theory
Given the following graph:

1. Determine all edges that are incident to v₄!
2. Determine all edges that are adjacent to e₁!
3. Determine all vertices that are adjacent to v₆!
4. Determine the degrees of all vertices in the graph!

Sub-Problem A:
e₃, e₄, e₅ and e₆

Sub-Problem B:
e₂, e₈, e₉ and e₁₃

Sub-Problem C:
v₂, v₄, v₅ and e₇

Sub-Problem D:

Vertices	Degrees
v1	2
v2	4
v3	2
v4	4
v5	4
v6	4
v7	4
v8	4

Problem 5: Graphs Theory
Using the same graph from Problem 4:


Determine what the following walks are classified as (trails, path, closed walk, circuit, or simple circuit).

1. v₁ e₁ v₂ e₉ v₈
2. v₁ e₁ v₂ e₁ v₁
3. v₁ e₁ v₂ e₈ v₆ e₆ v₄ e₃ v₃ e₂ v₂
4. v₈ e₉ v₂ e₈ v₆ e₇ v₅ e₁₂ v₇ e₁₀ v₈

Sub-Problem A: Path
Sub-Problem B: Closed Walk
Sub-Problem C: Trail
Sub-Problem D: Simple Circuit

Problem 6: Graphs Theory
Given an undirected and directed graph:




Determine the adjacency matrix of the given graphs!

The adjacency matrix of the undirected graph is:
$\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 2 & 1 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 2\\ 1 & 1 & 0 & 0 & 0 & 0 & 2 & 0 \end{bmatrix}$

The adjacency matrix of the directed graph is:
$\begin{bmatrix} 0 &0 &0 &1 &1 \\ 1 & 0 & 0& 0 & 1\\ 0 & 1& 0 & 0 &1 \\ 0 &0 & 1& 0& 1\\ 0 & 0 & 0& 0&0 \end{bmatrix}$

Problem 7: Graphs Theory
Using the same graph from Problem 4:


Describe an euler circuit in the graph, if it exists.

Euler Circuit exists in a graph whose edges can be traversed once, and the degrees of all vertices have even amount of degrees, and its starting & finishing vertices are the same vertice. All the vertices in this graph has even amount of degrees. One of the Euler Circuits for the graph above:
v₁ e₁₃ v₈ e₁₀ v₇ e₁₂ v₅ e₄ v₄ e₅ v₅ e₇ v₆ e₁₄ v₇ e₁₁ v₈ e₉ v₂ e₈ v₆ e₆ v₄ e₃ v₃ e₂ v₂ e₁ v₁

Or, the drawn version:

Problem 8: Graphs Theory
Given two graphs, G and G':




Determine if both graphs are isomorphic graphs.

Pair the vertices and edges from the first graph and second graph accordingly. The pairing result:
v₁ -> G
v₂ -> F
v₃ -> E
v₄ -> D
v₅ -> I
v₆ -> H
v₇ -> A
v₈ -> J
v₉ -> C
v₁₀ -> K
v₁₁ -> B
v₁₂ -> L

e_1-2 -> e_G-F
e_1-12 -> e_G-L
e_1-6 -> e_G-H
e_2-11 -> e_F-B
e_2-3 -> e_F-E
e_3-10 -> e_E-K
e_3-4 -> e_E-D
e_4-9 -> e_D-C
e_4-5 -> e_D-I
e_5-8 -> e_I-J
e_6-7 -> e_H-A
e_7-9 -> e_A-C
e_7-11 -> e_A-B
e_8-10 -> e_J-K
e_8-12 -> e_J-L
e_9-11 -> e_C-B
e_10-12 -> e_K-L

Both graphs are isomorphic.

Problem 9: Graphs Theory
Given two graphs, A and B:

1. Colour the vertices of graph A.
2. Colour the edges and faces of graph B.

Sub-Problem A:
List all the degrees of the vertices:

Vertices	Degree	Colour
v1	4	1
v2	3	2
v3	3	1
v4	3	2
v8	3	2
v9	3	2
v10	3	1
v5	2	3
v6	2	3
v7	2	1

When coloured:


Sub-Problem B:

Problem 10: Trees


Determine the minimum spanning tree and the total cost, using prim's and kruskal's algorithm.

Prim's Algorithm
Step-by-step:

Vertices	Weight
I-J	1
I-D	2
D-E	3
E-K	1
D-C	2
C-B	4
B-A	4
B-F	2
A-H	2
F-G	5
G-L	1
Cost	27

Drawn:


Kruskal's Algorithm
Step-by-step:

Vertices	Weight
I-J	1
K-E	1
L-G	1
I-D	2
A-H	2
F-B	2
C-D	2
D-E	3
E-F	4
C-B	4
G-E	5
Cost	27

If drawn, it is the same as Prim's algorithm.

Problem 11: Finite State Automata


Determine ¹states, ²start states, ³end states, ⁴input alphabet, ⁵FSA function and ⁶the pattern of accepted strings.

State: s₀, s₁, s₂, s₃, s₄, s₅.
Input / Start State: s₀.
Output / End State: s₂ and s₅.
Input Alphabet: 0 and 1.
FSA Function:

		1	0
->	s0	s1	s3
	s1	s2	s4
O	s2	s2	s4
	s3	s4	s5
	s4	s5	s3
O	s5	s5	s5

The automaton above accepts strings that fulfill one of the following:

• String begins with "11" and only contain "1"s.
• String begins with "00".
• String begins with "10", ends with "00", and the string length is at least 4.