Next we present two examples: the Maximum Spanning Network Problem and the Integer Deadline Scheduling Problem with unit processing times.
First consider the problem of finding a Minimum Spanning Tree (network) in a weighted graph G. Let E be the set of edges in the graph G. Let I be the set of all forests of G (that is, all graphs using edges of G which have no cycles). Then (E,I) is a matroid.
To see this consider the two properties which define a matroid. Property (1) is satisfied since removing any edge from a forest results in another forest. Property (2) is satisfied by the following argument: Start with any I_{1},I_{2} in I with |I_{2}| = |I_{1}|+1. Consider three possibilites.
Now, the maximum cardinality forest of G is a spanning tree of G. Also, the weight of a spanning network in the Minimum Spanning Network problem is the sum of the edges in the network (a tree). That is, the weight of a maximum cardinality independent set is the sum of weights of objects in that set. Hence, we may use the greedy method above to solve the Minimum Spanning Network problem (which is what we have been doing all along). The only part that has to be filled in is how to check whether adding a particular edge to a forest T keeps a forest. But, this is easy, as we saw.
The Integer Deadline Scheduling problem is stated as follows:
Integer Deadline Scheduling
Instance: A set A =
{a_{1},a_{2},...,a_{n}} of n jobs,
each requiring unit time to complete, and associated with each job a is
an integer deadline d(a) and an integer profit p(a).
Produce: A schedule [a_{o1},a_{o2},...,a_{on}] for a single processor such that the sum of the profits of all jobs which are processed before their deadline is maximum over all schedules.
The solution here is trickier than for the Minimum Spanning Tree problem since, first, we can order jobs based on their deadlines or their profits so we must decide on which to base the ordering and, second, we need a schedule (that is, a list) as output and not a subset. As you might suspect, ordering on profit is correct (since we are trying to maximize profit). We use T to hold a subset of jobs which can be scheduled in such a way that all jobs in the subset can be completed before their deadlines. The final solution is obtained by finding that schedule for T (easily done by ordering the jobs in T by increasing deadline) and tacking onto that schedule all jobs not in T in any order.