Chapter 7

Question 1

is a non-linear data structure consisting of vertices and edges.

Answer 1

Graph

Question 2

the fundamental units of the graph

Answer 2

Vertices

Question 3

drawn or used to connect two nodes of the graph.

Answer 3

Edges

Question 4

A graph is known as a __ if there are no edges in the graph.

Answer 4

null graph

Question 5

Graph having only a single vertex, it is also the smallest graph possible

Answer 5

Trivial Graph

Question 6

The graph in which from one node we can visit any other node in the graph is known as a

Answer 6

Connected Graph

Question 7

The graph in which at least one node is not reachable from a node is known as a

Answer 7

Disconnected Graph

Question 8

The graph in which the degree of every vertex is equal to K is called

Answer 8

Regular Graph

Question 9

The graph in which from each node there is an edge to each other node.

Answer 9

Complete Graph

Question 10

The graph in which the graph is a cycle in itself, the degree of each vertex is 2.

Answer 10

Cycle Graph

Question 11

A graph containing at least one cycle is known

Answer 11

Cyclic Graph

Question 12

A Directed Graph that does not contain any cycle.

Answer 12

Directed Acyclic Graph

Question 13

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

Answer 13

Bipartite Graph

Question 14

A graph in which the edges are already specified with suitable weight

Answer 14

Weighted Graph

Question 15

the restricted types of graphs, just with some more rules.

Answer 15

Trees

Question 16

Two ways to store a graph:

Answer 16

Adjacency Matrix
Adjacency List

Question 17

can be used to represent the interactions between players on a team, such as passes, shots, and tackles

Answer 17

Graph data structures

Question 18

Can be used to represent the topology of computer networks, such as the connections between routers and switches.

Answer 18

Graphs

Question 19

are used to represent the connections between different places in a transportation network, such as roads and airports

Answer 19

Graphs

Question 20

real-life applications of graph

Answer 20

1.Neural Networks
2.Compilers
3.Robot planning

Question 21

used to search a graph data structure for a node that meets a set of criteria.

Answer 21

TheBreadth First Search (BFS)algorithm

Question 22

similar toDepth First Traversal of a tree.The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice).

Answer 22

Depth First Traversal (or DFS)for a graph

Question 23

an algorithm for traversing or searching tree or graph data structures.

Answer 23

Depth-first search

Question 24

A graph has a cycle if and only if we see a back edge during DFS

Answer 24

Detecting cycle in a graph

Question 25

mainly used for scheduling jobs from the given dependencies among jobs.

Answer 25

Topological Sorting