Tentaplugg - Algoritmer och datastrukturer

My preparation for the 'munta'.

Ludde127 2023-06-05



Stable matching problem

Given two sets X and Y a matching M is a set of pairs (xi, yi) so that each x and y occurs in exactly one matching.

Bipartite graph

A bipartite graph consists of two distinct sets of nodes U and V with only edges (u, v) where u is from U and v from V.

Bipartite graph example

Thus the matchings created from the stable matching problem are a bipartite graph. Assume each node in U has a ranking of its prefered nodes in V and each node in V has a ranking of the nodes in U. Then we can create a stable matching by; starting with a node u in U pair u with its most preffered node in v, this makes a temporary matching (u, v). If later in the algorithm another node u which is better ranked in v's list matches the old match is broken and the new one is created.

A matching is unstable if it has to pairs (u_a, v_a), (u_b, v_b) and

  • u_a prefers v_b and v_b prefers u_a or if,
  • v_a prefers u_b and u_b prefers v_a.

A stable matching is a perfect matching which contains no unstable pairs.

An algorithm for solving this problem is the Gale-shapley algorithm.

Gale-Shapley algorithm

Proving the Gale-Shapley algorithm can be done by reasoning.

EDAF05 example questions 2023

Card: 1/42 Score:  0.0
Press to start

Lecture 9

Card: 1/7 Score:  0.0
Press to start

Reading advice

Card: 1/31 Score:  0.0
Press to start