A Eulerian path is a path in a graph that visits every edge exactly once.
What is a Hamiltonian cycle?
A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once.
Explain a planar graph.
A planar graph is a graph that can be drawn on a plane without any edges crossing.
What is graph isomorphism?
Graph isomorphism is a one-to-one correspondence between the vertex sets of two graphs that preserves adjacency.
Define the adjacency matrix of a graph.
The adjacency matrix is a square matrix used to represent a graph, with rows and columns labeled by graph vertices.
What is the incidence matrix?
The incidence matrix is a matrix that shows the relationship between vertices and edges in a graph.
What defines a chromatic number of a graph?
The chromatic number is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.
What is breadth-first search (BFS)?
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.
What is depth-first search (DFS)?
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.
Explain Dijkstra's algorithm.
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.
What is a minimum spanning tree?
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.
What is a network flow?
Network flow involves finding the flow of items through a network, maximizing throughput from source to sink, often using the Ford–Fulkerson method.
What are cliques in graph theory?
A clique is a subset of vertices of a graph such that every two distinct vertices are adjacent.
What is edge connectivity?
Edge connectivity is the minimum number of edges that need to be removed to disconnect a connected graph.
Explain the traveling salesman problem.
The traveling salesman problem asks for the shortest possible route that visits each city exactly once and returns to the origin city.