Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Cs 2nd Year, 1st Sem > Chapter 7 > Flashcards

Chapter 7 Flashcards

1
Q

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

A

Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

the fundamental units of the graph

A

Vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

drawn or used to connect two nodes of the graph.

A

Edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

null graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

Trivial Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

Connected Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Disconnected Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Regular Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Complete Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

Cycle Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

A graph containing at least one cycle is known

A

Cyclic Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A Directed Graph that does not contain any cycle.

A

Directed Acyclic Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Bipartite Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

Weighted Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

Trees

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Two ways to store a graph:

A

Adjacency Matrix
Adjacency List

17
Q

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

A

Graph data structures

18
Q

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

A

Graphs

19
Q

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

A

Graphs

20
Q

real-life applications of graph

A

1.Neural Networks
2.Compilers
3.Robot planning

21
Q

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

A

TheBreadth First Search (BFS)algorithm

22
Q

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).

A

Depth First Traversal (or DFS)for a graph

23
Q

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

A

Depth-first search

24
Q

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

A

Detecting cycle in a graph

25
Q

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

A

Topological Sorting

Cs 2nd Year, 1st Sem (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions