CSCE 411 Lecture 8

Lecture Slides

« previous | Wednesday, September 12, 2012 | next »

Greedy Algorithms (cont'd)

Matroids

Let $S$ be a set, and $F$ be a set of subsets of $S$

1. If $B\in F$ and $A\subseteq B$, then $A\in F$. (hereditary)
2. If $A$ and $B$ are in $F$ such that $A$ is smaller than $B$, then there's an element $x$ that's in $B$ but not in $A$. Adding $x$ to $A$ produces a set that is also in $F$ (exchange property)

Graphs

Induced subgraph has a subset of edges from an original graph

Spanning Tree is an induced subgraph that happens to be a tree (i.e. no cycles) and connects all vertices

Graphic Matroids

Let $G=(V,E)$ be an undirected graph.

$S$ would just be the edges

$F=\{A\mid H=(V,A){\mbox{such that H is an induced subgraph and forest of G}}\}$. A forest is just 1 or more trees that can be made from the edges of $G$

1. hereditary property mandates that any forest can be split into more trees by removing an edge.
2. exchange property states that an edge can be added to a forest to create another forest.