词汇表

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

握手和约会

阅读时间: ~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}日期。