For the preferences listed below, find a solution to the stable marriage problem that, among all possible solutions, finds the most highly preferred partner for each woman.
Adam: Wanda, Xanthippe, Yasmin, Zelda
Bob: Xanthippe, Wanda, Yasmin, Zelda
Carl: Yasmin, Wanda, Xanthippe, Zelda
Don: Zelda, Wanda, Xanthippe, Yasmin
Wanda: Bob, Adam, Carl, Don
Xanthippe: Carl, Adam, Bob, Don
Yasmin: Bob, Adam, Carl, Don
Zelda: Carl, Adam, Don, Bob
Find a partition of the polygon shown below into the minimum possible number of rectangles.
Give an example of a graph that is not bipartite but that nevertheless satisfies the equation |M| + |I| = |V| where M is a maximum matching, I is a maximum independent set, and V is the set of all vertices. Show the maximum matching and maximum independent set for your example.
Find an alternating path starting at t and ending at u in the graph shown below.