Maximum spanning forest: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Input ==
== Input ==
# An [[undirected graph]] <math>G = (V,E)</math>, not necessarily connected.
# An [[Basic graph definitions#Directed and undirected graphs|undirected graph]] <math>G = (V,E)</math>, not necessarily connected.
# An edge length <math>l(e) \in \mathbb{R}_0^+</math> for each edge <math>e \in E</math>.
# An edge length <math>l(e) \in \mathbb{R}</math> for each edge <math>e \in E</math>.


== Output ==
== Output ==
An [[undirected forest]] <math> F= (V,E_F)</math> such that <math>E_F \subseteq E</math>.
An [[Basic graph definitions#Forests, trees, branchings, arborescences|undirected forest]] <math> F= (V,E_F)</math> such that <math>E_F \subseteq E</math>.


== Objective ==
== Objective ==
Line 17: Line 17:


[[Kruskal]]
[[Kruskal]]
== Known variants ==
== Remark ==

Latest revision as of 18:03, 18 September 2015

Input

  1. An undirected graph [math]\displaystyle{ G = (V,E) }[/math], not necessarily connected.
  2. An edge length [math]\displaystyle{ l(e) \in \mathbb{R} }[/math] for each edge [math]\displaystyle{ e \in E }[/math].

Output

An undirected forest [math]\displaystyle{ F= (V,E_F) }[/math] such that [math]\displaystyle{ E_F \subseteq E }[/math].

Objective

Maximize: [math]\displaystyle{ \sum{}{}_{e \in E_F}l(e) }[/math].

Complexity

Polynomial.

Known algorithms

Kruskal