Exploring Graph Theory Concepts

Which vocabulary term describes the graph?

• circuit

• path

• complete graph

• polygon

Which vocabulary term is illustrated through the diagram?

• Minimal Spanning Tree

• Four Color Theorem

• Cycle

• Vertices

The following undirected graph shows six houses in a village. A salesperson needs to visit all

the houses starting from house A and finishing at house F. Calculate the shortest distance in km.

• 3.05

• 3.08

• 3.30

• 3.68

Find the most optimum path to travel from a to d.

• a --> b --> d

• a --> b --> c --> d

• a --> e --> d
  

• a --> d

What is a simple graph?

• A graph with multiple edges between the same pair of vertices

• A graph with no loops or multiple edges

• A graph with at least one loop

• A graph with directed edges

Which of the following is a complete graph with 4 vertices?

• A graph with 3 edges

• A graph with 4 edges

• A graph with 6 edges

• A graph with 8 edges

What is the shortest path problem in graph theory?

• Finding the longest path between two vertices

• Finding the path with the fewest edges

• Finding the path with the minimum total weight

• Finding a path that visits all vertices

Which algorithm is commonly used to find the shortest path in a graph?

• Kruskal's algorithm

• Dijkstra's algorithm

• Prim's algorithm

• Euler's algorithm

What does it mean for a graph to be connected?

• Every vertex has a loop

• There is a path between every pair of vertices

• The graph has no edges

• The graph is directed

What is an adjacency matrix?

• A list of all edges in a graph

• A matrix representing the distances between vertices

• A matrix used to represent which vertices are adjacent

• A matrix showing the degree of each vertex