CSCE 411 Lecture 9

Lecture Slides: 1 2

« previous | Friday, September 14, 2012 | next »

Graphic Matroids

Let $G=(V,E)$ be an undirected graph. $S=E$, and $F=\{A\mid H=(V,A){\mbox{ is an induced subgraph of }}G{\mbox{ such that }}H{\mbox{ is a forest}}\}$.

Then $(S,F)$ is a matroid.

1. $F$ is nonempty, and deleting an edge from a forest produces another forest (hereditary)
2. Let $A,B\in F$ with $|A|<|B|$. then $(V,B)$ has fewer trees than $(V,A)$. Therefore, $(V,B)$ must contrain a tree $T$, whose vertices are in different trees in the forest $(V,A)$. One can add the edge $x$ connecting the two different trees to $A$ and obtain another forest $(V,A\cup \{x\})$.

A matroid can be weighted; let $w$ represent the weight.

Greedy algorithm

1. Sort $S$ into monotonically decreasing order by weight $w$
2. for each $x\in S$ taken in monotonically decreasing order: if $A\cup \{x\}\in F$, then add $x$ to $A$

def greedy s, f # this is our matroid (s,f)
  a = []
  s.sort! {|v1,v2| v2.weight <=> v1.weight} # sort in decreasing order
  s.each do |x|
    a << x if f.include?(a + [x])
  end
  a
end

Correctness

Seeking a contradiction, suppose that greedy returns $C\in F$, but there exists $B\in F$ such that $w(B)>w(C)$.

Since $w>0$, we can assume that $B$ and $C$ are bases.

Let $i$ be the smallest index such that $w(b_{1})\leq w(c_{1}),\ldots ,w(b_{i})>w(c_{i})$.

greedy would've picked $b_{i}$ at the $i$^th step. … So $w(B)<w(C)$ by the exchange property. CONTRADICTION!

Complexity

Let $n=\left|S\right|$

Suppose that sorting takes $O(n\log {n})$

For loop iterates $n$ times, but checking whether $A\cup \{x\}$ takes $f(n)$ time.

Therefore $greedy\in O(n\,\log {n}+n\,f(n))$.

Example

Imagine the triangular graph

${\begin{aligned}V&=\{1,2,3\}\\E&=\{(1,2),(1,3),(2,3)\}\end{aligned}}$

$F=\{\emptyset ,\{(1,2)\},\{(1,3)\},\{(2,3)\},\{(1,2),(1,3)\},\{(1,2),(2,3)\},\{(1,3),(2,3)\}\}$

Kruskal's Minimum Spanning Tree Algorithm

Let $w'(a)=m-w(a)$, where $m$ is a number that is more than the maximum weight in the graph

1. sort edges by weight in increasing order (by $w'$)
2. Keep taking edges from the sorted list as long as they do not form a cycle. ($F$ does not contain any graphs with cycles)
3. Resulting subset of edges will form minimum spanning tree

Dynamic Programming

Similar to Greedy algorithms:

• Concerned with optimization
• Optimal solution to problem contains within it optimal solutions to subproblems

However, some of the subproblems overlap

Giving Optimal Change

The "stupid country" version

Sometimes the greedy algorithm doesn't work (e.g. coin values of (1,3,4): greedy algorithm for 6 gives 4,1,1 instead of 3, 3)

Can we design an algorithm htat will give the minimum number of coins as change for any given amount?

Yes, using dynamic programming