2009-06-25 倍数グラフ quiz 任意のグラフG(V,E)に対し、以下の条件を満たすような Vから自然数への単射fは存在するでしょうか。 条件: f(u)がf(v)の倍数または約数 ⇔ (u,v)∈E 存在しないグラフがあるとの答えをだした後にこのようなことを思った。 ありゃー、 できないんだったら出題するわけないよなと 帰納法するためにちょっと書き出したら |V|==3 で これはできないと感じて作ったのが上です。 なんていうか、 出題者が答えを知っているか否かを知っているか否かで 方針の立て方が相当変わりますね。