diff options
Diffstat (limited to 'ss2017/stable_marriage_problem/structure.md')
-rw-r--r-- | ss2017/stable_marriage_problem/structure.md | 10 |
1 files changed, 8 insertions, 2 deletions
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 @@ | |||
7 | - Definition: Tables, embedded tables, embedded pairs, embedded matchings | 7 | - Definition: Tables, embedded tables, embedded pairs, embedded matchings |
8 | - Definition: stable tables | 8 | - Definition: stable tables |
9 | - Matchings embedded in stable tables are stable (4.2.4 ii) | 9 | - Matchings embedded in stable tables are stable (4.2.4 ii) |
10 | - (Stable tables are determined by all first OR all last entries (4.2.4 iii)) | 10 | - Stable tables are determined by all first OR all last entries (4.2.4 iii) |
11 | - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i) | 11 | - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i) |
12 | 12 | ||
13 | # Phase 1 | 13 | # Phase 1 |
14 | - Removal of pairs from tables | ||
15 | - Engagement | ||
14 | - Present algorithm and demonstrate | 16 | - Present algorithm and demonstrate |
15 | - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i) | 17 | - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i) |
16 | - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii) | 18 | - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii) |
@@ -18,7 +20,8 @@ | |||
18 | 20 | ||
19 | # Rotations | 21 | # Rotations |
20 | - Definition: rotation, exposure of rotations in stable tables | 22 | - Definition: rotation, exposure of rotations in stable tables |
21 | - Rotations exposed in a stable T are either identical or disjunct (4.2.5) | 23 | - Directed graphs & tails |
24 | - (Rotations exposed in a stable T are either identical or disjunct (4.2.5)) | ||
22 | 25 | ||
23 | # Phase 2 | 26 | # Phase 2 |
24 | - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6) | 27 | - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6) |
@@ -26,4 +29,7 @@ | |||
26 | - ignores non-elements of rotation (4.2.7 iii) | 29 | - ignores non-elements of rotation (4.2.7 iii) |
27 | - results in table consistent with rotation (4.2.7 i, ii) | 30 | - results in table consistent with rotation (4.2.7 i, ii) |
28 | - Thus: produce stable subtables (4.2.8) | 31 | - Thus: produce stable subtables (4.2.8) |
32 | - Subtables that don't agree with an exposed rotation have at least that rotation removed entirely (4.2.9) | ||
33 | - Any subtable can be created by removing a series of exposed rotations (Cor 4.2.2) | ||
34 | - Removal of rotations preserve matchings (Thm 4.2.1) | ||
29 | - Present derived algorithm and demonstrate | 35 | - Present derived algorithm and demonstrate |