Maximum branching: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== General information == '''Definition:''' A '''branching''' is a cycle-free '''Input:''' # A directed graph <math>G=(V,A)</math>: # A real-valued weight <math>w(a)</math>...") |
No edit summary |
||
| Line 2: | Line 2: | ||
'''Definition:''' | '''Definition:''' | ||
A '''branching''' is a cycle-free | A '''branching''' is a cycle-free directed graph such that each node has at most one incoming arc. | ||
| Line 11: | Line 11: | ||
'''Output:''' | '''Output:''' | ||
A | 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 16:08, 9 October 2014
General information
Definition: A branching is a cycle-free directed graph such that each node has at most one incoming arc.
Input:
- A directed graph [math]\displaystyle{ G=(V,A) }[/math]:
- 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.