Course outline
Module 1
Module 1: Introduction to Graphs
Introduction to Graphs
Knowledge check
Q1. What is a graph composed of?
- A. Vertices and edges
- B. Lines and points
- C. Nodes and connections
- D. All of the above ✓
Why: A graph is composed of vertices (or nodes) and edges (or connections) which represent relationships between the vertices.
Q2. Which of the following is an example of a simple graph?
- A. A graph with multiple edges between two vertices
- B. A graph with loops
- C. A graph with no loops or multiple edges ✓
- D. A graph with directed edges
Why: A simple graph is defined as a graph with no loops or multiple edges between any pair of vertices.
Q3. What is the degree of a vertex in a graph?
- A. The number of edges connected to it ✓
- B. The number of vertices connected to it
- C. The number of loops on it
- D. The number of paths from it
Why: The degree of a vertex is the number of edges incident to it.
Q4. What is a path in a graph?
- A. A sequence of edges that connects two vertices ✓
- B. A sequence of vertices that connects two edges
- C. A sequence of loops
- D. A sequence of multiple edges
Why: A path is a sequence of edges that connects two vertices, with no repeated edges or vertices.
Q5. Which of the following is a directed graph?
- A. A graph with undirected edges
- B. A graph with no edges
- C. A graph with directed edges ✓
- D. A graph with only loops
Why: A directed graph, or digraph, is a graph where edges have a direction associated with them.
Module 2
Module 2: Basic Graph Terminology
Basic Graph Terminology
Knowledge check
Q1. What is a graph composed of?
- A. Vertices and edges ✓
- B. Vertices and nodes
- C. Edges and lines
- D. Nodes and connections
Why: A graph is composed of vertices (also called nodes) and edges (also called connections or lines) that connect these vertices.
Q2. What is a vertex with degree zero called?
- A. Isolated vertex ✓
- B. Leaf vertex
- C. Internal vertex
- D. Root vertex
Why: A vertex with no edges connected to it is called an isolated vertex.
Q3. What is the degree of a vertex in a graph?
- A. The number of edges incident to it ✓
- B. The number of vertices connected to it
- C. The number of loops in the graph
- D. The number of paths from it to other vertices
Why: The degree of a vertex is defined as the number of edges incident to it.
Q4. What is a graph with no edges called?
- A. Empty graph ✓
- B. Trivial graph
- C. Null graph
- D. Simple graph
Why: A graph with no edges is referred to as an empty graph.
Q5. What is a graph called if it has no multiple edges and no loops?
- A. Simple graph ✓
- B. Multigraph
- C. Pseudograph
- D. Directed graph
Why: A simple graph is defined as a graph with no multiple edges and no loops.
Module 3
Module 3: Types of Graphs
Types of Graphs
Knowledge check
Q1. What is a graph with no edges called?
- A. Simple graph
- B. Null graph ✓
- C. Complete graph
- D. Bipartite graph
Why: A null graph is a graph with no edges and no vertices, or sometimes just no edges.
Q2. Which of the following is a characteristic of a simple graph?
- A. It has loops
- B. It has multiple edges between two vertices
- C. It has no loops or multiple edges ✓
- D. It has directed edges
Why: A simple graph is defined as having no loops or multiple edges between any two vertices.
Q3. Which type of graph allows edges to connect a vertex to itself?
- A. Simple graph
- B. Null graph
- C. Multigraph
- D. Pseudograph ✓
Why: A pseudograph is a graph that allows both loops and multiple edges.
Q4. Which of the following is a type of graph where every pair of vertices is connected by an edge?
- A. Tree
- B. Cycle graph
- C. Complete graph ✓
- D. Bipartite graph
Why: A complete graph is a graph in which every pair of distinct vertices is connected by a unique edge.
Q5. Which of the following is a graph that consists of vertices and edges but no cycles?
- A. Complete graph
- B. Tree ✓
- C. Cycle graph
- D. Multigraph
Why: A tree is an undirected graph in which any two vertices are connected by exactly one path, and hence it contains no cycles.
Module 4
Module 4: Graph Representation
Graph Representation
Knowledge check
Q1. What is the primary purpose of graph representation?
- A. To calculate the area of a graph
- B. To visually or structurally depict relationships between entities ✓
- C. To determine the color of a graph
- D. To measure the distance between nodes
Why: Graph representation is used to visually or structurally depict relationships between entities, such as nodes and edges.
Q2. Which of the following is a common way to represent a graph?
- A. Using a table of colors
- B. Using a matrix or adjacency list ✓
- C. Using a calendar
- D. Using a spreadsheet for financial data
Why: Graphs are commonly represented using adjacency matrices or adjacency lists, which capture the relationships between nodes.
Q3. What does an adjacency list represent in a graph?
- A. The color of the edges
- B. The list of nodes connected to each node ✓
- C. The distance between nodes
- D. The number of edges in a graph
Why: An adjacency list represents the list of nodes connected to each node, making it an efficient way to store sparse graphs.
Q4. What is an advantage of using an adjacency matrix over an adjacency list?
- A. It is more memory efficient for sparse graphs
- B. It allows for quick lookup of whether an edge exists between two nodes ✓
- C. It is easier to implement for large graphs
- D. It is better for representing weighted graphs
Why: An adjacency matrix allows for quick lookup of whether an edge exists between two nodes, which is a key advantage in certain applications.
Q5. In an undirected graph, how is the adjacency matrix represented?
- A. It is always triangular
- B. It is symmetric ✓
- C. It is diagonal
- D. It is sparse
Why: In an undirected graph, the adjacency matrix is symmetric because if there is an edge from node A to node B, there is also an edge from node B to node A.
Module 5
Module 5: Traversing Graphs
Traversing Graphs
Knowledge check
Q1. What is the term for a path that visits every edge exactly once in a graph?
- A. Euler trail ✓
- B. Euler circuit
- C. Hamiltonian path
- D. Hamiltonian cycle
Why: An Euler trail visits every edge exactly once, while an Euler circuit does the same but starts and ends at the same vertex. Hamiltonian paths and cycles focus on visiting vertices, not edges.
Q2. Which of the following is a necessary condition for a graph to have an Euler circuit?
- A. All vertices have even degree ✓
- B. All vertices have odd degree
- C. Exactly two vertices have odd degree
- D. The graph is disconnected
Why: For a graph to have an Euler circuit, all vertices must have even degree, and the graph must be connected.
Q3. What is the name of a path that visits every vertex exactly once?
- A. Euler trail
- B. Euler circuit
- C. Hamiltonian path ✓
- D. Hamiltonian cycle
Why: A Hamiltonian path visits every vertex exactly once, while a Hamiltonian cycle does the same but starts and ends at the same vertex.
Q4. Which type of graph guarantees the existence of a Hamiltonian cycle?
- A. Complete graph ✓
- B. Bipartite graph
- C. Tree
- D. Cycle graph
Why: A complete graph with at least three vertices guarantees the existence of a Hamiltonian cycle, as every vertex is connected to every other vertex.
Q5. Which of the following is true about a graph with an Euler trail?
- A. It has exactly two vertices of odd degree ✓
- B. All vertices have even degree
- C. It has no vertices of odd degree
- D. It has more than two vertices of odd degree
Why: A graph with an Euler trail must have exactly two vertices of odd degree, and all other vertices must have even degree.
Module 6
Module 6: Shortest Path Algorithms
Shortest Path Algorithms
Knowledge check
Q1. What is the primary goal of a shortest path algorithm?
- A. To find the number of edges in a graph
- B. To find the path with the least total weight between two vertices ✓
- C. To determine if a graph is connected
- D. To find the number of cycles in a graph
Why: The primary goal of a shortest path algorithm is to find the path with the least total weight between two vertices.
Q2. Which algorithm is best suited for finding the shortest path in a graph with non-negative edge weights?
- A. Bellman-Ford
- B. Dijkstra's ✓
- C. Floyd-Warshall
- D. Breadth-First Search
Why: Dijkstra's algorithm is best suited for finding the shortest path in a graph with non-negative edge weights.
Q3. What data structure is typically used to implement the priority queue in Dijkstra's algorithm?
- A. Stack
- B. Queue
- C. Heap ✓
- D. Linked List
Why: A heap is typically used to implement the priority queue in Dijkstra's algorithm.
Q4. Which of the following algorithms can handle graphs with negative edge weights?
- A. Dijkstra's
- B. Breadth-First Search
- C. Bellman-Ford ✓
- D. Prim's
Why: Bellman-Ford algorithm can handle graphs with negative edge weights.
Q5. What is the time complexity of Dijkstra's algorithm when using a Fibonacci heap?
- A. O(V log V + E) ✓
- B. O(V + E log V)
- C. O(E + V log V)
- D. O(V^2)
Why: The time complexity of Dijkstra's algorithm when using a Fibonacci heap is O(V log V + E).
Module 7
Module 7: Graph Coloring Basics
Graph Coloring Basics
Knowledge check
Q1. What is the minimum number of colors required to color a bipartite graph?
Why: A bipartite graph can be divided into two sets of vertices with no edges within each set, so only two colors are needed.
Q2. Which of the following is a proper vertex coloring?
- A. Adjacent vertices have the same color
- B. Adjacent vertices have different colors ✓
- C. All vertices have the same color
- D. No two vertices have the same color
Why: In a proper vertex coloring, adjacent vertices must have different colors.
Q3. What is the chromatic number of a cycle graph with an odd number of vertices?
Why: A cycle graph with an odd number of vertices is not bipartite and requires three colors for proper coloring.
Q4. What is the chromatic number of a complete graph with 4 vertices?
Why: In a complete graph, every vertex is connected to every other vertex, so each vertex must have a unique color.
Q5. Which of the following graphs is always 2-colorable?
- A. Complete graph
- B. Cycle graph with even vertices
- C. Tree graph
- D. Both B and C ✓
Why: Cycle graphs with even vertices and tree graphs are both bipartite and hence 2-colorable.