The Minimum Spanning Tree Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 4: Line 4:
* [[Kruskal%27s_Algorithm|Kruskal's Algorithm]]
* [[Kruskal%27s_Algorithm|Kruskal's Algorithm]]
=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 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]].


=The Problem=
=The Problem=


Given an [[Graph_Concepts#Undirected_Graph|undirected]] graph G=(V, E),
Given an [[Graph_Concepts#Undirected_Graph|undirected]] graph G=(V, E),

Revision as of 21:22, 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),