词汇表

选择左侧的一个关键字...

握手和约会

阅读时间: ~10 min
此页面已自动翻译,可能包含错误。如果您想帮助我们审核翻译,请与我们取得联系!

已邀请您与朋友一起参加精彩的生日聚会。包括你自己和主人,有${hnd}人们在场。

到了晚上,当客人准备离开时,每个人都与其他人握手。总共有多少次握手?

我们可以用图形来表示握手:每个人都是 ,并且每一次握手是

现在很容易计算图中的边数。我们发现${hnd}个人,会有${hnd*(hnd-1)/2}次握手。

除了计算大型图中的所有边,我们还可以尝试找到一个简单的公式,该公式可以告诉我们_任意_数量的来宾的结果。

聚会上的${n}个人,每人都与其他${n-1}个人握手。使得总共握手数为${n} × ${n-1} = ${n×(n-1)}。对于n个人,握手次数为

不幸的是,这个答案不太正确。注意第一行的前两个条目其实是如何一样的,只是翻转了。

实际上,我们已经计算了握手 每回涉及的两个人各一次。这意味着正确的握手次数是${n}个客人${n}×${n-1}2=${n*(n-1)/2} 次。

握手图是特殊的,因为每个顶点都与其他每个顶点相连。具有此属性的 称为 完全图 。具有4个顶点的完全图形通常缩写为K4 ,具有5个顶点的完全图形称为K5 , 等等。

我们刚刚显示的具有n顶点Kn , 有n×n12边缘。

在另一天,我们邀请您参加${m}个男孩和${f}个女孩的约会。有很多小桌子,每个男孩和每个女孩在一起都花5分钟。总共有多少个单独的“约会”?

在这种情况下,对应的图由两组单独的顶点组成。每个顶点都连接到所有顶点,但没有顶点在集合。具有这种布局的称为二分图

具有两组大小为xy的二分图通常写为Kx,y 。它有条边, 这意味着在上面的示例中有${m} × ${f} = ${m×f}次约会。