Graph algorithms

Graphs

Graphs are an important mathematical concept that many algorithms are based on. It is a convenient abstraction for computation and the mathematical properties of graphs have been studied for centuries. By reducing computational tasks identified in your domain to graph problems, you immediately get access to an immense toolbox of algorithms for solving various problems. This can mean that you can pull in solutions from a graph algorithm library in your favorite programming language, or at least can figure out what algorithm, or adaption of an algorithm, you want to use.

  1. What are the elements of graphs?
  2. What is a “digraph”?
  3. What is meant by a “weighted graph”?
  4. Explain the following graph concepts:
    1. Path
    2. Cycle
    3. Subgraph
    4. Bipartite
    5. Matching
    6. Clique
    7. Independent set
  5. What is a minimum spanning tree?
  6. What is an Euler cycle?
  7. What is a Hamiltonian cycle?

Graph algorithms

  1. Graph traversal: What is…
    1. a “depth-first search”?
    2. a “breadth-first search”?
  2. What problem is Kruskal’s algorithm for?
  3. What is the Travelling salesman problem?