Maximum branching: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 3: Line 3:
'''Definition:'''
'''Definition:'''
A '''branching''' is a cycle-free directed graph such that each node has at most one incoming arc.
A '''branching''' is a cycle-free directed graph such that each node has at most one incoming arc.


'''Input:'''
'''Input:'''
# A directed graph <math>G=(V,A)</math>:
# A directed graph <math>G=(V,A)</math>:
# A real-valued weight <math>w(a)</math> for each arc <math>a\in A</math>.
# A real-valued weight <math>w(a)</math> for each arc <math>a\in A</math>.


'''Output:'''
'''Output:'''
A branching of maximum weight such that all arcs in the branching are arcs of <math>G</math>. In that, the weight of a branching is the sum of the weights of all of its arcs.
A branching of maximum weight such that all arcs in the branching are arcs of <math>G</math>. In that, the weight of a branching is the sum of the weights of all of its arcs.

Revision as of 08:51, 11 October 2014

General information

Definition: A branching is a cycle-free directed graph such that each node has at most one incoming arc.

Input:

  1. A directed graph [math]\displaystyle{ G=(V,A) }[/math]:
  2. A real-valued weight [math]\displaystyle{ w(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].

Output: A branching of maximum weight such that all arcs in the branching are arcs of [math]\displaystyle{ G }[/math]. In that, the weight of a branching is the sum of the weights of all of its arcs.