Back to notes
What defines a connected graph?
Press to flip
A graph in which all pairs of vertices are connected by paths.
Describe a trivial graph.
A trivial graph consists of only one vertex and no edges.
Distinguish between a cyclic and an acyclic graph.
A cyclic graph contains at least one cycle, while an acyclic graph contains no cycles.
What defines a vertex's degree in a graph?
The number of vertices adjacent to the vertex.
Highlight a practical application of graphs in computing.
Graphs are used in websites like Google Maps for route optimization.
In what scenario would a multigraph be preferred over a simple graph?
When multiple edges between the same pair of vertices are necessary.
Explain the concept of a pseudograph.
A pseudograph contains at least one self-loop, where a vertex has an edge to itself.
Explain how breadth-first search (BFS) algorithm operates in graph traversal.
BFS starts at the root node and explores all neighbors at the present depth prior to moving on to nodes at the next depth level, using a queue data structure.
Compare and contrast adjacency matrix and adjacency list representations of a graph.
Adjacency matrix is a sequential representation using 0s and 1s or weights for connections, while an adjacency list is a linked representation listing neighbors for each vertex.
Differentiate between a cycle and a path in graph theory.
A path is a sequence of vertices with consecutive vertices adjacent, while a cycle is a path where the first and last vertices are the same.
What type of graph is characterized by the directionality of its edges?
Directed Graph.
Identify a graph where not all pairs of vertices are connected.
Disconnected Graph.
What is a regular graph?
A graph where all vertices have an equal degree.
How does depth-first search (DFS) prioritize node exploration?
DFS goes deep, exploring as far as possible along each branch before backtracking, utilizing a stack data structure.
What distinguishes a weighted graph from a simple graph?
A weighted graph has edges with weights representing traversal cost, whereas a simple graph has one edge per vertex pair without weights.
Previous
Next