网易首页 > 网易号 > 正文 申请入驻

2021年美国数学奥林匹克竞赛中的图论问题——到底难在哪里?

0
分享至

普拉纳国家公园由几条在交叉路口交汇的小径组成。。每条小路的两个端点都在两个不同的路口,而每个路口正好是三条小路的端点。小路只在路口相交。最后,没有小路在相同的两个路口开始和结束。下面是一个可能的公园布局的例子,其中有六个路口和九条小路。


一个游客在公园里的行走情况如下:她从一个路口开始,沿着一条小路行走。在第一条小路的尽头,她进入了一个路口并向左转。在下一个路口,她向右转,以此类推,在每个路口交替进行左转和右转。她这样做,直到她回到她开始的那个路口。在公园所有可能的布局中,她在行走过程中进入任何路口的最大可能次数是多少?

这个问题的陈述非常冗长,但是我们有简单图(Simple Graph)工具可以帮助理解(默认为平面图)

简单图是指任意两个顶点之间没有超过一条边,也没有边的起点和终点在同一个顶点的图。换句话说,一个简单的图是一个没有循环和多条边的图。


下面这个简单图中,每个顶点的度数为3(顶点的度数是指和该节点相关联的边的条数)。 让我们看看根据题目要求的方式散步时,在每个顶点左右交替进行会发生什么。


我在每条路径上用字母 "L "和 "R "来表示散步者是左转还是右转。题目要求的是:进入任何路口的最大可能次数。在上面显示的第一条路径中,这个数字是1。

再选择几条路径,我们发现有可能进入一个路口两次。


为了考虑其他可能的行走方式,以更有规律的方向重新绘制图形是有帮助的,这样我们就可以看到对称性。


一旦我们认识到这种对称性,我们就可以看到,在这个公园里没有太多的 "不同 "路径。通过不断尝试,我们发现不可能进入任何路口两次以上。

但这个问题不仅仅是问所提供的公园的例子,而是问 "公园所有可能的布局"。

我认为有两个问题值得考虑。

  1. 对公园的可能布局是否有限制,以帮助我们找到最大值?
  2. 为什么会有一个最大值,也就是说,为什么不可能在一个无限循环中不断地进入同一个路口?

可能的公园布局

从考虑最简单的情况开始。给出的例子有6个路口(顶点),但是否有可能出现顶点更少的公园?我发现2个顶点是不可能的,因为 "没有小路在同一个路口开始和结束",也就是说,这个图形是 "简单 "的。


我试着画一个有3个路口的公园,但没有成功,我意识到没有奇数个路口是可行的。因为对于n个路口,边的总数是3n÷2,(与每个顶点相连的3条边,除以2以避免重复计算)。如果n是奇数,这个总数就不是一个整数。

有一个可能有4个路口的公园,但不可能多次进入一个路口。


例子中给出的是一个有6个路口的公园,我没有找到具有6个路口的不同情况,所以我转到了8个路口。



这个图形是我熟悉的立方体的平面嵌入。它让我意识到,所有符合给定条件的公园都可以表示为多面体。这是一个切入点。8个路口的公园不允许任何路口进入一次以上。

对于10个路口,遵循类似的结构,有一个内部和外部的五边形。并尝试了一些不同的走法,我发现有可能进入一个路口3次!

一个路口进入3次的例子


想出这个结构后,我觉得3可能是最大的可能。

另外,这时我已经意识到,可能的公园有无限的变化,为了解决问题,我不能轻易地进行分类。


  • 可能的公园布局情况

因此,我决定从我之前提出的关于无限循环的可能性的问题出发,重新审视这个问题。

排除无限循环的可能性

根据题意,散步者回到起点时将会停止。那么,有没有可能进入一个不包括起点的无限循环?这个无限循环会是什么样子呢?

在不失一般性的前提下,我们假设散步者进入了假设的无限循环,并向右转。


这意味着它必须以左转来结束这个循环,然后再右转来重复这个循环。但由于她是从另一个方向来的,右转会使她离开循环,如上面的动画所示。

因此,我们已经表明,无论任何路口的最大入口数是多少,它至少是有限的!这就是我们的观察。

关键是观察,路径是确定性的

一个重要的观察结果是,一旦我们知道散步者是在某条小路(边)上向左转还是向右转,接下来的每条小路就只有一种可能的选择。同样地,前一条小路也只有一种可能的选择,以此类推。所以她的整个路径是完全确定的。

我们也已经表明,不可能进入一个无限的循环,因为她回到起点后就停止了。所以不可能在一条特定的小路上左转两次,也不可能在一条特定的小路上右转两次。

这就把最大的可能上界减少到了6个(向左或向右转入3条小路的每个路口)。


但它实际上有可能实现吗?

当她进入一个路口左转时,她必须右转离开(反之亦然)。所以我应该在图中加入出口。它将有6个箭头进入,和6个箭头出来。

总之,有些地方不对。为了走完所有这些路径,她必须从她已经走过的路回来,但方向是相反的。

在下图中,只包括了4个箭头。橙色的箭头表示她左转进入路口,右转出来,蓝色的箭头表示她后面需要走的相反方向。


为什么这是不可能的?

正如我们之前所说,一旦我们知道路线和方向(左或右),整个路径就完全确定了。特别是,一旦我们知道她沿着橙色箭头左转进入路口,我们就知道她的整个路径形成了一个循环,从起点开始,在某个时间返回那里。


为了沿着蓝色箭头行走,她需要走这个完全相同的循环,但方向相反。这是不可能的。一旦开始走这条路,就真的没有回头路了!这限制了可能的最大数量。

这个限制将一个路口的最大可能进入次数限制为3次。下面显示了两种可能性,根据进入-退出顺序用颜色编码。


我们已经展示了一个实现最大3次的公园的例子(上面的五边形棱形结构)。

所以在公园所有可能的布局中,3是她在行走过程中进入任何路口的最大可能次数。

图论真了不起

图论是离散数学的一个迷人的领域,有很多实际应用。特别是世界网络和社交媒体的出现。

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
男人“射精”时为什么会心情愉悦?原因有3,事后也别忘做好3事

男人“射精”时为什么会心情愉悦?原因有3,事后也别忘做好3事

健康播报
2021-12-02 17:14:43
美国危机来临,中国连抛3425亿美债,美财长态度突然反转

美国危机来临,中国连抛3425亿美债,美财长态度突然反转

灰太狼带你看娱乐
2021-12-03 07:20:25
在南非感染奥密克戎的江苏男子:半年前曾感染新冠,这次特别渴

在南非感染奥密克戎的江苏男子:半年前曾感染新冠,这次特别渴

极目新闻
2021-12-03 16:34:21
死刑!立即执行!广西男子当街打死70岁越战老兵,终于判了

死刑!立即执行!广西男子当街打死70岁越战老兵,终于判了

第一军情
2021-12-03 16:11:53
江苏人妻因房事欲求不满闹上法院,妻子:一周我要3次!丈夫:你想都不要想...

江苏人妻因房事欲求不满闹上法院,妻子:一周我要3次!丈夫:你想都不要想...

最潮生活
2021-12-03 01:59:32
三胎产下三胞胎儿子,两天喝光三罐奶粉,爸爸月入一万不够养家

三胎产下三胞胎儿子,两天喝光三罐奶粉,爸爸月入一万不够养家

小岛访谈录
2021-12-03 18:40:17
老婆列假来了近一个月,老公陪她去检查,趁她缴费时,医生:报警

老婆列假来了近一个月,老公陪她去检查,趁她缴费时,医生:报警

解语爱生活
2021-12-03 11:48:04
“我眼泪都快掉下来了”!医保谈判代表一句话,上了三个热搜

“我眼泪都快掉下来了”!医保谈判代表一句话,上了三个热搜

环球网资讯
2021-12-03 16:29:42
尘封18年大案重启:河南省司法厅原厅长被指当“保护伞”

尘封18年大案重启:河南省司法厅原厅长被指当“保护伞”

中国网资讯
2021-12-03 09:52:18
当了十多年房东,突然倒欠租客10万元?上海女子一夜白头!

当了十多年房东,突然倒欠租客10万元?上海女子一夜白头!

新民晚报
2021-12-03 10:50:40
气功大师王林开光时女星云集,以求菩萨保佑,开光须得在床上

气功大师王林开光时女星云集,以求菩萨保佑,开光须得在床上

局小乖简史
2021-12-03 10:49:08
55岁华裔富婆身价10个亿,多次拒绝泰王追求,王后都要怕她三分

55岁华裔富婆身价10个亿,多次拒绝泰王追求,王后都要怕她三分

鬼谷子思维
2021-12-03 17:36:13
1999年陕西一砖厂挖出价值20亿的金饼,被村民一抢而光,结果如何

1999年陕西一砖厂挖出价值20亿的金饼,被村民一抢而光,结果如何

柳婉月
2021-12-02 23:19:17
尴尬了!立陶宛体育部长宣布不会出席北京冬奥会,外界并无反应

尴尬了!立陶宛体育部长宣布不会出席北京冬奥会,外界并无反应

玉兔捣药
2021-12-03 14:39:29
中年大妈公园里做皮肉生意,20元一次,老头带饭排队等候:很划算

中年大妈公园里做皮肉生意,20元一次,老头带饭排队等候:很划算

夕阳情感屋
2021-12-03 14:38:50
女子与老男人发生关系,因男子使用工具,心理难以接受而报警

女子与老男人发生关系,因男子使用工具,心理难以接受而报警

身边的刑法故事
2021-12-02 22:58:27
立陶宛被中国海关系统删除?律师:如删除代码336,确实无法报关

立陶宛被中国海关系统删除?律师:如删除代码336,确实无法报关

吴国雄海关律师
2021-12-03 17:41:17
中国危险了?日本突然急于签署日俄和平条约:一刻也不想等

中国危险了?日本突然急于签署日俄和平条约:一刻也不想等

利刃号
2021-12-03 09:44:06
12小时内被强制灌水120斤:她们无能为力,只能挣扎着死去

12小时内被强制灌水120斤:她们无能为力,只能挣扎着死去

看得见的生活
2021-12-03 13:28:26
张无忌为明教第34任教主,那前33任都是谁?全名人,名字有点耳熟

张无忌为明教第34任教主,那前33任都是谁?全名人,名字有点耳熟

花不见叶
2021-11-29 18:14:28
2021-12-03 20:32:49
老胡说科学
老胡说科学
科学如此美妙,我想让你知道
854文章数 26984关注度
往期回顾 全部

教育要闻

125万考生一本率不到12%!这个省果不其然从没让人失望过……

头条要闻

德国候任外长声称要“对华强硬” 中国驻德使馆回应

头条要闻

德国候任外长声称要“对华强硬” 中国驻德使馆回应

体育要闻

这个"球"真不错!乔丹这回没看走眼

娱乐要闻

汪小菲有新欢?女方甜蜜依偎他怀里

财经要闻

科技要闻

爱奇艺新员工吐槽赔偿:工资60元/天加会员卡

汽车要闻

宝马新款X7上市 除入门车型全系价格上调5万

态度原创

时尚
教育
亲子
本地
游戏

她才25岁?怎么那么会穿啊

教育要闻

125万考生一本率不到12%!这个省果不其然从没让人失望过……

亲子要闻

养男孩如养哈士奇,不是他疯,就是你疯

本地新闻

焦虑症千万别玩,一局就是400天

盟重英雄冰雪传奇游戏,单职业和三职业哪个更好玩