Scroll to Top

Virtual Math Learning Center

Virtual Math Learning Center Texas A&M University Virtual Math Learning Center

Section 2.4 - Minimum-Cost Spanning Trees

Instructions

  • The first video below explains the concepts in this section.
  • This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.

Concepts

  • Trees, spanning trees, and minimum-cost spanning trees
  • Kruskal's algorithm for finding mininmum-cost spanning trees

If you would like to see more videos on the topic, click the following link and check the related videos.

Exercises

Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.

1. Find at least 2 different spanning trees for the following graph.

A graph on seven vertices in the shape of a hexagon

Here are several possible answers.

Three spanning trees on a graph with seven vertices

If you would like to see more videos on this topic, click the following link and check the related videos.

2. Use Kruskal's algorithm to find a minimum-cost spanning tree.

A weighted graph on seven vertices

A spanning tree for a weighted graph with seven vertices

If you would like to see more videos on this topic, click the following link and check the related videos.

3. Use Kruskal's algorithm to find a minimum-cost spanning tree.

A weighted graph on six vertices

A spanning tree for a weighted graph on six vertices

If you would like to see more videos on this topic, click the following link and check the related videos.

4. Use Kruskal's algorithm to find a minimum-cost spanning tree.

A weighted graph on eight vertices

A spanning tree for a weighted graph on eight vertices

If you would like to see more videos on this topic, click the following link and check the related videos.

Change the section

Prev Section Next Section Return to Course