Untitled Course握手とデート

友達と一緒に素敵な誕生日パーティーに招待されました。あなた自身とホストを含めて、 ${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×n−12エッジ。

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

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

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

言語を変えてください