题目内容

Given the same 3 men and 3 women as exercise 1. Which of the following misrepresentation can make Grace obtain better partner for herself in the returned matching?

A. Grace lies "I prefer David to Jack"
B. Grace lies "I prefer Jack to Bob"
C. Grace lies "I prefer David to Bob"

查看答案

搜索结果不匹配？点我反馈

更多问题

Gale-Shapley algorithm finds______.

A. a perfect matching without stability
B. possible different assignments among all executions
C. the man-optimal assignment which is a stable matching

查看答案

Given the same 3 men and 3 women as exercise 1. Which one is the result of Gale-Shapley algorithm?

A. Bob-Grace, Jack-Anna, David-Alice
Bob-Alice, Jack-Grace, David-Anna
C. Bob-Anna, Jack-Grace, David-Alice

查看答案

There is a directed graph $G = (V;E)$ with $n$ nodes and $m$ edges. Can one determine if $G$ is strongly connected in $O(m + n)$ time?

A. Yes
B. No
C. Depending on $V$ and $E$

查看答案

A graph G is bipartite iff _____.

A. it contains no even length cycle
B. it contains no odd length cycle
C. it contains no cycle

查看答案

Given the same 3 men and 3 women as exercise 1. Which of the following misrepresentation can make Grace obtain better partner for herself in the returned matching?

A. Grace lies "I prefer David to Jack" B. Grace lies "I prefer Jack to Bob" C. Grace lies "I prefer David to Bob"

Gale-Shapley algorithm finds______.

Given the same 3 men and 3 women as exercise 1. Which one is the result of Gale-Shapley algorithm?

There is a directed graph $G = (V;E)$ with $n$ nodes and $m$ edges. Can one determine if $G$ is strongly connected in $O(m + n)$ time?

A graph G is bipartite iff _____.

A. Grace lies "I prefer David to Jack"
B. Grace lies "I prefer Jack to Bob"
C. Grace lies "I prefer David to Bob"