The Minimum Spanning Tree Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
* [[Prim%27s_Algorithm|Prim's Algorithm]] | * [[Prim%27s_Algorithm|Prim's Algorithm]] | ||
* [[Kruskal%27s_Algorithm|Kruskal's Algorithm]] | * [[Kruskal%27s_Algorithm|Kruskal's Algorithm]] | ||
* [[The Optimal Branching Problem]] | |||
=Overview= | =Overview= | ||
We discuss the minimum spanning problem in the context of [[Graph_Concepts#Undirected_Graph|undirected]] graphs. The same problem can be discussed for [[Graph_Concepts#Directed_Graph|directed]] graphs but in that case it is referred to as the [[The Optimal Branching Problem|Optimal Branching Problem]]. | We discuss the minimum spanning problem in the context of [[Graph_Concepts#Undirected_Graph|undirected]] graphs. The same problem can be discussed for [[Graph_Concepts#Directed_Graph|directed]] graphs but in that case it is referred to as the [[The Optimal Branching Problem|Optimal Branching Problem]]. | ||
Revision as of 21:23, 20 October 2021
Internal
Overview
We discuss the minimum spanning problem in the context of undirected graphs. The same problem can be discussed for directed graphs but in that case it is referred to as the Optimal Branching Problem.
The Problem
Given an undirected graph G=(V, E),