Discussion and Examples
Example 1: Consider S = {A1, A2, A3} with
- A1 = {1, 2, 3}
- A2 = {1, 4, 5}
- A3 = {3, 5}.
A valid SDR would be {1, 4, 5}. (Note this is not unique: {2, 1, 3} works equally well, for example.)
Example 2: Consider S = {A1, A2, A3, A4} with
- A1 = {2, 3, 4, 5}
- A2 = {4, 5}
- A3 = {5}
- A4 = {4}.
No valid SDR exists; the marriage condition is violated as is shown by the subcollection {A2, A3, A4}.
Example 3: Consider S= {A1, A2, A3, A4} with
- A1 = {a, b, c}
- A2 = {b, d}
- A3 = {a, b, d}
- A4 = {b, d}.
The only valid SDR's are (c, b, a, d) and (c, d, a, b).
Read more about this topic: Hall's Marriage Theorem
Famous quotes containing the words discussion and/or examples:
“My companion and I, having a minute’s discussion on some point of ancient history, were amused by the attitude which the Indian, who could not tell what we were talking about, assumed. He constituted himself umpire, and, judging by our air and gesture, he very seriously remarked from time to time, “you beat,” or “he beat.””
—Henry David Thoreau (1817–1862)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)