T*******x 发帖数: 8565 | 1 任意一棵树,图论中的树,呵呵,假设有n个node,n-1个edge。证明:可以在每个node
和每个edge上放一个1到2n-1之间的数,node上放奇数,edge上放偶数,不重复,使任
意一个edge上的数等于相连的两
个node上的数之差。 |
l**********3 发帖数: 10970 | |
T*******x 发帖数: 8565 | 3 你再看看。
【在 l**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能不要老弄小学生加分题来糊弄好吗
|
b******r 发帖数: 1 | 4 显然不可能。。。
2n-1里找n 个正整数,没法保证差两两不相等。。 |
T*******x 发帖数: 8565 | 5 怎么就不可能啊?
1-5-3
中间放4和2。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 显然不可能。。。 : 2n-1里找n 个正整数,没法保证差两两不相等。。
|
z***t 发帖数: 10817 | 6 令2n - 1为root
left child 1 , 2n-5, 5, 2n - 9 ...
right child 2n -3 , 3, 2n -7,
差就是2n-2 2n-4 。。。 2
程序这么写
证明用数学归纳法
n = 1 2 3都成立
假设 n = k成立
当n = k + 1时 依次把node上2k+1顺移到2k-1 edge不变 |
z***t 发帖数: 10817 | 7 没说二叉树
可以是 n-1叉
1 -2- 3
-4- 5
-6- 7
……
-2n-2-- 2n - 1
对不对 都不用证明 |
T*******x 发帖数: 8565 | 8 任意树。没说二叉树。
【在 z***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没说二叉树 : 可以是 n-1叉 : 1 -2- 3 : -4- 5 : -6- 7 : …… : -2n-2-- 2n - 1 : 对不对 都不用证明
|
b******r 发帖数: 1 | 9 呃,我想差了。并不需要遍历所有的两两之差。
不过你这个例子给了很强的提示呀:node奇数,edge偶数。呵呵。
: 怎么就不可能啊?
: 1-5-3
: 中间放4和2。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任意树。没说二叉树。
|
T*******x 发帖数: 8565 | 10 如果是单链结构,那算比较简单的。
如果是甲烷那种结构,甚至更复杂,就没那么容易了。哦,甲烷是简单的,乙烷,丙烷
,丙烯,这就复杂了。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃,我想差了。并不需要遍历所有的两两之差。 : 不过你这个例子给了很强的提示呀:node奇数,edge偶数。呵呵。 : : : 怎么就不可能啊? : : 1-5-3 : : 中间放4和2。 :
|
|
|
b******r 发帖数: 1 | 11 没有分叉就是这样震荡的排91753。按每个点的值定义高度,用归纳。加入一个点以后
就把这个点右边和上边所有点加上2。
感觉应该有什么不用归纳的更本质的办法。
: 怎么就不可能啊?
: 1-5-3
: 中间放4和2。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是单链结构,那算比较简单的。 : 如果是甲烷那种结构,甚至更复杂,就没那么容易了。哦,甲烷是简单的,乙烷,丙烷 : ,丙烯,这就复杂了。
|
T*******x 发帖数: 8565 | 12 这个也可以出一个编程算法题,但是比较简单,数学证明难多了。
node
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任意一棵树,图论中的树,呵呵,假设有n个node,n-1个edge。证明:可以在每个node : 和每个edge上放一个1到2n-1之间的数,node上放奇数,edge上放偶数,不重复,使任 : 意一个edge上的数等于相连的两 : 个node上的数之差。
|
T*******x 发帖数: 8565 | 13 来看个乙烷结构树的结果:
C3H7H9H11
C15H1H5H13
两个C互相连接,每个C和3个H连接,节点上的数如上,可保证相连节点之差不重复。
手算可不容易。但是机算很容易。但是证明可不容易。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个也可以出一个编程算法题,但是比较简单,数学证明难多了。 : : node
|
b******r 发帖数: 1 | 14 看我楼上的证明呀。。。
: 来看个乙烷结构树的结果:
: C3H7H9H11
: C15H1H5H13
: 两个C互相连接,每个C和3个H连接,节点上的数如上,可保证相连节点之差不重
复。
: 手算可不容易。但是机算很容易。但是证明可不容易。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 来看个乙烷结构树的结果: : C3H7H9H11 : C15H1H5H13 : 两个C互相连接,每个C和3个H连接,节点上的数如上,可保证相连节点之差不重复。 : 手算可不容易。但是机算很容易。但是证明可不容易。
|
T*******x 发帖数: 8565 | 15 你那篇我看过,我没觉得你是在写证明。又看了一遍,你好像是解决了单链树的问题。
是吗?我都说了,单链树是简单的,原问题是任意树。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看我楼上的证明呀。。。 : : : 来看个乙烷结构树的结果: : : C3H7H9H11 : : C15H1H5H13 : : 两个C互相连接,每个C和3个H连接,节点上的数如上,可保证相连节点之差不重 : 复。 : : 手算可不容易。但是机算很容易。但是证明可不容易。 :
|
b******r 发帖数: 1 | 16 就是任意树。
新加进来的节点可以加到任何位置。
: 你那篇我看过,我没觉得你是在写证明。又看了一遍,你好像是解决了单链树的
问题。
: 是吗?我都说了,单链树是简单的,原问题是任意树。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你那篇我看过,我没觉得你是在写证明。又看了一遍,你好像是解决了单链树的问题。 : 是吗?我都说了,单链树是简单的,原问题是任意树。
|
T*******x 发帖数: 8565 | 17 要不你试一个?你那篇给出的单链的例子就不对:91753,这不行。当然,单链是容易
的,你可以在此基础上试一下,就试乙烷结构树就行,CH3-CH3,就用你的方法,给出
答案我看看行不行。你的方法我没太看懂,所以你自己给出答案。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是任意树。 : 新加进来的节点可以加到任何位置。 : : : 你那篇我看过,我没觉得你是在写证明。又看了一遍,你好像是解决了单链树的 : 问题。 : : 是吗?我都说了,单链树是简单的,原问题是任意树。 :
|
b******r 发帖数: 1 | 18 啥是ch3ch3?
......
: 要不你试一个?你那篇给出的单链的例子就不对:91753,这不行。当然,单链
是容易
: 的,你可以在此基础上试一下,就试乙烷结构树就行,CH3-CH3,就用你的方法
,给出
: 答案我看看行不行。你的方法我没太看懂,所以你自己给出答案。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要不你试一个?你那篇给出的单链的例子就不对:91753,这不行。当然,单链是容易 : 的,你可以在此基础上试一下,就试乙烷结构树就行,CH3-CH3,就用你的方法,给出 : 答案我看看行不行。你的方法我没太看懂,所以你自己给出答案。
|
b******r 发帖数: 1 | 19 笔误,91735 保持上下震荡。
: 要不你试一个?你那篇给出的单链的例子就不对:91753,这不行。当然,单链
是容易
: 的,你可以在此基础上试一下,就试乙烷结构树就行,CH3-CH3,就用你的方法
,给出
: 答案我看看行不行。你的方法我没太看懂,所以你自己给出答案。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要不你试一个?你那篇给出的单链的例子就不对:91753,这不行。当然,单链是容易 : 的,你可以在此基础上试一下,就试乙烷结构树就行,CH3-CH3,就用你的方法,给出 : 答案我看看行不行。你的方法我没太看懂,所以你自己给出答案。
|
T*******x 发帖数: 8565 | 20 乙烷的分子式。
两个C相连,每个C上连了三个H。把C和H看做node,把连接看成edge,这就是一个树,
用你的方法在这个树上试试,给出答案,我看看对不对,也学学你的方法。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啥是ch3ch3? : ...... : : : 要不你试一个?你那篇给出的单链的例子就不对:91753,这不行。当然,单链 : 是容易 : : 的,你可以在此基础上试一下,就试乙烷结构树就行,CH3-CH3,就用你的方法 : ,给出 : : 答案我看看行不行。你的方法我没太看懂,所以你自己给出答案。 :
|
|
|
p*******w 发帖数: 1381 | 21 最恶心的是国内的中小学数学培训班非要起名为“兴趣班” 就是把小孩最没兴趣的事
强行洗脑成兴趣 |
B*********L 发帖数: 700 | 22 先证明:
1. node上是奇数,edge上一定是偶数。
2.然后证明n是奇数时,以n-1为中心,存在n-1对整数:n-1-x和n-1+x,x在。。。范围内
3.再证明n是偶数时。。。。。。
4.之后根据2和3,证明edge。。
这样算吗?
node
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任意一棵树,图论中的树,呵呵,假设有n个node,n-1个edge。证明:可以在每个node : 和每个edge上放一个1到2n-1之间的数,node上放奇数,edge上放偶数,不重复,使任 : 意一个edge上的数等于相连的两 : 个node上的数之差。
|
b******r 发帖数: 1 | 23 先写最长的一串:7153。
然后在5上插一个点。753都加上2,新加进来的点于是就是3变成9175
3
再加一个点变成11 1 9 7
3 5
3,5都连在9上面。
然后在1上面插如新的点。
变成
13 1 9 7
11 3 5
11连在1上面,3 5连在9上面。
再插入一个点,变成:
15 1 9 7
13 11 3 5
13, 11 连在1上面,3,5连在9上面。
: 乙烷的分子式。
: 两个C相连,每个C上连了三个H。把C和H看做node,把连接看成edge,这就是一
个树,
: 用你的方法在这个树上试试,给出答案,我看看对不对,也学学你的方法。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 乙烷的分子式。 : 两个C相连,每个C上连了三个H。把C和H看做node,把连接看成edge,这就是一个树, : 用你的方法在这个树上试试,给出答案,我看看对不对,也学学你的方法。
|
T*******x 发帖数: 8565 | 24 结果是对的。但是算法描述上,好像还不清楚。比如第一步,从7153开始,在5上插一
点,插的是什么数?是3吗?所以原有大于等于3的数都加2。为什么要插3?怎么描述这
个算法?
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先写最长的一串:7153。 : 然后在5上插一个点。753都加上2,新加进来的点于是就是3变成9175 : 3 : 再加一个点变成11 1 9 7 : 3 5 : 3,5都连在9上面。 : 然后在1上面插如新的点。 : 变成 : 13 1 9 7 : 11 3 5
|
T*******x 发帖数: 8565 | 25 这个算个开头吧。后面你想清楚没有?
围内
【在 B*********L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先证明: : 1. node上是奇数,edge上一定是偶数。 : 2.然后证明n是奇数时,以n-1为中心,存在n-1对整数:n-1-x和n-1+x,x在。。。范围内 : 3.再证明n是偶数时。。。。。。 : 4.之后根据2和3,证明edge。。 : 这样算吗? : : node
|
b******r 发帖数: 1 | 26 每个节点的数值定义为该点的高度。
把这个树排成上下震荡的,并且从左到右振幅越来越小。
加入一个新的节点的时候保持该节点右侧振幅不变,左侧振幅加2。
比如7 1 5 3在5加入节点的时候5的右边,上边数(包括5本身)值都加2。于是7变9,5变
7,3变5,1不变。新加入的节点于是就是3.
每个节点都是一个局部最大或最小值。
如果在局部最小值上加一个新的节点,稍有不同,但思想一样,保证节点右边振幅不变
,左边振幅加2。
: 结果是对的。但是算法描述上,好像还不清楚。比如第一步,从7153开始,在5
上插一
: 点,插的是什么数?是3吗?所以原有大于等于3的数都加2。为什么要插3?怎么
描述这
: 个算法?
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个算个开头吧。后面你想清楚没有? : : 围内
|
c****8 发帖数: 1 | 27 你就是干苦力的命,认了吧,琢磨数学没用
盹盹盹
:任意一棵树,图论中的树,呵呵,假设有n个node,n-1个edge。证明:可以在每个
node和每个edge上放一个1到2n-1之间的数,node上放奇数,edge上放偶数,不重复,
使任
:意一个edge上的数等于相连的两
:个node上的数之差。
:☆ 发自 iPhone 买买提 1.24.09
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个算个开头吧。后面你想清楚没有? : : 围内
|
T*******x 发帖数: 8565 | 28 嗯。有意义。
咱们再想两天。星期五晚上,我给答案。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每个节点的数值定义为该点的高度。 : 把这个树排成上下震荡的,并且从左到右振幅越来越小。 : 加入一个新的节点的时候保持该节点右侧振幅不变,左侧振幅加2。 : 比如7 1 5 3在5加入节点的时候5的右边,上边数(包括5本身)值都加2。于是7变9,5变 : 7,3变5,1不变。新加入的节点于是就是3. : 每个节点都是一个局部最大或最小值。 : 如果在局部最小值上加一个新的节点,稍有不同,但思想一样,保证节点右边振幅不变 : ,左边振幅加2。 : : : 结果是对的。但是算法描述上,好像还不清楚。比如第一步,从7153开始,在5
|
l*******k 发帖数: 922 | 29 搞那么复杂干嘛?中间一个1,然后3,5,..., 2n-1全部只连到1不就完了?也就是说
是个星型。
树的定义是没有cycle就行了,星型也是树。 |
T*******x 发帖数: 8565 | 30 树是给定的,不是你自己定的。
【在 l*******k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 搞那么复杂干嘛?中间一个1,然后3,5,..., 2n-1全部只连到1不就完了?也就是说 : 是个星型。 : 树的定义是没有cycle就行了,星型也是树。
|
|
|
T*******x 发帖数: 8565 | 31 你不是在写证明吧?我怕漏了你,确认一下。
【在 z***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没说二叉树 : 可以是 n-1叉 : 1 -2- 3 : -4- 5 : -6- 7 : …… : -2n-2-- 2n - 1 : 对不对 都不用证明
|
T*******x 发帖数: 8565 | 32 把你给漏了。你哪冒出来的?呵呵。
【在 c****8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你就是干苦力的命,认了吧,琢磨数学没用 : 盹盹盹 : : :任意一棵树,图论中的树,呵呵,假设有n个node,n-1个edge。证明:可以在每个 : node和每个edge上放一个1到2n-1之间的数,node上放奇数,edge上放偶数,不重复, : 使任 : :意一个edge上的数等于相连的两 : :个node上的数之差。 : :☆ 发自 iPhone 买买提 1.24.09
|
T*******x 发帖数: 8565 | 33 你这个算法,可能还是没描述清楚,或者是没有完全走通。
咱们来看看丙烷结构树:CH3-CH2-CH3,三个C一字相连,两边的C各连三个H,中间的C
连两个H。把C和H看成节点,这是一个树,有11个节点,10个边。
用你的方法来试试,先找出最长的链:H-C-C-C-H。从左到右,填上19375。然后看节点
7,也就是从右边数第二个。想要插入一个数连在这个节点上。插什么数呢?这个地方
有规则吗?确定的规则。我试了一下,插入3不行,但是插入5可以。然后原树中大于等
于5的数加2,小于5的数不变。然后我在同一个节点上又试插了一个数,可以。接下来
每步都需要试验,我没有走通。
你可以试图证明如下论断:
在任意一棵树,以及已经满足条件的数的安排,之上,在任意节点上,都存在一个数,
奇数,从1到原树最大数加2之间,连接到该节点,把原树中大于等于插入数的数加2,
小于插入数的数不变,新的安排仍然满足条件。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每个节点的数值定义为该点的高度。 : 把这个树排成上下震荡的,并且从左到右振幅越来越小。 : 加入一个新的节点的时候保持该节点右侧振幅不变,左侧振幅加2。 : 比如7 1 5 3在5加入节点的时候5的右边,上边数(包括5本身)值都加2。于是7变9,5变 : 7,3变5,1不变。新加入的节点于是就是3. : 每个节点都是一个局部最大或最小值。 : 如果在局部最小值上加一个新的节点,稍有不同,但思想一样,保证节点右边振幅不变 : ,左边振幅加2。 : : : 结果是对的。但是算法描述上,好像还不清楚。比如第一步,从7153开始,在5
|
b*******8 发帖数: 37364 | 34 看了一下,似乎可以用类似归纳的方法慢慢缩小树的规模,但要保持小树的性质,比如
1在树中的位置,有些麻烦。似乎不能一步证明,要搞两三个引理什么的。 |
b******r 发帖数: 1 | 35 你不要想要插入几。只管把该加的节点加上2,剩下的是几就分配给新的节点。
91735在7上加节点,那么9735(7右边和上边的节点,包括7本身)都加上2变成11 1 9 5
7还有3没分配,于是新的节点就是3。
: 你这个算法,可能还是没描述清楚,或者是没有完全走通。
: 咱们来看看丙烷结构树:CH3-CH2-CH3,三个C一字相连,两边的C各连三个H,中
间的C
: 连两个H。把C和H看成节点,这是一个树,有11个节点,10个边。
: 用你的方法来试试,先找出最长的链:H-C-C-C-H。从左到右,填上19375。然后
看节点
: 7,也就是从右边数第二个。想要插入一个数连在这个节点上。插什么数呢?这
个地方
: 有规则吗?确定的规则。我试了一下,插入3不行,但是插入5可以。然后原树中
大于等
: 于5的数加2,小于5的数不变。然后我在同一个节点上又试插了一个数,可以。
接下来
: 每步都需要试验,我没有走通。
: 你可以试图证明如下论断:
: 在任意一棵树,以及已经满足条件的数的安排,之上,在任意节点上,都存在一
个数,
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个算法,可能还是没描述清楚,或者是没有完全走通。 : 咱们来看看丙烷结构树:CH3-CH2-CH3,三个C一字相连,两边的C各连三个H,中间的C : 连两个H。把C和H看成节点,这是一个树,有11个节点,10个边。 : 用你的方法来试试,先找出最长的链:H-C-C-C-H。从左到右,填上19375。然后看节点 : 7,也就是从右边数第二个。想要插入一个数连在这个节点上。插什么数呢?这个地方 : 有规则吗?确定的规则。我试了一下,插入3不行,但是插入5可以。然后原树中大于等 : 于5的数加2,小于5的数不变。然后我在同一个节点上又试插了一个数,可以。接下来 : 每步都需要试验,我没有走通。 : 你可以试图证明如下论断: : 在任意一棵树,以及已经满足条件的数的安排,之上,在任意节点上,都存在一个数,
|
l**o 发帖数: 131 | 36 从头开始一个个加节点来构造结果,保持一下属性:和最大节点V连接的边(s)是在最大
的边(s),而且移去这个最大节点V后剩下G-V也有这个属性,这就可以保证只要你按节
点大小来增加节点Label,你不会遇到重复。
剩下的就好办了,假定你已经构造了k个节点的G_k, G_k当然是原G的子图,加一个节点
v, 然后从最大节点开始+2,如果找不到合适的Label给v, 就继续给次大节点加2. |
T*******x 发帖数: 8565 | 37 试试丙烷结构吧。
【在 l**o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从头开始一个个加节点来构造结果,保持一下属性:和最大节点V连接的边(s)是在最大 : 的边(s),而且移去这个最大节点V后剩下G-V也有这个属性,这就可以保证只要你按节 : 点大小来增加节点Label,你不会遇到重复。 : 剩下的就好办了,假定你已经构造了k个节点的G_k, G_k当然是原G的子图,加一个节点 : v, 然后从最大节点开始+2,如果找不到合适的Label给v, 就继续给次大节点加2.
|
T*******x 发帖数: 8565 | 38 单链中一个节点可以谈左右,插入一个数之后,这个节点就不光有左右了,还有新插入
的数呢。如果想再在该节点插入一个数,怎么办?
5
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你不要想要插入几。只管把该加的节点加上2,剩下的是几就分配给新的节点。 : 91735在7上加节点,那么9735(7右边和上边的节点,包括7本身)都加上2变成11 1 9 5 : 7还有3没分配,于是新的节点就是3。 : : : 你这个算法,可能还是没描述清楚,或者是没有完全走通。 : : 咱们来看看丙烷结构树:CH3-CH2-CH3,三个C一字相连,两边的C各连三个H,中 : 间的C : : 连两个H。把C和H看成节点,这是一个树,有11个节点,10个边。 : : 用你的方法来试试,先找出最长的链:H-C-C-C-H。从左到右,填上19375。然后 : 看节点
|
T*******x 发帖数: 8565 | 39 This problem has remained unsolved since 1967. It’s still open.
https://youtu.be/v5KWzOOhZrw
哈哈。
node
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任意一棵树,图论中的树,呵呵,假设有n个node,n-1个edge。证明:可以在每个node : 和每个edge上放一个1到2n-1之间的数,node上放奇数,edge上放偶数,不重复,使任 : 意一个edge上的数等于相连的两 : 个node上的数之差。
|
b******r 发帖数: 1 | 40 呃,中计了,我对图论一无所知。
仔细想了下我的办法只对caterpillar tree 有效。。
: This problem has remained unsolved since 1967. It’s still open.
: https://youtu.be/v5KWzOOhZrw
: 哈哈。
: node
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : This problem has remained unsolved since 1967. It’s still open. : https://youtu.be/v5KWzOOhZrw : 哈哈。 : : node
|
|
|
T*******x 发帖数: 8565 | 41 嗯。也不错了。我觉得好问题就是这样,它让你一个species一个species研究,内容博
大精深。
【在 b******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃,中计了,我对图论一无所知。 : 仔细想了下我的办法只对caterpillar tree 有效。。 : : : This problem has remained unsolved since 1967. It’s still open. : : https://youtu.be/v5KWzOOhZrw : : 哈哈。 : : node :
|