用語集

左側のキーワードの1つを選択…

握手とデート

読書の時間: ~10 min
このページは自動翻訳されているため、エラーが含まれている可能性があります。翻訳のレビューをご希望の場合はご連絡ください。

友達と一緒に素敵な誕生日パーティーに招待されました。あなた自身とホストを含めて、 ${hnd}人々が存在します。

夕方、ゲストが出発する準備ができると、誰もが他の人と握手します。握手は全部でいくつありますか?

グラフを使用してハンドシェイクを表すことができます。すべての人が 、そしてすべてのハンドシェイクは

これで、グラフのエッジの数を数えることが簡単になりました。そこに${hnd}人、あります${hnd*(hnd-1)/2}握手。

大きなグラフのすべてのエッジを数えるのではなく、 _任意の_数のゲストの結果を示す単純な式を見つけることもできます。

それぞれの${n}パーティーの人々は握手${n-1}その他。それは${n} × ${n-1} = ${n×(n-1)}合計で握手。 n人の場合、ハンドシェイクの数は

残念ながら、この回答は正しくありません。方法に注意してください一番上の行の最初の2つのエントリ実際には同じですが、反転します。

実際、すべてのハンドシェイクをカウント関係する2人それぞれに1回ずつ。これは、正しい数のハンドシェイクが${n}ゲストは${n}×${n-1}2=${n*(n-1)/2}

すべての頂点が他のすべての頂点に接続されているため、ハンドシェイクグラフは特別です。このプロパティを持つグラフは完全グラフと呼ばれます 。 4つの頂点を持つ完全なグラフは、しばしば次のように省略されます。 K4 、5つの頂点を持つ完全なグラフはK5 、 等々。

完全なグラフがn頂点、 Kn 、持っているn×n12エッジ。

別の日に、あなたはのスピードデートイベントに招待されています${m}男の子と${f}女の子。小さなテーブルがたくさんあり、すべての男の子が各女の子と5分を過ごします。個別の「日付」は合計でいくつありますか?

この場合、対応するグラフは、頂点の2つの別個のセットで構成されます。すべての頂点はすべての頂点に接続されていますセットが、 の頂点のどれもセット。このレイアウトのグラフは、 2部グラフと呼ばれます

サイズxyの 2つのセットを持つ2部グラフは、 Kx,y 。それは持っていますエッジ、 つまり、上記の例では、 ${m} × ${f} = ${m×f}日付。