アカウント名:
パスワード:
前提条件:
昔、オートマトン理論を少しかじったものですが、実はこの問題の限定された場合をタネにした手品(っぽいもの)があります。
色分け済みのグラフ(実際は地図とか部屋の見取り図とか、親しみのもてそうな図)を観客に配って、 「あなたがどこにいても、私は自分のもとに呼び寄せることができます。」ってやるやつ。 複数の客がみな任意に選んだ違う部屋からスタートするのに、「赤いドアの方に行ってください」「青いドアの方に」って指示された通りに動くと、最後には全員が同じ部屋にたどりつくのを見せられると、けっこう「おおぉーっ」って反応が得られますよ。
最近、似たようなネタを Mr. マリックがやってたけど、これはグラフが殆どスター状になっててよく見てみると仕掛けが読み取れちゃうやつでした。
この問題の面白さは、ゴール地点を変えても任意の頂点からそこへたどりつく色順が存在することなんで、グラフの形をじっと眺めてもなかなか仕掛けは読み取れない。「今度は、私の居場所を変えてみますよ。それでも呼び寄せられます。」ってもう一度やってみせると、さらにインパクトありです。 さらにこれは自分の居場所だけで経路が決まるので、客の居場所の初期値を見ないで誘導してみせると迫力あるかも。
「どのように塗った場合でも」じゃないです。「以下の性質を満たす塗り方が存在する」ですね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
日本発のオープンソースソフトウェアは42件 -- ある官僚
wikioediaの解説をざっと見たところでは (スコア:1)
Re:wikioediaの解説をざっと見たところでは (スコア:2, 興味深い)
前提条件:
Re:wikioediaの解説をざっと見たところでは (スコア:2, 興味深い)
昔、オートマトン理論を少しかじったものですが、実はこの問題の限定された場合をタネにした手品(っぽいもの)があります。
色分け済みのグラフ(実際は地図とか部屋の見取り図とか、親しみのもてそうな図)を観客に配って、 「あなたがどこにいても、私は自分のもとに呼び寄せることができます。」ってやるやつ。
複数の客がみな任意に選んだ違う部屋からスタートするのに、「赤いドアの方に行ってください」「青いドアの方に」って指示された通りに動くと、最後には全員が同じ部屋にたどりつくのを見せられると、けっこう「おおぉーっ」って反応が得られますよ。
最近、似たようなネタを Mr. マリックがやってたけど、これはグラフが殆どスター状になっててよく見てみると仕掛けが読み取れちゃうやつでした。
この問題の面白さは、ゴール地点を変えても任意の頂点からそこへたどりつく色順が存在することなんで、グラフの形をじっと眺めてもなかなか仕掛けは読み取れない。「今度は、私の居場所を変えてみますよ。それでも呼び寄せられます。」ってもう一度やってみせると、さらにインパクトありです。
さらにこれは自分の居場所だけで経路が決まるので、客の居場所の初期値を見ないで誘導してみせると迫力あるかも。
Re:wikioediaの解説をざっと見たところでは (スコア:1)
「どのように塗った場合でも」じゃないです。「以下の性質を満たす塗り方が存在する」ですね。
Re: (スコア:0)
は何かダミーの枝みたいなので何とかなるかもしれないけど、
> 非周期的(aperiodic: グラフ中のすべての閉路について、それらの経路長の最大公約数が1)
を満たせるような実用的な応用ってあるような気がしない。
Re: (スコア:0)
前提部がオイラー路で準備部がグラフ彩色
#思いついただけで、確認もとってないのでAC