作者yonex (诸法皆空)
看板tutor
标题Re: [问题] 一笔划成的图形
时间Thu Mar 23 21:38:49 2006
※ 引述《yonex (诸法皆空)》之铭言:
: ※ 引述《britneycafe (嘟嘟嘟)》之铭言:
: : 请问一下,给你各种图形要怎麽判断图形可不可以一笔划成呀??
: : 是判断一个点连几条线去分吗??一。一
: : ‧
: : │
: : │
: : ‧──‧──‧
: : ......其他图形我不会画,画了一个最简单的 0rz
: 1. 图要连通
: (分裂的图没办法一笔画,笔一定要拿起来)
: 2. 除了起点与终点(起终点可任选),
: 每个『节点』所延伸出来的路径,都要是偶数
: (想一想....要求逛完全部的大街小巷,路又不能重复走,
: 除了起点与终点,其余所以节点都要一进一出。不能进了出不去呀!)
: 1.2.都要满足,才可以一笔画,在数学上这叫 Euler trial
: 你那张图,第二条件不满足
多讲几句赘言好了...
封闭的图,一笔画肯定起终点重合,那麽每个节点延伸的路径都必须是偶数
不封闭的图,一笔画肯定起终点不能重合,那麽仅能有两个节点延伸的路径为奇数
其他节点都必须为偶数
当然,图都不可以分裂。
条件1与2之联集 为 一笔画 之充分必要条件
封闭的一笔画称为Euler circuit (欧拉回圈?)
不封闭的一笔画称为Euler trial (不知道怎麽翻译)
你可以解柯尼斯堡(Konigsberg)七桥问题了....
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.67.107.200