Graph Theory in Discrete Mathematics

Question 1

is the study of graphs, which are
mathematical structures used to model
pairwise relations between objects.

Answer 1

Graph Theory

Question 2

Edges have no direction.

Answer 2

Undirected Graph

Question 3

Edges have a direction from
one vertex to another.

Answer 3

Directed Graph

Question 4

Edges have weights representing costs

Answer 4

Weighted Graph

Question 5

Connected acyclic graphs. Every two vertices are
connected by exactly one path.

Answer 5

Trees

Question 6

Graphs where vertices can be divided
into two disjoint sets such that no two graph vertices
within the same set are adjacent.

Answer 6

Bipartite Graphs

Question 7

Graphs in which there is a unique edge
connecting every pair of vertices.

Answer 7

Complete Graphs

Question 8

Number of edges incident to a vertex.

Answer 8

Degree

Question 9

A sequence of edges connecting a sequence of
vertices.

Answer 9

Path

Question 10

A path that starts and ends at the same vertex.

Answer 10

Cycle

Question 11

A graph is connected if there is a path
between every pair of vertices.

Answer 11

Connectivity

Question 12

Algorithms for traversing or searching tree or graph data
structures.

Answer 12

Depth-First Search (DFS) and Breadth-First Search (BFS)

Question 13

For finding the shortest path between
nodes in a graph.

Answer 13

Dijkstra’s Algorithm

Question 14

For finding the minimum spanning tree of a graph.

Answer 14

Kruskal’s and Prim’s Algorithms