From 8b5c35e41c5ea7fceec83a5134708ae02bcba395 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Sat, 6 May 2017 17:10:02 +0200 Subject: Finish indexing paper & demonstration haskell --- ss2017/stable_marriage_problem/structure.md | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'ss2017/stable_marriage_problem/structure.md') diff --git a/ss2017/stable_marriage_problem/structure.md b/ss2017/stable_marriage_problem/structure.md index 89f467c..fa9ac96 100644 --- a/ss2017/stable_marriage_problem/structure.md +++ b/ss2017/stable_marriage_problem/structure.md @@ -7,10 +7,12 @@ - Definition: Tables, embedded tables, embedded pairs, embedded matchings - Definition: stable tables - Matchings embedded in stable tables are stable (4.2.4 ii) - - (Stable tables are determined by all first OR all last entries (4.2.4 iii)) + - Stable tables are determined by all first OR all last entries (4.2.4 iii) - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i) # Phase 1 + - Removal of pairs from tables + - Engagement - Present algorithm and demonstrate - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i) - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii) @@ -18,7 +20,8 @@ # Rotations - Definition: rotation, exposure of rotations in stable tables - - Rotations exposed in a stable T are either identical or disjunct (4.2.5) + - Directed graphs & tails + - (Rotations exposed in a stable T are either identical or disjunct (4.2.5)) # Phase 2 - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6) @@ -26,4 +29,7 @@ - ignores non-elements of rotation (4.2.7 iii) - results in table consistent with rotation (4.2.7 i, ii) - Thus: produce stable subtables (4.2.8) + - Subtables that don't agree with an exposed rotation have at least that rotation removed entirely (4.2.9) + - Any subtable can be created by removing a series of exposed rotations (Cor 4.2.2) + - Removal of rotations preserve matchings (Thm 4.2.1) - Present derived algorithm and demonstrate -- cgit v1.2.3