**Unit 7: graph [16 marks]**

** 2, 4 & 8 mark question**

**1) Define graph? [2m]**

** Ans:**

A graph is a collection of two sets V and E where V is the set of vertices, E is the set of edges.

It is mathematically represented by G=(V,E)

The set of vertices in the above graph is {A,B,C,D,E}.

The set of edges will be { (A,B),(A,D),(A,C),(C,D),(C,E)}

Graph is a non linear data structure that is widely used to solve real life computing problems.

Graphs can be used in variety of applications such as electrical circuits , routing, find critical paths in networks etc.

** 2) Explain the following term with respect to graph using suitable example. (i) In-degree (ii) Out-degree**

** (In-degree with example – 2 Marks, Out-degree with example – 2 Marks)**

** Ans:**

The total number of edges linked to the vertex is called as degree.

**In-degree** of a specified vertex in a graph is number of edges coming towards it i.e. number of edges that have that specified vertex as the head.

**Out-degree** of a specified vertex in a graph is number of edges going out from a specified vertex i.e. number of edges that have that specified vertex as the tail.

Vertex A has **Indegree 2** as only two edges are coming towards vertex A.

Vertex C has **Outdegree 1** as one edge is going out from vertex C.

**3) Explain term weighted graph. (Definition-2Marks)**

** Ans:** A graph is a weighted graph if a number (weight) is assigned to each edge.

Such weights might represent costs, lengths or capacities etc.

**OR**

A weighted graph is graph in which edges are assigned weights. Weight in the graph denote the distance between the vertex connected by the corresponding edges

**4) Describe directed graph and undirected graph with diagram. ( 2 marks each)**

** Ans:**

**Directed graph:**

Each edge in the graph is assigned with the direction called directed graph or digraph.

In a directed graph, each edge is represented by a pair of ordered vertices

i.e. an edge has a specific direction.

An edge (Vi, Vj) ≠ (Vi, Vj)

**Undirected graph:**

Each edge in the graph is not assigned with the direction called undirected graph.

A graph is an undirected graph if the pairs of vertices that make up the edges are unordered pairs.

i.e. an edge (Vi, Vj) = (Vj, Vi) the graph G1 is an

undirected graph.

**5) Enlist and explain the types of graphs with example [6 m ] ****(2 marks for list and explain any four 1 mark each)**

** Ans:**

** The different types of graph is as follows**

i) Directed graph ii) Undirected graph

iii) Complete graph iv) Connected graph

v) Multigraph

**1) Directed Graph:** Each edge in the graph is assigned with the direction called directed graph or digraph. refer fig 1

**2) Undirected Graph:** Each edge in the graph is not assigned with the direction called undirected graph. refer fig 2

**3) Complete Graph:** A graph is said to complete graph if there exists an edge between every pair of vertices. refer fig 3

**4) Connected Graph:** A graph is said to connected if there is at least one path between every pair of vertices refer fig 4

**5) Multigraph :** A graph which contain pair of nodes joined by more than one edge is called multigraph and such edges are called as parallel edges. refer fig 5

**6) Explain the sequential and linked representation of graphs**

** Ans:** There are two methods of representing graph in computer’s memory.

i) Sequential representation ii) Linked representation

**i) Sequential Representation:**

The sequential representation of graph is done by means of adjacency matrix.

**ii) Linked Representation:**

The linked representation of graph is done by means of adjacency list

**Adjacency Matrix is defined as**

**Example:**

**Path Matrix is defined as**

Example:

**7) Consider the graph shown in Fig No. 2. (Adjacency matrix–4M, Adjacency list–4M)**

** (i) Give adjacency matrix representation.**

** (ii) Give adjacency list representation of the graph.**

** Ans:**

**(i) Adjacency matrix**

**8) Consider the graph given in figure find its adjacency matrix and adjacency link representation. (4 Marks for matrix & 4 Marks for link representation)**

**Adjacent nodes can contain two or three fields.**

**9) Consider the graph ‘G’ in fig.**

** i) Find all the simple paths from X to Z**

** ii) Find all the simple paths from Y to Z.**

** iii) Find indeg (Y) and outdeg (Y).**

** iv) Find the adjacency matrix A of the graph G.**

** v) Find the path P of G using powers of the ****adjacency matrix A. ****(Path from X to Z-1Mark, Paths from Y to Z-1Mark, In deg- 1 Mark, Out deg-1 Mark, ****Adjacency matrix- 2 Marks, Path P of G using powers of the Adjacency matrix A-2 ****Marks)**

** Ans:**

**10) Describe breadth first traversal of graph. (algorithm in terms of example can also be considered 8Marks)**

**Ans:** The general idea behind a BFS is starting with any node say A.

Then we visit all its neighbour nodes.

Queue data structure is used for implementing breadth first traversal.

**Algorithm for breadth first traversal on graph.**

1. Initialize all nodes to the ready state(STATUS=1)

2. Put the starting node A in queue & change its status to the waiting

state(status=2)

3. Repeat step 4 & 5 until Queue is empty.

4. Remove the front node N of queue. Process N and change the status of N to the processed state(STATUS=3)

5. Add to the rear of QUEUE all the neighbours of N that are in the ready state(STATUS=1) and change their status to the waiting state (STATUS=2) [End of step 3 LOOPS]
6. Exit

**11) Describe breadth first search traversal in a graph with example.**

** (Algorithm 4 marks, Any relevant example explaining BFS 4 marks)**

** Ans:**

**Algorithm for BFS:**

1. Initialize all nodes to ready state.

2. Insert starting node in a queue and change its state to waiting state.

3. Repeat steps 4 to 6 till the queue becomes empty.

4. Remove front node N from queue 2 change its status to visited.

5. Insert all adjacent nodes of N at the rear end of the queue and change their status to “waiting state”.

6. From the origin find path from source node to destination node or from the queue element list find all nodes that are reachable.

7. Stop.

Front of the queue is set to “0” Rear of the queue is set to “0” Queue is used to indicate elements of the graph which are visited.

Origin is used to keep track of origin of each node.

Find all nodes reachable from “A”

**1. Insert A into a queue.**

**12) Explain DFS with suitable example.**

** (Description – 4 Marks, Example – 4 Marks; any valid example shall be considered)**

** Ans:** **Depth First Search (DFS)**

The aim of DFS algorithm is to traverse the graph in such a way that it tries to go far from the root node.

Stack is used in the implementation of the depth first search.

Back tracking used in this algorithm

**Algorithm**

Step1: Start

Step2: Initialize all nodes as unvisited

Step3: Push the starting node onto the stack. Mark it as waiting.

Step4: Pop the top node from stack and mark is as visited.

Push all its adjacent nodes into the stack &mark them as waiting.

Step 5 .Repeat step 4 until stack is empty.

Step 6: Stop

**For example,** consider the following graph G as follows:

Suppose we want to find and print all the nodes reachable from the node J (including J itself).

The steps for the will be as follows:

**a)** Initially, push J onto stack as follows:

**stack: J**

**b)** Pop and print the top element J, and then push onto the stack all the neighbours of J as follows:

**Print J STACK : D, K**

**c)** Pop and print the top element K, and then push onto the stack all the unvisited neighbours of k

**Print K STACK : D, E, G**

**d)** Pop and print the top element G, and then push onto the stack all the neighbours of **G**.

**Print G STACK : D, E, C**

Note that only **C** is pushed onto the stack, since the other neighbour, **E** is not pushed because **E** has already been pushed onto the stack).

**e)** Pop and print the top element C and then push onto the stack all the neighbours of C

**Print C STACK : D, E, F**

**f)** Pop and print the top element F

**Print F STACK : D, E**

Note that only neighbour **D** of** F** is not pushed onto the stack, since **D** has already been pushed onto the stack.

**g)** Pop and print the top element E and push onto the stack all the neighbours of D

**Print E STACK : D,**

**h)** Pop and print the top element D, and push onto the stack all the neighbours of D

**Print D STACK : empty**

The stack is now empty, so the DFS of G starting at J is now complete.

Accordingly, the nodes which were printed,

**J, K, G, C, F, E, D**

These are the nodes reachable from **J.**

**13) What is Hashing? Give its significance.**

** (Definition of hashing -2Marks, Significance- 2Marks)**

** Ans:**

**Definition: –** Hashing is a technique used to compute memory address for performing insertion, deletion and searching of an element using hash function.

**Significance of Hashing:-**

1. Fast retrieval of information.

2. Element can be placed at appropriate position.

3. Collision can be avoided.

4. In finding duplicate records.

5. For online spelling checking hashing function used.

**14) Explain the concept of hashing and hash function. (each 2 mark)**

** OR**

** 14) Define hashing. (Definition – 2 Marks)**

**Ans:** The hashing is defined as

1. Key-value pairs are stored in a fixed size table called a hash table.

2. A hash table is partitioned into many buckets.

3. Each bucket has many slots.

4. Each slot holds one record.

**OR**

The process of mapping large amount of data item to a smaller table with the help of hashing function is known as hashing.

**OR**

Hashing is a technique used to compute memory address for performing insertion, deletion and searching of an element using hash function.

**Hash function :**

A mathematical function that converts a large possibly variable sized amount of data into small data usually a single integer that may serve as an index to an array is called hash function.

The value returned by hash function are called as hash values, hash codes, checksums.

**OR**

A hash function f(x) transforms the identifier (key) into an address in the hash table.

**15) State the characteristics of good hash function ? [2marks]**

** Ans:**

1) Low cost

2) Determination

3) Uniformity

4) Variable Range

5) Data Normalization

6) Continuity

**16) Describe the applications of hashing? [2 marks]**

** Ans:**

1) Database system

2) Data Dictionaries

3) Network Processing Algorithms

4) Browsers cashes

5) Indexing

6) Symbol table

7) Hashing is also used in encryption and decryption of digital signatures.

**17) Enlist and describe different hash addressing functions[4 marks] (2 mark for listing and 2 mark for explain any two)**

** OR**

**17) Explain any one hashing method with suitable example[2m/4m]**

** Ans:**

Different Hashing Functions are

1) Mid square method. 2) Folding method.

3) Division method. 4) Digit Analysis

5) Length Dependant method

**i) Mid Square Method:**

In this method we first square the key element and take the number of digits required to form an address from the middle position of squared value.

**Example:**

**ii) Folding Method:**

In this method, the key element is portioned into number of parts.

The parts are added together ignoring the last carry.

**Example:**

**iii) Division Method:**

In this method, we use modular arithmetic system to divide the key value

by some integer divisor m.

The hash function is defined as H(K)=K(mod m)+1

where, H(K) = location of table.

k = Key value.

m = Number of slots in file or table size.

**Example:** Suppose k=23 and m=10 then

H(K) =(23mod 10)+1

=3+1=4

**18) Define collision resolution technique.(2Mark)**

** Ans:** More than one key may generate same hash address, this is called as collision.

The technique used to solve this collision problem is called collision resolution techniques.

**Different Techniques of solving collision is**

1) Open Addressing 2) Chaining

i) Linear Probing

ii) Quadratic Probing

iii) Rehashing

K 4147 3750

K2 17197609 14062500

H(K) 97 62

K 2103 7156

K1,K2, 21,03 71,56

H(K) 21+03=24 71+56=127=27