1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 2-4, 2-5, 2-6

False. For example, we suppose there are 2 wowen (w, w') and 2 men(m, m'). for m, he prefer w to w'. For m', he prefers w' to w. For w, she prefers m' to m.For w', she prefers m to m'.

there are 2 stable matching. [w-m , w'-m'] and [w-m', w'-m]. Neither match satisfies the above conditions.

the arrow means prefer

True. If there exist an matching doesn't include [m-w]. then there must exist an matching [m-w', w-m'] however, for both m and w, they rank first on the preference of themselves. According to the definition of unstable pair, m-w is unstable pair. This contradicts the hypothesis. Thus, the statement is true.example, A network has three channel ,ranks 4, 7,1 .And B network also has channel, ranks 3 2 5. I listed all the possible matching. The green arrow shows the pair which one of the network will want to change. Actually, for network A, if 4-3 is not paired, it will change to make 4-3. However, for network B, if 4-5 is not paired, it will change to make 4-5. So there is no stable matching.

其实就是要证明一个A> B >A 的问题，田忌赛马的例子

全部用减法或者除法都可以

(d) nlogn