Back to notes
If a graph is represented by an adjacency list, what does it map each vertex to?
Press to flip
A list of its neighbors.
What is a common problem involving finding the path of least length between two vertices?
Shortest Path problem
What are the components in a graph called?
Vertices (or Nodes)
Which graph representation is preferred for sparse graphs and why?
Adjacency List, because it is efficient for graphs with large vertices and few edges per vertex.
Which graph representation involves a matrix where an entry is 1 if there is an edge between nodes i and j?
Adjacency Matrix
What graph term describes a sequence of vertices connected by edges?
Path
What is the main characteristic of a Directed Acyclic Graph (DAG)?
It contains no cycles.
What problem in graph theory seeks to determine if two vertices are connected?
Connectivity
What kind of graphs model friendships in social networks?
Undirected Graphs
What describes a problem of finding a path that visits every vertex exactly once?
Hamiltonian Path
What is a Connected Component?
A subset of vertices that is connected within a graph.
Why is the Vertex Coloring problem significant?
It assigns colors to vertices ensuring no two neighbors share the same color.
In graph theory, what do vertices represent in mapping and navigation applications?
Intersections
How does one distinguish between paths and cycles in graph theory?
A cycle is a path that starts and ends at the same vertex. All cycles are paths but not all paths are cycles.
Explain what an Eulerian Path is.
A path that uses every edge exactly once.
Define the degree of a vertex.
The number of edges connected to a vertex (number of neighbors).
What defines an undirected graph?
Edges imply bidirectional relationships.
How can one describe a tree in graph theory?
A connected, acyclic graph. Removing an edge disconnects it; adding one creates a cycle.
What type of graph has edges that model metrics like traffic or distances?
Weighted Graph
In what scenarios would you use a Directed Cyclic Graph?
When modeling unidirectional relationships that may include cycles, such as task scheduling with dependencies.
Previous
Next