填空题

设M为无向图G中一个匹配，Γ为G中关于M的可增广的交错路径，则Γ中不在M中的边比在M中的边多（）条。

答案： 1

你可能感兴趣的试题

设M为无向图G中的一个匹配，C为G中关于M的交错圈，已知G中有k条M中的边，k≥1，则C中有（）条边在G中，而不在M中。

答案： k

设G为无孤立点的无向简单图，M既是G中的最大匹配，又是G中的最小边覆盖集，则M应为（）匹配。

答案：完美