Subjects | Gate Vidyalay

Category: Subjects

Euler Graph | Euler Path | Euler Circuit

Types of Graphs-

Before you go through this article, make sure that you have gone through the previous article on various Types of Graphs in Graph Theory.

We have discussed-

A graph is a collection of vertices connected to each other through a set of edges.
The study of graphs is known as Graph Theory.

In this article, we will discuss about Euler Graphs.

Euler Graph-

An Euler graph may be defined as-

Any connected graph is called as an Euler Graph if and only if all its vertices are of even degree.

An Euler Graph is a connected graph that contains an Euler Circuit.

Euler Graph Example-

The following graph is an example of an Euler graph-

Here,

This graph is a connected graph and all its vertices are of even degree.
Therefore, it is an Euler graph.

Alternatively, the above graph contains an Euler circuit BACEDCB, so it is an Euler graph.

Also Read- Planar Graph

Euler Path-

Euler path is also known as Euler Trail or Euler Walk.

If there exists a Trail in the connected graph that contains all the edges of the graph, then that trail is called as an Euler trail.

If there exists a walk in the connected graph that visits every edge of the graph exactly once with or without repeating the vertices, then such a walk is called as an Euler walk.

NOTE

A graph will contain an Euler path if and only if it contains at most two vertices of odd degree.

Euler Path Examples-

Examples of Euler path are as follows-

Euler Circuit-

Euler circuit is also known as Euler Cycle or Euler Tour.

If there exists a Circuit in the connected graph that contains all the edges of the graph, then that circuit is called as an Euler circuit.

If there exists a walk in the connected graph that starts and ends at the same vertex and visits every edge of the graph exactly once with or without repeating the vertices, then such a walk is called as an Euler circuit.

An Euler trail that starts and ends at the same vertex is called as an Euler circuit.

A closed Euler trail is called as an Euler circuit.

NOTE

A graph will contain an Euler circuit if and only if all its vertices are of even degree.

Euler Circuit Examples-

Examples of Euler circuit are as follows-

Semi-Euler Graph-

If a connected graph contains an Euler trail but does not contain an Euler circuit, then such a graph is called as a semi-Euler graph.

Thus, for a graph to be a semi-Euler graph, following two conditions must be satisfied-

Graph must be connected.
Graph must contain an Euler trail.

Example-

Here,

This graph contains an Euler trail BCDBAD.
But it does not contain an Euler circuit.
Therefore, it is a semi-Euler graph.

Also Read- Bipartite Graph

Important Notes-

Note-01:

To check whether any graph is an Euler graph or not, any one of the following two ways may be used-

If the graph is connected and contains an Euler circuit, then it is an Euler graph.
If all the vertices of the graph are of even degree, then it is an Euler graph.

Note-02:

To check whether any graph contains an Euler circuit or not,

Just make sure that all its vertices are of even degree.
If all its vertices are of even degree, then graph contains an Euler circuit otherwise not.

Note-03:

To check whether any graph is a semi-Euler graph or not,

Just make sure that it is connected and contains an Euler trail.
If the graph is connected and contains an Euler trail, then graph is a semi-Euler graph otherwise not.

Note-04:

To check whether any graph contains an Euler trail or not,

Just make sure that the number of vertices in the graph with odd degree are not more than 2.
If the number of vertices with odd degree are at most 2, then graph contains an Euler trail otherwise not.

Note-05:

A graph will definitely contain an Euler trail if it contains an Euler circuit.
A graph may or may not contain an Euler circuit if it contains an Euler trail.

Note-06:

An Euler graph is definitely be a semi-Euler graph.
But a semi-Euler graph may or may not be an Euler graph.

PRACTICE PROBLEMS BASED ON EULER GRAPHS IN GRAPH THEORY-

Problems-

Which of the following is / are Euler Graphs?

Solutions-

If all the vertices of a graph are of even degree, then graph is an Euler Graph otherwise not.

Using the above rule, we have-

A) It is an Euler graph.

B) It is not an Euler graph.

C) It is not an Euler graph.

D) It is not an Euler graph.

E) It is an Euler graph.

F) It is not an Euler graph.

To gain better understanding about Euler Graphs in Graph Theory,

Watch this Video Lecture

Next Article- Hamiltonian Graph

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

How to Find Chromatic Number | Graph Coloring Algorithm

Graph Theory

Chromatic Number-

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

We gave discussed-

Graph Coloring is a process of assigning colors to the vertices of a graph.
It ensures that no two adjacent vertices of the graph are colored with the same color.
Chromatic Number is the minimum number of colors required to properly color any graph.

In this article, we will discuss how to find Chromatic Number of any graph.

Graph Coloring Algorithm-

There exists no efficient algorithm for coloring a graph with minimum number of colors.
Graph Coloring is a NP complete problem.

However, a following greedy algorithm is known for finding the chromatic number of any given graph.

Greedy Algorithm-

Step-01:

Color first vertex with the first color.

Step-02:

Now, consider the remaining (V-1) vertices one by one and do the following-

Color the currently picked vertex with the lowest numbered color if it has not been used to color any of its adjacent vertices.
If it has been used, then choose the next least numbered color.
If all the previously used colors have been used, then assign a new color to the currently picked vertex.

Drawbacks of Greedy Algorithm-

There are following drawbacks of the above Greedy Algorithm-

The above algorithm does not always use minimum number of colors.
The number of colors used sometimes depend on the order in which the vertices are processed.

Also Read- Types of Graphs in Graph Theory

PRACTICE PROBLEMS BASED ON FINDING CHROMATIC NUMBER OF A GRAPH-

Problem-01:

Find chromatic number of the following graph-

Solution-

Applying Greedy Algorithm, we have-

Vertex	a	b	c	d	e	f
Color	C1	C2	C1	C2	C1	C2

From here,

Minimum number of colors used to color the given graph are 2.
Therefore, Chromatic Number of the given graph = 2.

The given graph may be properly colored using 2 colors as shown below-

Problem-02:

Find chromatic number of the following graph-

Solution-

Applying Greedy Algorithm, we have-

Vertex	a	b	c	d	e	f
Color	C1	C2	C2	C3	C3	C1

From here,

Minimum number of colors used to color the given graph are 3.
Therefore, Chromatic Number of the given graph = 3.

The given graph may be properly colored using 3 colors as shown below-

Problem-03:

Find chromatic number of the following graph-

Solution-

Applying Greedy Algorithm, we have-

Vertex	a	b	c	d	e	f	g
Color	C1	C2	C1	C3	C2	C3	C4

From here,

Minimum number of colors used to color the given graph are 4.
Therefore, Chromatic Number of the given graph = 4.

The given graph may be properly colored using 4 colors as shown below-

Problem-04:

Find chromatic number of the following graph-

Solution-

Applying Greedy Algorithm, we have-

Vertex	a	b	c	d	e	f
Color	C1	C2	C3	C1	C2	C3

From here,

Minimum number of colors used to color the given graph are 3.
Therefore, Chromatic Number of the given graph = 3.

The given graph may be properly colored using 3 colors as shown below-

Problem-05:

Find chromatic number of the following graph-

Solution-

Applying Greedy Algorithm,

Minimum number of colors required to color the given graph are 3.
Therefore, Chromatic Number of the given graph = 3.

The given graph may be properly colored using 3 colors as shown below-

To gain better understanding about How to Find Chromatic Number,

Watch this Video Lecture

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Graph Coloring in Graph Theory | Chromatic Number of Graphs

Graph Theory

Graph Coloring-

Graph Coloring is a process of assigning colors to the vertices of a graph

such that no two adjacent vertices of it are assigned the same color.

Graph Coloring is also called as Vertex Coloring.
It ensures that there exists no edge in the graph whose end vertices are colored with the same color.
Such a graph is called as a Properly colored graph.

Graph Coloring Example-

The following graph is an example of a properly colored graph-

In this graph,

No two adjacent vertices are colored with the same color.
Therefore, it is a properly colored graph.

Graph Coloring Applications-

Some important applications of graph coloring are as follows-

Map Coloring
Scheduling the tasks
Preparing Time Table
Assignment
Conflict Resolution
Sudoku

Chromatic Number-

Chromatic Number is the minimum number of colors required to properly color any graph.

Chromatic Number is the minimum number of colors required to color any graph

such that no two adjacent vertices of it are assigned the same color.

Chromatic Number Example-

Consider the following graph-

In this graph,

No two adjacent vertices are colored with the same color.
Minimum number of colors required to properly color the vertices = 3.
Therefore, Chromatic number of this graph = 3.
We can not properly color this graph with less than 3 colors.

Also Read- Types of Graphs in Graph Theory

Chromatic Number Of Graphs-

Chromatic Number of some common types of graphs are as follows-

1. Cycle Graph-

A simple graph of ‘n’ vertices (n>=3) and ‘n’ edges forming a cycle of length ‘n’ is called as a cycle graph.
In a cycle graph, all the vertices are of degree 2.

Chromatic Number

If number of vertices in cycle graph is even, then its chromatic number = 2.
If number of vertices in cycle graph is odd, then its chromatic number = 3.

Examples-

2. Planar Graphs-

A Planar Graph is a graph that can be drawn in a plane such that none of its edges cross each other.

Chromatic Number

Chromatic Number of any Planar Graph

= Less than or equal to 4

Examples-

All the above cycle graphs are also planar graphs.
Chromatic number of each graph is less than or equal to 4.

3. Complete Graphs-

A complete graph is a graph in which every two distinct vertices are joined by exactly one edge.
In a complete graph, each vertex is connected with every other vertex.
So to properly it, as many different colors are needed as there are number of vertices in the given graph.

Chromatic Number

Chromatic Number of any Complete Graph

= Number of vertices in that Complete Graph

Examples-

4. Bipartite Graphs-

A Bipartite Graph consists of two sets of vertices X and Y.
The edges only join vertices in X to vertices in Y, not vertices within a set.

Chromatic Number

Chromatic Number of any Bipartite Graph

= 2

Example-

5. Trees-

A Tree is a special type of connected graph in which there are no circuits.
Every tree is a bipartite graph.
So, chromatic number of a tree with any number of vertices = 2.

Chromatic Number

Chromatic Number of any tree

= 2

Examples-

To gain better understanding about Graph Coloring & Chromatic Number,

Watch this Video Lecture

Next Article- Graph Coloring Algorithm

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Planar Graph in Graph Theory | Planar Graph Example

Graph Theory

Types of Graphs-

Before you go through this article, make sure that you have gone through the previous article on various Types of Graphs in Graph Theory.

We have discussed-

A graph is a collection of vertices connected to each other through a set of edges.
The study of graphs is known as Graph Theory.

In this article, we will discuss about Planar Graphs.

Planar Graph-

A planar graph may be defined as-

In graph theory,

Planar graph is a graph that can be drawn in a plane such that none of its edges cross each other.

Planar Graph Example-

The following graph is an example of a planar graph-

Here,

In this graph, no two edges cross each other.
Therefore, it is a planar graph.

Regions of Plane-

The planar representation of the graph splits the plane into connected areas called as Regions of the plane.

Each region has some degree associated with it given as-

Degree of Interior region = Number of edges enclosing that region
Degree of Exterior region = Number of edges exposed to that region

Example-

Consider the following planar graph-

Here, this planar graph splits the plane into 4 regions- R1, R2, R3 and R4 where-

Degree (R1) = 3
Degree (R2) = 3
Degree (R3) = 3
Degree (R4) = 5

Planar Graph Chromatic Number-

Chromatic Number of any planar graph is always less than or equal to 4.
Thus, any planar graph always requires maximum 4 colors for coloring its vertices.

Planar Graph Properties-

Property-01:

In any planar graph, Sum of degrees of all the vertices = 2 x Total number of edges in the graph

Property-02:

In any planar graph, Sum of degrees of all the regions = 2 x Total number of edges in the graph

Special Cases

Case-01:

In any planar graph, if degree of each region is K, then-

K x |R| = 2 x |E|

Case-02:

In any planar graph, if degree of each region is at least K (>=K), then-

K x |R| <= 2 x |E|

Case-03:

In any planar graph, if degree of each region is at most K (<=K), then-

K x |R| >= 2 x |E|

Property-03:

If G is a connected planar simple graph with ‘e’ edges, ‘v’ vertices and ‘r’ number of regions in the planar representation of G, then-

r = e – v + 2

This is known as Euler’s Formula.

It remains same in all the planar representations of the graph.

Property-04:

If G is a planar graph with k components, then-

r = e – v + (k + 1)

Also Read- Bipartite Graph

PRACTICE PROBLEMS BASED ON PLANAR GRAPH IN GRAPH THEORY-

Problem-01:

Let G be a connected planar simple graph with 25 vertices and 60 edges. Find the number of regions in G.

Solution-

Given-

Number of vertices (v) = 25
Number of edges (e) = 60

By Euler’s formula, we know r = e – v + 2.

Substituting the values, we get-

Number of regions (r)

= 60 – 25 + 2

= 37

Thus, Total number of regions in G = 37.

Problem-02:

Let G be a planar graph with 10 vertices, 3 components and 9 edges. Find the number of regions in G.

Solution-

Given-

Number of vertices (v) = 10
Number of edges (e) = 9
Number of components (k) = 3

By Euler’s formula, we know r = e – v + (k+1).

Substituting the values, we get-

Number of regions (r)

= 9 – 10 + (3+1)

= -1 + 4

= 3

Thus, Total number of regions in G = 3.

Problem-03:

Let G be a connected planar simple graph with 20 vertices and degree of each vertex is 3. Find the number of regions in G.

Solution-

Given-

Number of vertices (v) = 20
Degree of each vertex (d) = 3

Calculating Total Number Of Edges (e)-

By sum of degrees of vertices theorem, we have-

Sum of degrees of all the vertices = 2 x Total number of edges

Number of vertices x Degree of each vertex = 2 x Total number of edges

20 x 3 = 2 x e

∴ e = 30

Thus, Total number of edges in G = 30.

Calculating Total Number Of Regions (r)-

By Euler’s formula, we know r = e – v + 2.

Substituting the values, we get-

Number of regions (r)

= 30 – 20 + 2

= 12

Thus, Total number of regions in G = 12.

Problem-04:

Let G be a connected planar simple graph with 35 regions, degree of each region is 6. Find the number of vertices in G.

Solution-

Given-

Number of regions (n) = 35
Degree of each region (d) = 6

Calculating Total Number Of Edges (e)-

By sum of degrees of regions theorem, we have-

Sum of degrees of all the regions = 2 x Total number of edges

Number of regions x Degree of each region = 2 x Total number of edges

35 x 6 = 2 x e

∴ e = 105

Thus, Total number of edges in G = 105.

Calculating Total Number Of Vertices (v)-

By Euler’s formula, we know r = e – v + 2.

Substituting the values, we get-

35 = 105 – v + 2

∴ v = 72

Thus, Total number of vertices in G = 72.

Problem-05:

Let G be a connected planar graph with 12 vertices, 30 edges and degree of each region is k. Find the value of k.

Solution-

Given-

Number of vertices (v) = 12
Number of edges (e) = 30
Degree of each region (d) = k

Calculating Total Number Of Regions (r)-

By Euler’s formula, we know r = e – v + 2.

Substituting the values, we get-

Number of regions (r)

= 30 – 12 + 2

= 20

Thus, Total number of regions in G = 20.

Calculating Value Of k-

By sum of degrees of regions theorem, we have-

Sum of degrees of all the regions = 2 x Total number of edges

Number of regions x Degree of each region = 2 x Total number of edges

20 x k = 2 x 30

∴ k = 3

Thus, Degree of each region in G = 3.

Problem-06:

What is the maximum number of regions possible in a simple planar graph with 10 edges?

Solution-

In a simple planar graph, degree of each region is >= 3.

So, we have 3 x |R| <= 2 x |E|.

Substituting the value |E| = 10, we get-

3 x |R| <= 2 x 10

|R| <= 6.67

|R| <= 6

Thus, Maximum number of regions in G = 6.

Problem-07:

What is the minimum number of edges necessary in a simple planar graph with 15 regions?

Solution-

In a simple planar graph, degree of each region is >= 3.

So, we have 3 x |R| <= 2 x |E|.

Substituting the value |R| = 15, we get-

3 x 15 <= 2 x |E|

|E| >= 22.5

|E| >= 23

Thus, Minimum number of edges required in G = 23.

To gain better understanding about Planar Graphs in Graph Theory,

Watch this Video Lecture

Next Article- Euler Graph

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Cache Mapping | Cache Mapping Techniques

Computer Organization and Architecture

Cache Memory-

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

We have discussed-

Cache memory bridges the speed mismatch between the processor and the main memory.

When cache hit occurs,

The required word is present in the cache memory.
The required word is delivered to the CPU from the cache memory.

When cache miss occurs,

The required word is not present in the cache memory.
The page containing the required word has to be mapped from the main memory.
This mapping is performed using cache mapping techniques.

In this article, we will discuss different cache mapping techniques.

Cache Mapping-

Cache mapping defines how a block from the main memory is mapped to the cache memory in case of a cache miss.

Cache mapping is a technique by which the contents of main memory are brought into the cache memory.

The following diagram illustrates the mapping process-

Now, before proceeding further, it is important to note the following points-

NOTES

Main memory is divided into equal size partitions called as blocks or frames.
Cache memory is divided into partitions having same size as that of blocks called as lines.
During cache mapping, block of main memory is simply copied to the cache and the block is not actually brought from the main memory.

Cache Mapping Techniques-

Cache mapping is performed using following three different techniques-

Direct Mapping
Fully Associative Mapping
K-way Set Associative Mapping

1. Direct Mapping-

In direct mapping,

A particular block of main memory can map only to a particular line of the cache.
The line number of cache to which a particular block can map is given by-

Cache line number

= ( Main Memory Block Address ) Modulo (Number of lines in Cache)

Example-

Consider cache memory is divided into ‘n’ number of lines.
Then, block ‘j’ of main memory can map to line number (j mod n) only of the cache.

Need of Replacement Algorithm-

In direct mapping,

There is no need of any replacement algorithm.
This is because a main memory block can map only to a particular line of the cache.
Thus, the new incoming block will always replace the existing block (if any) in that particular line.

Division of Physical Address-

In direct mapping, the physical address is divided as-

2. Fully Associative Mapping-

In fully associative mapping,

A block of main memory can map to any line of the cache that is freely available at that moment.
This makes fully associative mapping more flexible than direct mapping.

Example-

Consider the following scenario-

Here,

All the lines of cache are freely available.
Thus, any block of main memory can map to any line of the cache.
Had all the cache lines been occupied, then one of the existing blocks will have to be replaced.

Need of Replacement Algorithm-

In fully associative mapping,

A replacement algorithm is required.
Replacement algorithm suggests the block to be replaced if all the cache lines are occupied.
Thus, replacement algorithm like FCFS Algorithm, LRU Algorithm etc is employed.

Division of Physical Address-

In fully associative mapping, the physical address is divided as-

3. K-way Set Associative Mapping-

In k-way set associative mapping,

Cache lines are grouped into sets where each set contains k number of lines.
A particular block of main memory can map to only one particular set of the cache.
However, within that set, the memory block can map any cache line that is freely available.
The set of the cache to which a particular block of the main memory can map is given by-

Cache set number

= ( Main Memory Block Address ) Modulo (Number of sets in Cache)

Also Read- Set Associative Mapping | Implementation and Formulas

Example-

Consider the following example of 2-way set associative mapping-

Here,

k = 2 suggests that each set contains two cache lines.
Since cache contains 6 lines, so number of sets in the cache = 6 / 2 = 3 sets.
Block ‘j’ of main memory can map to set number (j mod 3) only of the cache.
Within that set, block ‘j’ can map to any cache line that is freely available at that moment.
If all the cache lines are occupied, then one of the existing blocks will have to be replaced.

Need of Replacement Algorithm-

Set associative mapping is a combination of direct mapping and fully associative mapping.
It uses fully associative mapping within each set.
Thus, set associative mapping requires a replacement algorithm.