Tap or click on cards to flip them and reveal the answers. You can use arrow keys as well.
Loading folders...
1/15 cards
What is a Eulerian path?
Click to flip
A Eulerian path is a path in a graph that visits every edge exactly once.
Click to flip
What is a Hamiltonian cycle?
Click to flip
A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once.
Click to flip
Explain a planar graph.
Click to flip
A planar graph is a graph that can be drawn on a plane without any edges crossing.
Click to flip
What is graph isomorphism?
Click to flip
Graph isomorphism is a one-to-one correspondence between the vertex sets of two graphs that preserves adjacency.
Click to flip
Define the adjacency matrix of a graph.
Click to flip
The adjacency matrix is a square matrix used to represent a graph, with rows and columns labeled by graph vertices.
Click to flip
What is the incidence matrix?
Click to flip
The incidence matrix is a matrix that shows the relationship between vertices and edges in a graph.
Click to flip
What defines a chromatic number of a graph?
Click to flip
The chromatic number is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.
Click to flip
What is breadth-first search (BFS)?
Click to flip
BFS is an algorithm for traversing or searching tree or graph data structures, starting from the root and exploring each neighbor before moving to the next depth level.
Click to flip
What is depth-first search (DFS)?
Click to flip
DFS is an algorithm for traversing or searching tree or graph data structures, by exploring as far as possible along one branch before backing up.
Click to flip
Explain Dijkstra's algorithm.
Click to flip
Dijkstra's algorithm is a graph search algorithm that finds the shortest path between nodes in a graph, which may represent, for example, road networks.
Click to flip
What is a minimum spanning tree?
Click to flip
A minimum spanning tree is a subset of the edges of a connected, edge-weighted graph that connects all vertices together, without any cycles and with the minimum possible total edge weight.
Click to flip
What is a network flow?
Click to flip
Network flow involves finding the flow of items through a network, maximizing throughput from source to sink, often using the Ford–Fulkerson method.
Click to flip
What are cliques in graph theory?
Click to flip
A clique is a subset of vertices of a graph such that every two distinct vertices are adjacent.
Click to flip
What is edge connectivity?
Click to flip
Edge connectivity is the minimum number of edges that need to be removed to disconnect a connected graph.
Click to flip
Explain the traveling salesman problem.
Click to flip
The traveling salesman problem asks for the shortest possible route that visits each city exactly once and returns to the origin city.
Click to flip
Need More Study Materials?
Go back to the chat to generate additional resources.