Hall's Marriage Theorem - Discussion and Examples

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:

    We should seek by all means in our power to avoid war, by analysing possible causes, by trying to remove them, by discussion in a spirit of collaboration and good will. I cannot believe that such a programme would be rejected by the people of this country, even if it does mean the establishment of personal contact with the dictators.
    Neville Chamberlain (1869–1940)

    In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.
    Michel de Montaigne (1533–1592)