Subjects | Gate Vidyalay

Category: Subjects

Walk in Graph Theory | Path | Trail | Cycle | Circuit

Graph Theory

Walk in Graph Theory-

In graph theory,

A walk is defined as a finite length alternating sequence of vertices and edges.
The total number of edges covered in a walk is called as Length of the Walk.

Walk in Graph Theory Example-

Consider the following graph-

In this graph, few examples of walk are-

a , b , c , e , d (Length = 4)
d , b , a , c , e , d , e , c (Length = 7)
e , c , b , a , c , e , d (Length = 6)

Open Walk in Graph Theory-

In graph theory, a walk is called as an Open walk if-

Length of the walk is greater than zero
And the vertices at which the walk starts and ends are different.

Closed Walk in Graph Theory-

In graph theory, a walk is called as a Closed walk if-

Length of the walk is greater than zero
And the vertices at which the walk starts and ends are same.

NOTE

It is important to note the following points-

If length of the walk = 0, then it is called as a Trivial Walk.
Both vertices and edges can repeat in a walk whether it is an open walk or a closed walk.

Path in Graph Theory-

In graph theory, a path is defined as an open walk in which-

Neither vertices (except possibly the starting and ending vertices) are allowed to repeat.
Nor edges are allowed to repeat.

Cycle in Graph Theory-

In graph theory, a cycle is defined as a closed walk in which-

Neither vertices (except possibly the starting and ending vertices) are allowed to repeat.
Nor edges are allowed to repeat.

In graph theory, a closed path is called as a cycle.

Trail in Graph Theory-

In graph theory, a trail is defined as an open walk in which-

Vertices may repeat.
But edges are not allowed to repeat.

Circuit in Graph Theory-

In graph theory, a circuit is defined as a closed walk in which-

Vertices may repeat.
But edges are not allowed to repeat.

In graph theory, a closed trail is called as a circuit.

NOTE

It is important to note the following points-

Every path is a trail but every trail need not be a path.
Every cycle is a circuit but every circuit need not be a cycle.
For directed graphs, we put term “directed” in front of all the terms defined above.

Important Chart-

The following chart summarizes the above definitions and is helpful in remembering them-

Also Read- Types of Graphs in Graph Theory

PRACTICE PROBLEMS BASED ON WALK IN GRAPH THEORY-

Problem-01:

Consider the following graph-

Decide which of the following sequences of vertices determine walks.

For those that are walks, decide whether it is a circuit, a path, a cycle or a trail.

a , b , g , f , c , b
b , g , f , c , b , g , a
c , e , f , c
c , e , f , c , e
a , b , f , a
f , d , e , c , b

Solution-

Trail
Walk
Cycle
Walk
Not a walk
Path

Problem-02:

Consider the following graph-

Consider the following sequences of vertices and answer the questions that follow-

x , v , y , w , v
x , u , x , u , x
x , u , v , y , x
x , v , y , w , v , u , x

Which of the above given sequences are directed walks?
What are the lengths of directed walks?
Which directed walks are also directed paths?
Which directed walks are also directed cycles?

Solution-

Part-01:

Only (A) and (B) are the directed walks.
(C) is not a directed walk since there exists no arc from vertex u to vertex v.
(D) is not a directed walk since there exists no arc from vertex v to vertex u.

Part-02:

Both the directed walks (A) and (B) have length = 4.

Part-03:

Neither (A) nor (B) are directed paths.
This is because vertices repeat in both of them.
Vertex v repeats in Walk (A) and vertex u repeats in walk (B).

Part-04:

Neither of them are directed cycles.
Walk (A) does not represent a directed cycle because its starting and ending vertices are not same.
Walk (B) does not represent a directed cycle because it repeats vertices/edges.

Problem-03:

Consider the following graph-

Observe the given sequences and predict the nature of walk in each case-

v1e1v2e2v3e2v2
v4e7v1e1v2e2v3e3v4e4v5
v1e1v2e2v3e3v4e4v5
v1e1v2e2v3e3v4e7v1
v6e5v5e4v4e3v3e2v2e1v1e7v4e6v6

Solution-

Open walk
Trail (Not a path because vertex v4 is repeated)
Path
Cycle
Circuit (Not a cycle because vertex v4 is repeated)

To gain better understanding about Walk in Graph Theory,

Watch this Video Lecture

Next Article- Graph Coloring

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Complement of Graph in Graph Theory | Example | Problems

Graph Theory

Complement Of Graph-

Complement of a simple graph G is a simple graph G’ having-

All the vertices of G.
An edge between two vertices v and w iff there exists no edge between v and w in the original graph G.

Complement Of Graph Example-

The following example shows a graph G and its complement graph G’-

Relationship Between G & G’-

The following relationship exists between a graph G and its complement graph G’-

1. Number of vertices in G = Number of vertices in G’.

|V(G)| = |V(G’)|

2. The sum of total number of edges in G and G’ is equal to the total number of edges in a complete graph.

|E(G)| + |E(G’)|

= C(n,2)

= n(n-1) / 2

where n = total number of vertices in the graph

Important Terms-

It is important to note the following terms-

Order of graph = Total number of vertices in the graph
Size of graph = Total number of edges in the graph

Also Read- Types of Graphs in Graph Theory

PRACTICE PROBLEMS BASED ON COMPLEMENT OF GRAPH IN GRAPH THEORY-

Problem-01:

A simple graph G has 10 vertices and 21 edges. Find total number of edges in its complement graph G’.

Solution-

Given-

Number of edges in graph G, |E(G)| = 21
Number of vertices in graph G, n = 10

We know |E(G)| + |E(G’)| = n(n-1) / 2.

Substituting the values, we get-

21 + |E(G’)| = 10 x (10-1) / 2

|E(G’)| = 45 – 21

∴ |E(G’)| = 24

Thus, Number of edges in complement graph G’ = 24.

Problem-02:

A simple graph G has 30 edges and its complement graph G’ has 36 edges. Find number of vertices in G.

Solution-

Given-

Number of edges in graph G, |E(G)| = 30
Number of edges in graph G’, |E(G’)| = 36

We know |E(G)| + |E(G’)| = n(n-1) / 2.

Substituting the values, we get-

30 + 36 = n(n-1) / 2

n(n-1) = 132

n² – n – 132 = 0

Solving this quadratic equation, we get n = 12.

Thus, Number of vertices in graph G = 12.

Problem-03:

Let G be a simple graph of order n. If the size of G is 56 and the size of G’ is 80. What is n?

Solution-

Size of a graph = Number of edges in the graph.

Given-

Number of edges in graph G, |E(G)| = 56
Number of edges in graph G’, |E(G’)| = 80

We know |E(G)| + |E(G’)| = n(n-1) / 2.

Substituting the values, we get-

56 + 80 = n(n-1) / 2

n(n-1) = 272

n² – n – 272 = 0

Solving this quadratic equation, we get n = 17.

Thus, Number of vertices in graph G = 17.

In other words, Order of graph G = 17.

To gain better understanding about Complement Of Graph,

Watch this Video Lecture

Next Article- Walks in Graph Theory

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Recoverability in DBMS | Recoverable Schedule

Database Management System

Schedules in DBMS-

Before you go through this article, make sure that you have gone through the previous article on Schedules in DBMS.

We have discussed-

A schedule is the order in which the operations of multiple transactions appear for execution.
Non-serial schedules may be serializable or non-serializable.

In this article, we will discuss about Non-Serializable Schedules.

Also read- Serializability in DBMS

Non-Serializable Schedules-

A non-serial schedule which is not serializable is called as a non-serializable schedule.
A non-serializable schedule is not guaranteed to produce the the same effect as produced by some serial schedule on any consistent database.

Characteristics-

Non-serializable schedules-

may or may not be consistent
may or may not be recoverable

Irrecoverable Schedules-

If in a schedule,

A transaction performs a dirty read operation from an uncommitted transaction
And commits before the transaction from which it has read the value

then such a schedule is known as an Irrecoverable Schedule.

Example-

Consider the following schedule-

Here,

T2 performs a dirty read operation.
T2 commits before T1.
T1 fails later and roll backs.
The value that T2 read now stands to be incorrect.
T2 can not recover since it has already committed.

Recoverable Schedules-

If in a schedule,

A transaction performs a dirty read operation from an uncommitted transaction
And its commit operation is delayed till the uncommitted transaction either commits or roll backs

then such a schedule is known as a Recoverable Schedule.

Here,

The commit operation of the transaction that performs the dirty read is delayed.
This ensures that it still has a chance to recover if the uncommitted transaction fails later.

Example-

Consider the following schedule-

Here,

T2 performs a dirty read operation.
The commit operation of T2 is delayed till T1 commits or roll backs.
T1 commits later.
T2 is now allowed to commit.
In case, T1 would have failed, T2 has a chance to recover by rolling back.

Checking Whether a Schedule is Recoverable or Irrecoverable-

Method-01:

Check whether the given schedule is conflict serializable or not.

If the given schedule is conflict serializable, then it is surely recoverable. Stop and report your answer.
If the given schedule is not conflict serializable, then it may or may not be recoverable. Go and check using other methods.

Thumb Rules

All conflict serializable schedules are recoverable.
All recoverable schedules may or may not be conflict serializable.

Method-02:

Check if there exists any dirty read operation.

(Reading from an uncommitted transaction is called as a dirty read)

If there does not exist any dirty read operation, then the schedule is surely recoverable. Stop and report your answer.
If there exists any dirty read operation, then the schedule may or may not be recoverable.

If there exists a dirty read operation, then follow the following cases-

Case-01:

If the commit operation of the transaction performing the dirty read occurs before the commit or abort operation of the transaction which updated the value, then the schedule is irrecoverable.

Case-02:

If the commit operation of the transaction performing the dirty read is delayed till the commit or abort operation of the transaction which updated the value, then the schedule is recoverable.

Thumb Rule

No dirty read means a recoverable schedule.

Next Article- Cascading Schedule | Cascading Rollback | Cascadeless Schedule

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

View Serializability in DBMS

Database Management System

Schedules in DBMS-

Before you go through this article, make sure that you have gone through the previous article on Serializability in DBMS.

We have discussed-

The concept of serializability helps to identify the correct non-serial schedules that maintains the consistency of the database.
There are two types of serializability-

In this article, we will discuss about View Serializability.

View Serializability-

If a given schedule is found to be view equivalent to some serial schedule, then it is called as a view serializable schedule.

Also read- Schedules in DBMS

View Equivalent Schedules-

Consider two schedules S1 and S2 each consisting of two transactions T1 and T2.

Schedules S1 and S2 are called view equivalent if the following three conditions hold true for them-

Condition-01:

For each data item X, if transaction T_i reads X from the database initially in schedule S1, then in schedule S2 also, T_imust perform the initial read of X from the database.

Thumb Rule

“Initial readers must be same for all the data items”.

Condition-02:

If transaction T_i reads a data item that has been updated by the transaction T_j in schedule S1, then in schedule S2 also, transaction T_i must read the same data item that has been updated by the transaction T_j.

Thumb Rule

“Write-read sequence must be same.”.

Condition-03:

For each data item X, if X has been updated at last by transaction T_i in schedule S1, then in schedule S2 also, X must be updated at last by transaction T_i.

Thumb Rule

“Final writers must be same for all the data items”.

Checking Whether a Schedule is View Serializable Or Not-

Method-01:

Check whether the given schedule is conflict serializable or not.

If the given schedule is conflict serializable, then it is surely view serializable. Stop and report your answer.
If the given schedule is not conflict serializable, then it may or may not be view serializable. Go and check using other methods.

Thumb Rules

All conflict serializable schedules are view serializable.
All view serializable schedules may or may not be conflict serializable.

Method-02:

Check if there exists any blind write operation.

(Writing without reading is called as a blind write).

If there does not exist any blind write, then the schedule is surely not view serializable. Stop and report your answer.
If there exists any blind write, then the schedule may or may not be view serializable. Go and check using other methods.

Thumb Rule

No blind write means not a view serializable schedule.

Method-03:

In this method, try finding a view equivalent serial schedule.

By using the above three conditions, write all the dependencies.
Then, draw a graph using those dependencies.
If there exists no cycle in the graph, then the schedule is view serializable otherwise not.

Next Article- Practice Problems On View Serializability

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Conflict Serializability | Practice Problems

Database Management System

Conflict Serializability-

Before you go through this article, make sure that you have gone through the previous article on Conflict Serializability.

We have discussed-

The concept of serializability helps to identify the correct non-serial schedules that will maintain the consistency of the database.
There are two types of serializability-

In this article, we will discuss practice problems based on conflict serializability.

PRACTICE PROBLEMS BASED ON CONFLICT SERIALIZABILITY-

Problem-01:

Check whether the given schedule S is conflict serializable or not-

S : R₁(A) , R₂(A) , R₁(B) , R₂(B) , R₃(B) , W₁(A) , W₂(B)

Solution-

Step-01:

List all the conflicting operations and determine the dependency between the transactions-

R₂(A) , W₁(A) (T₂ → T₁)
R₁(B) , W₂(B) (T₁ → T₂)
R₃(B) , W₂(B) (T₃ → T₂)

Step-02:

Draw the precedence graph-

Clearly, there exists a cycle in the precedence graph.
Therefore, the given schedule S is not conflict serializable.

Problem-02:

Check whether the given schedule S is conflict serializable and recoverable or not-

Solution-

Checking Whether S is Conflict Serializable Or Not-

Step-01:

List all the conflicting operations and determine the dependency between the transactions-

R₂(X) , W₃(X) (T₂ → T₃)
R₂(X) , W₁(X) (T₂ → T₁)
W₃(X) , W₁(X) (T₃ → T₁)
W₃(X) , R₄(X) (T₃ → T₄)
W₁(X) , R₄(X) (T₁ → T₄)
W₂(Y) , R₄(Y) (T₂ → T₄)

Step-02:

Draw the precedence graph-

Clearly, there exists no cycle in the precedence graph.
Therefore, the given schedule S is conflict serializable.

Checking Whether S is Recoverable Or Not-

Conflict serializable schedules are always recoverable.
Therefore, the given schedule S is recoverable.

Alternatively,

There exists no dirty read operation.
This is because all the transactions which update the values commits immediately.
Therefore, the given schedule S is recoverable.
Also, S is a Cascadeless Schedule.

Problem-03:

Check whether the given schedule S is conflict serializable or not. If yes, then determine all the possible serialized schedules-

Solution-

Checking Whether S is Conflict Serializable Or Not-

Step-01:

List all the conflicting operations and determine the dependency between the transactions-

R₄(A) , W₂(A) (T₄ → T₂)
R₃(A) , W₂(A) (T₃ → T₂)
W₁(B) , R₃(B) (T₁ → T₃)
W₁(B) , W₂(B) (T₁ → T₂)
R₃(B) , W₂(B) (T₃ → T₂)

Step-02:

Draw the precedence graph-

Clearly, there exists no cycle in the precedence graph.
Therefore, the given schedule S is conflict serializable.

Finding the Serialized Schedules-

All the possible topological orderings of the above precedence graph will be the possible serialized schedules.
The topological orderings can be found by performing the Topological Sort of the above precedence graph.

After performing the topological sort, the possible serialized schedules are-