→ Logic:-

• Logic came from the Greek word logos, means “discourse”, “reason”.

• It is defined as the study of the principles of correct reasoning.

→ Types of Logic:

1. Propositional Logic
2. Predicate Logic

Note:

A proposition is a declarative sentence which is either true or false but not both. A sentence which is both true and false is called a paradox. Paradox is not a statement.

example:

• 2+2=5 (false), It is a proposition.
• kathmandu is the capital city of Nepal. (True), It is a proposition.
• Open the door. It is not a proposition.

Note: x>15, go there, who are you?

The above mentioned sentences are not propositions since we cannot say whether they are true or false.

→ Propositional variable:-

• Propositional variables (also called propositional symbols or atomic propositions) represent simple statements that can be either true or false.

• It is the placeholders for proposition. Propositional variable is denoted by letter p, q, r etc.

1. Propositional Logic:

Propositional Logic is the branch of logic that studies way of joining or modifying propositions to form more complicated propositions as well as logical relationship.

• It is also know as sentential logic/statement logic.

Note: In propositional logic, there are two types of sentences:

• Simple Sentence
• Compund Sentence

→ Simple Sentence:

Simple sentences are basic statements that cannot be further divided into simpler statements.

• It also known as atomic sentences or atomic propositions.

examples:

• “The sun rises in the east.”
• “Water boils at 100 degrees Celsius.”
• “Elephants are the largest land animals.”
• “Paris is the capital of France.”

→ Compund Sentence:

A compound sentence is a sentence that is formed by combining two or more simple sentences using logical connectives (such as conjunction, disjunction, implication, etc.)

examples:

• “It is raining AND the grass is wet.”
• “It is raining OR it is snowing.”
• “If it is raining, then the ground is wet.”

→ Simple proposition:

Any statement whose truth value does not depend on another proposition is called simple proposition.

example: Kathmandu is the capital city of Nepal.

‣Types of compound sentences:

1. Negation
2. Conjunction
3. Disjunction
4. Implications
5. Reductions
6. Equivalences

→ Truth value:-

The truth and falsity of a statement is called its truth value. The truth value of a statement is denoted by T or F according as it is true or false.

→ Negation:(not)

Let p be any preposition. The negative of given proposition P denoted by ⁓p is called negation of p.

Example:

p-“I love animals.”
negation of p i.e ⁓p is “I do not love animals.”
p: The summer in Terai is very hot.
⁓p: The summer in Terai is not very hot.

Truth Table

p	⁓p
T	F
F	T

→ Conjunction:(AND)

Given two propositions p and q, the proposition “p and q” denoted ny pΛq is the proposition that is true whenever both the propositions p and q are true, false otherwise.

• The proposition that is obtained by the use of “and” operator is also called conjunction of p and q.

Example:

If we have propositions p=”Ram is smart.” and q=”Ram is intelligent.”
then conjunction of p and q is (pΛq): Ram is smart and intelligent.

• This proposition is true only when Ram is smart and intelligent also, false otherwise.

Truth Table

p	q	pΛq
T	T	T
T	F	F
F	T	F
F	F	F

→ Disjunction:(OR)

Given two propositions p and q, the proposition “p OR q” is denoted by p⋁q is the proposition that is false whenever both the propositions p and q are false, true otherwise.

• The proposition that is obtained by the use of “or” operator is also called disjunction of p and q.

Example:

if we have proposition p= Ram is intelligent and q= Ram is diligent.
then disjunction of p and q is (p⋁q): Ram is intelligent or diligent.

Truth Table

p	q	p⋁q
T	T	T
T	F	T
F	T	T
F	F	F

→ Exclusive OR:(XOR)

Given two propositions p and q, the proposition exclusive or of p and q is denoted by p⨁q is the proposition that is true whenever only onen of the propositions p and q is true, false otherwise.

Example:

if we have propositins p= Ram drinks coffee in the morning. and q= Ram drinks tea in the morning. then the exclusive or of p and q (p⨁q): Ram drinks coffee or tea in the morning.

Truth Table

p	q	p⨁q
T	T	T
T	F	T
F	T	T
F	F	F

→ Implication(→):

Given two propositions p and q, the implication p→q is the proposition that is false when p is true and q is false, true otherwise.

•Here p is called hypothesis and q is called consequence.

We use different terminologies to express p→q like:

• if p , then q
• q is the consequence of p
• p only if q

Example:

if we have propositions p=Today is sunday. and q=It is hot today. then implication of p and q (p→q ): If today is sunday then it is hot day.
or Today is sunday only if it is hot today.

Truth Table

p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

→Some of the related implications formed from p→q are:

• Inverse of implication
• Converse of implication
• Contrapositive of implication

→ Inverse of implication:

When we add “not” to the hypothesis(p) and consequence(q) of implication p→q then it becomes ⁓p→⁓q.

Example:

p=It is raining. q=The road is muddy.
implication(p→q)=If it is raining then the road is muddy.
Inverse(⁓p→⁓q)=If it is not raining then the road is not muddy.

Truth Table

p	q	⁓p	⁓q	⁓p→⁓q
T	T	F	F	T
T	F	F	T	T
F	T	T	F	F
F	F	T	T	T

→ Converse of implication:

When we interchange/flip the hypothesis(p) and conclusion(q) of implication p→q then the result becomes q→p which is known as converse of implication.

Example:

Implication(p→q): If it is raining then the road is muddy.
Converse(q→p): If the road is muddy then it is raining.

Truth Table

p	q	p→q	q→p
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

→ Contrapositive of implication:

The contrapositive of an implication involves negating both the hypothesis (p) and the consequence (q) of the implication i.e(⁓p→⁓q) and then switching their positions to ⁓q→⁓p.

Example:

Implication(p → q): If it is raining then the road is muddy.
Contrapositive(⁓q→⁓p): If the road is not muddy then it is not raining.

Truth Table

p	q	⁓p	⁓q	⁓q→⁓p
T	T	F	F	T
T	F	F	T	F
F	T	T	F	T
F	F	T	T	T

→ Biconditional(↔):

Given two propositions p and q, the biconditional p↔q is a proposition that is true when p and q have same truth value, meaning they are either both true or both false and false otherwise.

•It is also known as “if and only if statement”.

Example:

p=You can enter the restricted area .
q= You have a valid access card.
p↔q=”You can enter the restricted area if and only if you have a valid access card.”

Truth Table

p	q	p↔q
T	T	T
T	F	F
F	T	F
F	F	T

→ Tautology:

A tautology is a compound proposition that is always true, no matter what the truth values of the atomic propositions.

Truth Table

p	⁓p	p⋁⁓p
T	F	T
F	T	T

→ Contradiction:

A contradiction is a compound proposition that is always false, regardless of the truth values of its component propositions.

Truth Table

p	⁓p	pΛ⁓p
T	F	F
F	T	F

→ Contingency:

A contingency is a compound proposition that is neither a tautology (always true) nor a contradiction (always false).

Note: To clarify, “contingency” is not a formal term in logic like “tautology” or “contradiction.” Rather, a contingency is a term used to describe a logical statement that can be true in some cases and false in others, depending on the specific truth values of its component propositions.

A contingency doesn’t have a specific truth table associated with it.

# Show that pΛq is contingency.

p	q	pΛq
T	T	T
T	F	F
F	T	F
F	F	F

Proof Methods and Strategies:

A proof is a method for establishing the truth of a statement.

Proofs are important because they allow us to establish the truth of theorems without having to rely on intuition or common sense.

Directed Proofs:

A direct proof is a type of proof that proves a theorem by starting with the hypothesis and logically deducing the conclusion. It is the simplest type of proof to understand and write.

The implication p→q can be proved by showing that if p is true, then q must also be true.

Q). If a and b are odd integers, then a+b is an even integer.

proof:

We know, if a number is odd then it can be written as 2k+1, where k is an integer.

Assume that a=2k+1 and b=2l+1, where k and l are integers.

Then, a+b=2k+1+2l+1
a+b=2(k+l)+2
since, k and l are integers, k+l is also an integer.
Hence, a+b is an even integer.

Q). If n is an odd integer, then n² is an odd integer.

proof:

Assume that n is an odd integer.
By definition, an odd integer is a number that is not divisible by 2.
Therefore, n can be written as n = 2m + 1, where m is an integer.
The square of n is n2 = (2m + 1)2.
Expanding the square, we get n2 = 4m2 + 4m + 1.
The first two terms, 4m2 and 4m, are both divisible by 2, since m is an integer.
Therefore, the only term in the expansion that is not divisible by 2 is the constant term, 1.
This means that n2 is divisible by 2, which means that it is not evenly divisible by 2. Therefore, n2 is an odd integer.

Indirect Method:

Trivial and Vacuous Proof:

Proofs by contradiction:

Mistakes in Proofs:

There are two ways of reasoning that is commanly used in drawing scientific conclusions.

• One is induction and another is deduction.

• Induction is a logical reasoning process used to establish a general proposition or statement based on specific cases or instances.

• Deduction, also known as deductive reasoning, is a method of logical inference where specific conclusions are drawn from general premises.

→ Types of Induction:

• Mathematical Induction
• Strong Induction

→ Mathematical Induction:

Mathematical Induction is an extremely important proof technique that is used to prove the mathematical theorems or statements.

• In many branches of mathematics such as algebra, geometry, arithmetic, etc , the statements or theorems involving positive integers which cannot be derived by direct proof can be proved by applying the method of mathematical induction.

• Mathematical induction typically involves three main steps:

• Base Case:

Proving that the statement is true for a specific initial value (usually the smallest value of the set of natural numbers). This step establishes that the statement holds for at least one instance.

In this step, we need to verify that P(n) is true for n=0 or 1.

• Induction Hyptothesis:

In this step, we assume that P(n) is ture for n=k i.e. P(k) is true.

• Inductive Step:

Assuming that the statement is true for a particular value (usually an arbitrary value k), and then proving that it’s true for the next value(K+1).

In this step, by using induction hypothesis, we show that P(n) is true for n=K+1.

If the base case, induction hypothesis and the inductive step are successfully established, it can be concluded that the statement is true for all natural numbers starting from the chosen initial value. This follows from the principle that if the statement is true for k, and if it can be shown that its truth for k+1 follows from its truth for k, then it must be true for all values beyond k.

In summary,

Denote the given statement(proposition) by P(n).
Prove that P(1) is true.                                → Basic Step
Assume that P(k) is true, Just replace n by k in P(n).  → Induction Hypothesis
Show that P(k+1) is also true.                          → Inductive Step

Then by the principle of mathematical induction P(n) is true for all n∈N, where n is a natural number.

Example:

→ Definiton:

Counting refers to the process of determining the number of elements in a set or the number of possible outcomes in a certain scenario.

• It is used in Inventory Management, Probability, Statistical Analysis etc.

Combinatory is a branch of discrete mathematics that focuses on studying arrangements, selections, and combinations of objects from finite sets.

• It is used in Permutations and Arrangements, Poker and Card Games, Coding and Cryptography etc.

→ Basic Counting principles:

Sum Rule Principle

The Sum Rule Principle, also known as the Addition Principle, is a fundamental counting principle in combinatorics.

• It states that if there are “m” ways to do one task and “n” ways to do another task, both of which cannot be done simultaneously, then there are “m + n” ways to choose one of these tasks.

• When facing a choice between two mutually exclusive options (A and B), the total number of ways to make the choice is the sum of the number of ways for each option i.e (m+n).

For example:

• If you can wear either a redshirt(A) in 5 ways(m) or a blueshirt(B) in 3 ways(n), then the total number of ways to choose a shirt is(m+n)= 5 + 3 = 8 ways.
• If you can travel to a destination either by car in 10 ways or by train in 6 ways, then the total number of ways to travel is 10 + 6 = 16 ways.

Product Rule Principle

The Product Rule Principle, also known as the Multiplication Principle, is a fundamental counting principle in combinatorics.

• It states that if there are “m” ways to do one task and “n” ways to do another independent task, then there are “m * n” ways to perform both tasks together.

• If a task can be accomplished by performing operation A in “m” ways and operation B in “n” independent ways, then the total number of ways to perform both tasks is “m * n.”

For example:

• If you have 4 shirts and 3 pairs of pants, then the total number of outfits you can create by choosing one shirt and one pair of pants is 4 * 3 = 12 outfits.
• If you can order a pizza with 5 different toppings and a drink with 4 choices, then the total number of meal combinations is 5 * 4 = 20 combinations.

→ The Pigeonhole Principle:

The pigeonhole principle (also known as the Dirichlet box principle) is a counting principle that states that if we have n pigeons and k pigeonholes, where n > k, then at least one pigeonhole must contain more than one pigeon.

Proof:

We use proof by contradiction here. Suppose that k+1 or more boxes are placed into k boxes and no boxes contain more than one object in it. If there are k boxes then there must be k objects such that there are no two objects in a box. This contradicts our assumptions. So there is at least one box containing two or more of the objects.

→ Generalized Pigeonhole Principle:

If n pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer, then at least one pigeonhole is occupied by k+1 or more pigeons.

Example:

Q). If 9 books are to be kept in 4 shelves, there must be at least one shelf which contains at least 3 books.
solution:-

The nine books can be thought of as pigeons and four shelves as pigeonholes. Then, n=4 (Pigeonholes) kn+1=9 (Pigeons) k*4+1=9 ∴k=2 So, at least 1 pigeonhole i.e. shelf is occupied by k+1=2+1=3 books.

→ Permutation:

A permutation is an arrangement of objects in a specific order.

• In other words, permutations refer to the different ways that a set of items can be rearranged while maintaining the distinctness and order of the items.

• Permutations are used to count the number of possible orders or sequences that a set of items can be placed in.

For example,
The permutations of the letters “A,” “B,” and “C” would include “ABC,” “ACB,” “BAC,” “BCA,” “CAB,” and “CBA.”

• Note: An ordered arrangement of r objects from a set of n objects is called as r-permutation of n objects. It is denoted by P(n,r) or ⁿP_r.

→ The formula to calculate the number of permutations is:

Q). In a hostel, there are 7 doors, In how many ways can a student enter the hostel and come out by different door?

solution:

A student can enter the hostel in 7 different ways. Since, he has to come out by a different doors, he can come out the hostel in (7-1=6 ways). So, by multiplication principle of counting the student can enter and exit the hostel in 7*6=42 different ways

→ Permutation without Repetitions:

The total number of permutation of a set of n distinct objects taken r at a time is given by :

→ Permutation with Repetitions:

The permutation of n objects taken all at a time, when there are P objects of one kind , q objects of second kind, r objects are of a third kind, is:

Q). In how many ways can the letters of the word “PROBABILITY” be arranged?

solution:

In the word “PROBABILITY“, there are 11 letters in which, no. of B = 2 no of I = 2. Thus, n=11,p=2,q=2 so, the required number of permutations: = n!/p!q! =11!/2!2! =11!/4 =9979200

→ Circular Permutation:

A circular permutation is an arrangement of objects in a circle rather than in a straight line.

• The number of ways of arranging n unlike objects in a ring when clockwise and anticlockwise arrangements are different is (n-1)! .

Note:
if the clockwise and anticlockwise arrangements are not distinct as in the case of necklace of beads and beads into a bracelet, then the required number of arrangements in a circle will be:

Q). In how many ways can the numbers on a clock face be arranged?

solution:

In a clock face there are 12 numbers. So they can be arranged in (12-1)!=11! ways

→ Combination:

A combination is a selection of objects from a set without regard to the order of selection.

• Combinations refer to the different ways that a subset of items can be chosen from a larger set, without considering the arrangement or order of the selected items.

• It is denoted by C(n,r) or ⁿC_r.

Formula:

→ Binomial Theorem:

The Binomial Theorem is a fundamental theorem that provides a formula for expanding the powers of a binomial expression.

Let x and y be two variables and n be non-negative interger then the binomial theorem for positive index n states that,

(a+x)n = C(n,0)an + C(n,1)an-1x + C(n,2)an-2x2 +…..+ C(n,n)xn

⁘ General Term of Binomial expansion of (a+x)ⁿ

The general term of the binomial expansion (a+x)ⁿ is denoted by t_r+1 and given by:

tr+1 = C(n,r) an-rxr

Note: if the expansion is (a-x)ⁿ , then its general term is given by:

tr+1 = C(n,r) an-rxr .(-1)r = (-1)r C(n,r) an-rxr

⁘ Middle Term

• When we expand (a+x)ⁿ , then we always get n+1 term in the expansion of (a+x)ⁿ.
• Therefore, if n is even then (n+1) will be odd and the expansion contains single middle term.
• Similarly, if n is odd then n+1 will be even and the expansion contains two middle terms.

→ Pascal`s Identity and Triangle:

Pascal’s Identity is a mathematical relationship that is closely associated with Pascal’s Triangle.

• It states that the sum of two adjacent entries in Pascal’s Triangle is equal to the entry immediately below them. Mathematically, it can be expressed as:

Pascal’s Triangle is a triangular array of numbers where the outer edges are filled with ones, and each interior number is the sum of the two numbers directly above it.

Q). Write down the expansion of (1+y)⁶, using Pascal`s theorem.

solution:

∴ (1+y)6 = 1(1)6 + 6(1)5y + 15(1)4y2 + 20(1)3y3+ 15(1)2y4 + 6(1)y5 + 1(1)0y6 = 1+6y+15y2+20y3+15y4+6y5+y6

The Inclusio-Exclusion Principle:

The Inclusion-Exclusion Principle is a fundamental concept in combinatorics and set theory. It provides a method for calculating the size of the union of multiple sets by accounting for overlaps and intersections between those sets.

→ Recurrence Relation:

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms.

• In other words, it is an equation that tells us how to calculate the next term in a sequence based on the previous terms.

For example, the Fibonacci sequence is defined by the recurrence relation

Fn = Fn-1 + Fn-2
where F0 = 0 and F1 = 1. This means that the first two terms of the Fibonacci sequence are 0 and 1, and the next term is equal to the sum of the previous two terms.

• Recurrence relations are used in a variety of applications, including:

• Algorithms and data structures
• Combinatorics
• Graph theory
• Number theory
• Computer science
• Engineering
• Physics
• Economics
• Biology

Here are some specific examples of how recurrence relations are used in these applications:

• In algorithms and data structures, recurrence relations are used to analyze the time and space complexity of algorithms.

• In combinatorics, recurrence relations are used to count the number of possible arrangements or combinations of objects.

• In graph theory, recurrence relations are used to solve problems such as finding the shortest path between two vertices in a graph.

• In number theory, recurrence relations are used to study the properties of numbers, such as prime numbers.

• In computer science, recurrence relations are used to implement algorithms such as sorting and searching.

• In engineering, recurrence relations are used to model physical systems such as electrical circuits and mechanical systems.

• In physics, recurrence relations are used to study the behavior of waves and particles.

• In biology, recurrence relations are used to model the growth of populations and the spread of diseases.

→ History

Graph Theory was introduced by the famous Swiss mathematician named Leonhard Euler, to solve many mathematical problems by constructing graphs based on given data or a set of points.

• The graphical representation shows different types of data in the form of bar graphs, frequency tables, line graphs, circle graphs, line plots, etc.

→ Introduction to Graph:

Graph is a discrete structure consisting of vertices and edges connecting the vertices.

• It is used to create a pairwise relationship between objects.

→ Definition of Graph Theory:

Graph Theory is the study of points and lines. In Mathematics, it is a sub-field that deals with the study of graphs.

• It is a pictorial representation that represents the Mathematical truth.
• It is the study of relationship between the vertices (nodes) and edges (lines).

» Formally, a graph is denoted as a pair G(V, E).

Where V represents the finite set vertices and E represents the finite set edges.

• Therefore, we can say a graph includes non-empty set of vertices V and set of edges E.

Example
‣ Suppose, a Graph G=(V,E),

where Vertices, V={a,b,c,d}
Edges, E={{a,b},{a,c},{b,c},{c,d}}

Simple Graph:

A graph G(V,E) is said to be simple if G has no loops and no parallel edges.

Multigraph:

A graph will be known as a multi-graph if the same sets of vertices contain multiple edges. In this type of graph, we can form a minimum of one loop or more than one edge.

Directed Graph:

A directed graph, or digraph, is a graph in which the edges have a direction. This means that each edge points from one vertex to another vertex.

Undirected Graph:

An undirected graph, on the other hand, is a graph in which the edges do not have a direction. This means that each edge connects two vertices, but it does not matter which vertex the edge is pointing from.

→ Graph terminology:

» Vertex:

A vertex (also called a node or a point) is a basic unit in a graph. It represents an object in the system that is being modeled.

» Edge:

An edge (also called a link or a line) is a connection between two vertices in a graph. It represents a relationship between the two objects that the vertices represent.

» Adjacent vertices:

Two vertices are adjacent if they are connected by an edge.

» Degree of a vertex:

The degree of a vertex is the number of edges that are connected to it.

• Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex and if the degree of a vertex is odd, the vertex is called an odd vertex.

• Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the above graph the degree of the graph is 3.

• The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal to twice the number of edges.

» Path:

A path is a sequence of vertices that are connected by edges, where no vertex is repeated.

» Cycle:

A cycle is a path that starts and ends at the same vertex.

» Connected graph:

A connected graph is a graph in which every pair of vertices is connected by a path.

» Weighted graph:

A weighted graph is a graph in which each edge has a weight associated with it. The weight can represent the distance between the two vertices, the cost of traveling between the two vertices, or some other measure of the relationship between the two objects that the vertices represent.

Special Types of Graph:

• Trivial Graph
• Complete Graph
• Regular Graph
• Bipartite Graph
• Complete Bipartite Graph
• Cycle Graph
• Wheel Graph
• Platonic Graph

‣ Trivial Graph:

A trivial graph is a graph with only one vertex and no edges. It is the simplest possible graph.

Figure:

‣ Complete Graph:

A graph G is said to be complete if there exists exactly one edge between any pair of vertices in G.

• The complete graph with n vertices is denoted by k_n.

‣ Regular Graph:

A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of degree r, the degree of each vertex of G is r.

• In above figure, k2, k3, k4, k5, k6, k7 are 2-regular,

‣ Bipartite Graph:

A bipartite graph is a graph in which the vertices can be divided into two sets, such that every edge connects a vertex in one set to a vertex in the other set.

• In above figure, bipartite sets are: {1,2,3,4,5} and {A,B,C,D,E}

‣ Complete Bipartite Graph:

A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to every single vertex in the second set. The complete bipartite graph is denoted by K_m,n where the graph G contains m vertices in the first set and x vertices in the second set.

‣ Cycle Graph:

A cycle graph is a graph that consists of a single cycle. In other words, it is a graph in which every vertex is connected to exactly two other vertices, and there are no edges that connect vertices that are already connected by another edge.

• Each vertex in the above figure is connected to exactly two other vertices by edges.

‣ Wheel Graph:

A wheel graph is a graph that consists of a single vertex connected to all other vertices in the graph by an edge. The other vertices in the graph are called the rim of the wheel.

• The vertex in the center of the diagram is the hub of the wheel, and the other vertices are the rim of the wheel.

‣ Platonic Graph:

The graph formed by the vertices and edges of five regular platonic– the tetrahedron, octahedron, cube, dodecahedron, and icosahedron are called the platonic graphs.

→ Representation of Graph:

In graph theory, a graph representation is a technique to store graph into the memory of computer.

• There are mainly three ways to represent a graph −

• Adjacency Matrix
• Incidence Matrix
• Adjacency List

‣ Adjacency Matrix:

Let G=(V,E) be a graph with n vertices: v₁, v₂, v₃, …… V_n. The adjacency matrix of G with respect to given ordered list of vertices is a nxn matrix denoted by A(G)=(a_ij)_nxn.
such that,

Undirected graph representation

Directed graph represenation

In the above examples, 1 represents an edge from row vertex to column vertex, and 0 represents no edge from row vertex to column vertex.

Q). Find the adjacency matrix M_A of undirected graph G shown in Fig:

Solution:
Since graph G consist of four vertices. Therefore, the adjacency matrix wills a 4 x 4 matrix. The adjacency matrix is as follows in fig:

‣ Incidence Matrix:

Let G be a graph with vertices v₁, v₂,…. v_m and edges e₁, e₂,… e_n. The incidence matrix I(G) of graph G is a mxn matrix with I(G) = (m_ij)_mxn.
such that,

Q). Consider the undirected graph G as shown in fig. Find its incidence matrix MI.

The undirected graph consists of four vertices and five edges. Therefore, the incidence matrix is an 4 x 5 matrix, which is shown in Fig:

‣ Adjacency List:

An adjacency list provides a collection of the combinations of connected vertices in a graph.

This type of graph is suitable for the undirected graphs without multiple edges, and directed graphs.

UnDirected Graph fig:

Directed Graph fig:

→ Graph Isomorphism:

The isomorphism graph can be described as a graph in which a single graph can have more than one form. That means two different graphs can have the same number of edges, vertices, and same edges connectivity. These types of graphs are known as isomorphism graphs.

The example of an isomorphism graph is described as follows:

In above figure, The same graph is represented in more than one form.

Number of vertices of graph (a) must be equal to graph (b), i.e., one to one correspondence some goes for edges.

» Conditions for graph isomorphism

Any two graphs will be known as isomorphism if they satisfy the following four conditions:

• There will be an equal number of vertices in the given graphs.
• There will be an equal number of edges in the given graphs.
• There will be an equal amount of degree sequence in the given graphs.
• If the first graph is forming a cycle of length k with the help of vertices {v1, v2, v3, …. vk}, then another graph must also form the same cycle of the same length k with the help of vertices {v1, v2, v3, …. vk}.

→ Connectivity:

Connectivity is a basic concept of graph theory. It defines whether a graph is connected or disconnected. Without connectivity, it is not possible to traverse a graph from one vertex to another vertex.

• A graph is said to be connected graph if there is a path between every pair of vertex. From every vertex to any other vertex there must be some path to traverse. This is called the connectivity of a graph.

• A graph is said to be disconnected, if there exists multiple disconnected vertices and edges.
Graph connectivity theories are essential in network applications, routing transportation networks, network tolerance etc.

Example of connected Graph:

In the above example, it is possible to travel from one vertex to another vertex. Here, we can traverse from vertex B to H using the path B -> A -> D -> F -> E -> H. Hence it is a connected graph.

Example of disconnected Graph:

In the above example, it is not possible to traverse from vertex B to H because there is no path between them directly or indirectly. Hence, it is a disconnected graph.

Walk:

A walk can be defined as a sequence of edges and vertices of a graph. When we have a graph and traverse it, then that traverse will be known as a walk.

In a walk, there can be repeated edges and vertices.

The number of edges which is covered in a walk will be known as the Length of the walk.

There are two types of the walk, which are described as follows:

Open walk
Closed walk

For example: In this example, we have a graph, which is described as follows:

In the above graph, there can be many walks, but some of them are described as follows:

Trail:

A trail is a walk in which no edge is repeated. The vertices can be repeated.

Path:

A walk in which no vertices and edges are repeated is called a path.

So for a path, the following two points are important, which are described as follows:

Edges cannot be repeated
Vertex cannot be repeated

In the above graph, there is a path, which is described as follows:

Circuit:

A closed trial which contains at least three edges is called a circuit.

So for a circuit, the following two points are important, which are described as follows:

Edges cannot be repeated
Vertex can be repeated

In the above graph, there is a circuit, which is described as follows:

Cycle:

A cycle is a circuit in which no vertex is repeated other than the starting and ending vertices.

Connectedness in Directed Graph:

Connectedness in Undirected Graph:

Eulerian Path:

An Euler path is a path that uses every edge in a graph with no repeats. Being a path, it does not have to return to the starting vertex.

If the path starts and ends at the same vertex, then it is called an Euler circuit.

Eulerian Circuit:

An Euler circuit is a circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex.

Hamiltonian Path:

A Hamiltonian path also visits every vertex once with no repeats, but does not have to start and end at the same vertex.

Hamiltonian Circuit:

A Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex.

Shortest-path problem:

There are several different algorithm to find the shortest path between two vertices in a wighted graph.

Some of them are explained below:

Dijkstra`s Algorithm:

Dijkstra’s algorithm is a greedy algorithm for finding the shortest path between a single source node and all other nodes in a weighted graph. It was developed by Edsger W. Dijkstra in 1956 and published three years later.

Travelling salesman problem:

The traveling salesman problem (TSP) is a well-known optimization problem in graph theory that involves finding the shortest possible route that visits each city in a given list exactly once and returns to the starting city.

Nearest Neighbour Method:

The nearest neighbour algorithm was one of the first algorithms used to solve the travelling salesman problem approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited.

This procedure gives reasonably good results for the travelling salesman problem.

The method is as follows:

Step1: Select an arbitrary vertex and find the vertex that is nearest to this starting vertex to form an initial path of one edge.

Step2: Let v denote the latest vertex that was added to the path. Now, among the result of the vertices that are not in the path, select the closest one to v and add the path, the edge-connecting v and this vertex. Repeat this step until all the vertices of graph G are included in the path.

Step3: Join starting vertex and the last vertex added by an edge and form the circuit.

Example: Use the nearest-neighbor method to solve the following travelling salesman problem, for the graph shown in fig starting at vertex v1.

Solution: We have to start with vertex v₁. By using the nearest neighbor method, vertex by vertex construction of the tour or Hamiltonian circuit is shown in fig:

The total distance of this route is 18.

→ Planar Graph:

A graph is said to be planar if it can be drawn in a plane so that no edge cross.

Example: The graph shown in fig is planar graph.

• Region of a Graph:

Consider a planar graph G=(V,E).A region is defined to be an area of the plane that is bounded by edges and cannot be further subdivided.

• A planar graph divides the plans into one or more regions. One of these regions will be infinite.

• Finite Region:

If the area of the region is finite, then that region is called a finite region.

• Infinite Region:

If the area of the region is infinite, that region is called a infinite region.

Note: A planar graph has only one infinite region.

Example: Consider the graph shown in Fig.
Determine the number of regions, finite regions and an infinite region.

Solution: There are five regions in the above graph, i.e. r₁,r₂,r₃,r₄,r₅.

There are four finite regions in the graph, i.e., r₂,r₃,r₄,r₅.

There is only one finite region, i.e., r₁

» Applications of Planar Graph:

Planar graphs have many applications in discrete mathematics and computer science.

Here are a few examples:

• Circuit layout
• Network routing
• Map coloring
• Graph drawing

Non-planar graph:

A graph is said to be non planar if it cannot be drawn in a plane so that no edge cross.

Example: The graphs shown in fig are non planar graphs.

→ Graph Coloring:

Graph coloring can be described as a process of assigning colors to the vertices of a graph.

• In this, the same color should not be used to fill the two adjacent vertices.
• We can also call graph coloring as Vertex Coloring.

• In graph coloring, we have to take care that a graph must not contain any edge whose end vertices are colored by the same color. This type of graph is known as the Properly colored graph.

Example of Graph coloring

In this graph, we are showing the properly colored graph, which is described as follows:

The above graph contains some points, which are described as follows:

• The same color cannot be used to color the two adjacent vertices.
• Hence, we can call it as a properly colored graph.

» Applications of Graph Coloring:

There are various applications of graph coloring.

• Some of their important applications are described as follows:

• Assignment
• Map coloring
• Scheduling the tasks
• Sudoku
• Prepare time table
• Conflict resolution

→ Introduction to Tree:

A tree is a connected, undirected graph with no cycles.

• This means that it is possible to travel from any vertex in the tree to any other vertex by following the edges of the tree, but there is no path that starts and ends at the same vertex and follows only distinct edges.

• The tree consisting of a single vertex with no edges is called the trivial tree or the degenerate tree.

→ Properties of Trees:

• There is only one path between each pair of vertices of a tree.
• A tree T with n vertices has n-1 edges.
• In any tree G, there are at least two pendant vertices
• A forest G with n vertices has n-k edges, where k is the number of components of G.

→ Tree Terminologies:

• Node: Each data item in a tree is called a node. It is the basic structure in a tree.

• Root: The root is the top data item (node) in a tree. It has no parent nodes.

• Degree of a node: The degree of a node is the number of child nodes that it has.

• Degree of a tree: The degree of a tree is the maximum degree of any node in the tree.

• Terminal node(s): A terminal node is a node that has no child nodes.

• Non-terminal node(s): A non-terminal node is a node that has at least one child node.

• Siblings: Two nodes are siblings if they have the same parent node.

• Level: The level of a node is the number of edges from the root node to that node.

• Edge: An edge is a connection between two nodes in a tree.

• Path: A path is a sequence of nodes and edges that connects two nodes in a tree.

• Depth: The depth of a node is the length of the longest path from the root node to that node.

• Forest: A forest is a set of two or more disjoint trees.

→ Rooted Trees:

A rooted tree is a tree in which one vertex is designated as the root.

• They are often used to represent hierarchical data structures, such as file systems, family trees, and organization charts. They can also be used to represent search algorithms, such as binary search trees.

→ Trees as model:

Application of Trees:

The various application of tree is described as follows:

• Binary Search Tree
• Decision Tree
• Game Tree
• Prefix Codes

Binary Search Tree:

A binary tree is a finite set of elements that is either empty or partitioned into three disjoint subsets.

• The first subset contains the single elements called root of the tree.

Note: The binary tree is so named because each node can have at most two child nodes.

Strictly Binary Tree:

A binary tree is called strictly binary tree if every non-leaf node in a binary tree has non-empty left and right sub-tree.

Complete(Full) Binary Tree:

A strictly binary tree in which all the leaf nodes lies on same level is called complete binary tree.

Decision Tree:

A decision tree is a tree-like graph or model that uses a branching process to help make decisions.

• Each internal node in the tree represents a decision, and each branch represents a possible outcome of that decision. The leaf nodes of the tree represent the final outcomes of the decision process.

Game Tree:

A game tree is a tree-like graph that represents all possible moves in a game.

• The nodes of the tree represent the game states, and the edges of the tree represent the moves that can be made from one state to another.

Prefix Codes:

A prefix code is a code in which no codeword is a prefix of any other codeword. This means that no codeword can be formed by simply adding more bits to another codeword.

• Prefix codes are often used to encode data in a way that is efficient and minimizes the number of bits required. For example, prefix codes are used to encode text in Morse code and Huffman coding.

• One way to construct a prefix code is to use a binary tree. Each node in the tree represents a codeword, and the path from the root node to a leaf node represents the codeword for that leaf node.

Tree Traversal:

Tree traversal is a process of visiting all the nodes of a tree in a systematic order.

‣ There are three standard methods to traverse the binary trees.
These are as follows:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal

Preorder Traversal:

Preorder traversal is a tree traversal algorithm that visits the root node of a tree first, followed by the nodes in the left subtree in preorder, and then the nodes in the right subtree in preorder.

Steps:

• If root =NULL, return
• Visit the root
• Traverse the left subtree in preorder
• Traverse the right subtree in preorder

Inorder Traversal:

Inorder traversal is a tree traversal algorithm that visits the nodes in the left subtree of a tree in inorder, followed by the root node, and then the nodes in the right subtree in inorder.

Steps:

• If root=NULL, retrurn
• Traverse the left subtree in inorder
• Visit the root
• Traverse the right subtree in inorder

Postorder Traversal:

Postorder traversal is a tree traversal algorithm that visits the nodes in the left subtree of a tree in postorder, followed by the nodes in the right subtree in postorder, and then the root node.

Steps:

• If root=NULL, return
• Traverse the left subtree in postorder
• Traverse the right subtree in postorder
• Visit the root

Q). Determine the preorder, postorder and inorder traversal of the binary tree as shown in fig:

Depth-first search (DFS)

DFS works by starting at the root node of a tree and exploring all of the nodes in the left subtree of the root node before moving on to the right subtree. This process is then repeated for each of the child nodes of the root node, and so on.

• DFS is a good algorithm for finding all of the paths between two nodes in a tree, or for finding all of the nodes in a tree that are reachable from a given node. It is also a good algorithm for finding the topological order of a directed acyclic graph (DAG).

Breadth-first search (BFS)

BFS works by starting at the root node of a tree and exploring all of the nodes at level 1 before moving on to level 2, and so on. This means that BFS visits all of the nodes at the same level before moving on to the next level.

• BFS is a good algorithm for finding the shortest path between two nodes in a tree, or for finding all of the nodes in a tree that are within a certain distance of the root node. It is also a good algorithm for finding the minimum spanning tree of a graph.

Applications of BFS and DFS

BFS and DFS are both powerful algorithms with a variety of applications

Here are a few examples:

BFS:

• Finding the shortest path between two nodes in a graph
• Finding all of the nodes in a graph that are within a certain distance of the root node
• Finding the minimum spanning tree of a graph
• Testing for bipartiteness in a graph

DFS:

• Finding all of the paths between two nodes in a graph
• Finding all of the nodes in a graph that are reachable from a given node
• Finding the topological order of a directed acyclic graph (DAG)
• Detecting cycles in a graph
• Finding strongly connected components in a graph

Spanning Tree:

A spanning tree of a connected graph is a subgraph that includes all of the vertices of the original graph and is also a tree. This means that the spanning tree has no circuits and is connected.

• A subgraph T of a connected graph G is called spanning tree of G if T is a tree and T include all vertices of G.

Minimum Spanning Tree:

A minimum spanning tree (MST) of a connected, undirected graph is a subset of the edges of the graph that connects all the vertices of the graph with the minimum total weight.

• The weight of an edge can be any metric, such as the length of the edge, the cost of building the edge, or the time it takes to travel across the edge.

Kruskal’s algorithm:

Kruskal’s algorithm is a greedy algorithm that finds the minimum spanning tree (MST) of a connected, undirected graph. It works by sorting the edges of the graph by weight and then adding them to the tree in ascending order until all of the vertices have been added. If adding an edge would create a cycle in the tree, the edge is not added.

• Input the given connected weighted graph G with n vertices whose minimum spanning tree T, we want to find.
• Order all the edges of the graph G according to increasing weights.
• Initialize T with all vertices but do include an edge.
• Add each of the graphs G in T which does not form a cycle until n-1 edges are added.

Q): Determine the minimum spanning tree of the weighted graph shown in fig:

Solution: Using kruskal’s algorithm arrange all the edges of the weighted graph in increasing order and initialize spanning tree T with all the six vertices of G. Now start adding the edges of G in T which do not form a cycle and having minimum weights until five edges are not added as there are six vertices.

Prim`s Algorithm:

Prim’s algorithm is a greedy algorithm that finds the minimum spanning tree (MST) of a connected, undirected graph. It works by starting at a root node and greedily adding edges to the tree until all of the vertices have been added. At each step, Prim’s algorithm adds the lightest edge that connects a vertex in the tree to a vertex that is not in the tree.

→ Sum Rule Principle:

Q1). You have two shirts (blue and red) and three pairs of pants (black, khaki, and jeans). How many different outfits can you create by choosing one shirt and one pair of pants?

solution:

There are 2 ways to choose a shirt (blue or red). There are 3 ways to choose a pair of pants (black, khaki, or jeans). By the sum rule, you can create 2+3=5 different outfits.

Q2). In a restaurant, you can order a sandwich or a salad as your main course and a soda or water as your beverage. How many different combinations of main course and beverage can you order?

solution:

There are 2 ways to choose a main course (sandwich or salad). There are 2 ways to choose a beverage (soda or water). By the sum rule, you can order 2+2=4 different combinations.

Q3). A student needs to select one elective course from a list of 4 mathematics courses and one elective course from a list of 3 computer science courses. How many different combinations of elective courses can the student choose?

solution:

There are 4 ways to choose a mathematics course. There are 3 ways to choose a computer science course. By the sum rule, the student can choose 4+3=7 different combinations of elective courses.

Q4). You are planning a weekend trip, and you can choose to visit one of two cities (City A or City B) and stay in one of three hotels (Hotel X, Hotel Y, or Hotel Z). How many different options do you have for your weekend trip?

solution:

There are 2 ways to choose a city (City A or City B). There are 3 ways to choose a hotel (Hotel X, Hotel Y, or Hotel Z). By the sum rule, you have 2+3=5 different options for your weekend trip.