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 的大作中提到】
: 能不要老弄小学生加分题来糊弄好吗
|
b******r
发帖数: 1 | 4 显然不可能。。。
2n-1里找n 个正整数，没法保证差两两不相等。。 |
T*******x
发帖数: 8565 | 5 怎么就不可能啊？
1-5-3
中间放4和2。
【在 b******r 的大作中提到】
: 显然不可能。。。
: 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 的大作中提到】
: 没说二叉树
: 可以是 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 的大作中提到】
: 任意树。没说二叉树。
|
T*******x
发帖数: 8565 | 10 如果是单链结构，那算比较简单的。
如果是甲烷那种结构，甚至更复杂，就没那么容易了。哦，甲烷是简单的，乙烷，丙烷
，丙烯，这就复杂了。
【在 b******r 的大作中提到】
: 呃，我想差了。并不需要遍历所有的两两之差。
: 不过你这个例子给了很强的提示呀：node奇数，edge偶数。呵呵。
:
:
: 怎么就不可能啊？
:
: 1-5-3
:
: 中间放4和2。
:
|
|
|
b******r
发帖数: 1 | 11 没有分叉就是这样震荡的排91753。按每个点的值定义高度，用归纳。加入一个点以后
就把这个点右边和上边所有点加上2。
感觉应该有什么不用归纳的更本质的办法。
: 怎么就不可能啊？
: 1-5-3
: 中间放4和2。
【在 T*******x 的大作中提到】
: 如果是单链结构，那算比较简单的。
: 如果是甲烷那种结构，甚至更复杂，就没那么容易了。哦，甲烷是简单的，乙烷，丙烷
: ，丙烯，这就复杂了。
|
T*******x
发帖数: 8565 | 12 这个也可以出一个编程算法题，但是比较简单，数学证明难多了。
node
【在 T*******x 的大作中提到】
: 任意一棵树，图论中的树，呵呵，假设有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 的大作中提到】
: 这个也可以出一个编程算法题，但是比较简单，数学证明难多了。
:
: node
|
b******r
发帖数: 1 | 14 看我楼上的证明呀。。。
: 来看个乙烷结构树的结果：
: C3H7H9H11
: C15H1H5H13
: 两个C互相连接，每个C和3个H连接，节点上的数如上，可保证相连节点之差不重
复。
: 手算可不容易。但是机算很容易。但是证明可不容易。
【在 T*******x 的大作中提到】
: 来看个乙烷结构树的结果：
: C3H7H9H11
: C15H1H5H13
: 两个C互相连接，每个C和3个H连接，节点上的数如上，可保证相连节点之差不重复。
: 手算可不容易。但是机算很容易。但是证明可不容易。
|
T*******x
发帖数: 8565 | 15 你那篇我看过，我没觉得你是在写证明。又看了一遍，你好像是解决了单链树的问题。
是吗？我都说了，单链树是简单的，原问题是任意树。
【在 b******r 的大作中提到】
: 看我楼上的证明呀。。。
:
:
: 来看个乙烷结构树的结果：
:
: C3H7H9H11
:
: C15H1H5H13
:
: 两个C互相连接，每个C和3个H连接，节点上的数如上，可保证相连节点之差不重
: 复。
:
: 手算可不容易。但是机算很容易。但是证明可不容易。
:
|
b******r
发帖数: 1 | 16 就是任意树。
新加进来的节点可以加到任何位置。
: 你那篇我看过，我没觉得你是在写证明。又看了一遍，你好像是解决了单链树的
问题。
: 是吗？我都说了，单链树是简单的，原问题是任意树。
【在 T*******x 的大作中提到】
: 你那篇我看过，我没觉得你是在写证明。又看了一遍，你好像是解决了单链树的问题。
: 是吗？我都说了，单链树是简单的，原问题是任意树。
|
T*******x
发帖数: 8565 | 17 要不你试一个？你那篇给出的单链的例子就不对：91753，这不行。当然，单链是容易
的，你可以在此基础上试一下，就试乙烷结构树就行，CH3-CH3，就用你的方法，给出
答案我看看行不行。你的方法我没太看懂，所以你自己给出答案。
【在 b******r 的大作中提到】
: 就是任意树。
: 新加进来的节点可以加到任何位置。
:
:
: 你那篇我看过，我没觉得你是在写证明。又看了一遍，你好像是解决了单链树的
: 问题。
:
: 是吗？我都说了，单链树是简单的，原问题是任意树。
:
|
b******r
发帖数: 1 | 18 啥是ch3ch3?
......
: 要不你试一个？你那篇给出的单链的例子就不对：91753，这不行。当然，单链
是容易
: 的，你可以在此基础上试一下，就试乙烷结构树就行，CH3-CH3，就用你的方法
，给出
: 答案我看看行不行。你的方法我没太看懂，所以你自己给出答案。
【在 T*******x 的大作中提到】
: 要不你试一个？你那篇给出的单链的例子就不对：91753，这不行。当然，单链是容易
: 的，你可以在此基础上试一下，就试乙烷结构树就行，CH3-CH3，就用你的方法，给出
: 答案我看看行不行。你的方法我没太看懂，所以你自己给出答案。
|
b******r
发帖数: 1 | 19 笔误，91735 保持上下震荡。
: 要不你试一个？你那篇给出的单链的例子就不对：91753，这不行。当然，单链
是容易
: 的，你可以在此基础上试一下，就试乙烷结构树就行，CH3-CH3，就用你的方法
，给出
: 答案我看看行不行。你的方法我没太看懂，所以你自己给出答案。
【在 T*******x 的大作中提到】
: 要不你试一个？你那篇给出的单链的例子就不对：91753，这不行。当然，单链是容易
: 的，你可以在此基础上试一下，就试乙烷结构树就行，CH3-CH3，就用你的方法，给出
: 答案我看看行不行。你的方法我没太看懂，所以你自己给出答案。
|
T*******x
发帖数: 8565 | 20 乙烷的分子式。
两个C相连，每个C上连了三个H。把C和H看做node，把连接看成edge，这就是一个树，
用你的方法在这个树上试试，给出答案，我看看对不对，也学学你的方法。
【在 b******r 的大作中提到】
: 啥是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 的大作中提到】
: 任意一棵树，图论中的树，呵呵，假设有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 的大作中提到】
: 乙烷的分子式。
: 两个C相连，每个C上连了三个H。把C和H看做node，把连接看成edge，这就是一个树，
: 用你的方法在这个树上试试，给出答案，我看看对不对，也学学你的方法。
|
T*******x
发帖数: 8565 | 24 结果是对的。但是算法描述上，好像还不清楚。比如第一步，从7153开始，在5上插一
点，插的是什么数？是3吗？所以原有大于等于3的数都加2。为什么要插3？怎么描述这
个算法？
【在 b******r 的大作中提到】
: 先写最长的一串：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 的大作中提到】
: 先证明：
: 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 的大作中提到】
: 这个算个开头吧。后面你想清楚没有？
:
: 围内
|
c****8
发帖数: 1 | 27 你就是干苦力的命，认了吧，琢磨数学没用
盹盹盹
：任意一棵树，图论中的树，呵呵，假设有n个node，n-1个edge。证明：可以在每个
node和每个edge上放一个1到2n-1之间的数，node上放奇数，edge上放偶数，不重复，
使任
：意一个edge上的数等于相连的两
：个node上的数之差。
：☆ 发自 iPhone 买买提 1.24.09
【在 T*******x 的大作中提到】
: 这个算个开头吧。后面你想清楚没有？
:
: 围内
|
T*******x
发帖数: 8565 | 28 嗯。有意义。
咱们再想两天。星期五晚上，我给答案。
【在 b******r 的大作中提到】
: 每个节点的数值定义为该点的高度。
: 把这个树排成上下震荡的，并且从左到右振幅越来越小。
: 加入一个新的节点的时候保持该节点右侧振幅不变，左侧振幅加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 的大作中提到】
: 搞那么复杂干嘛？中间一个1，然后3，5，..., 2n-1全部只连到1不就完了？也就是说
: 是个星型。
: 树的定义是没有cycle就行了，星型也是树。
|
|
|
T*******x
发帖数: 8565 | 31 你不是在写证明吧？我怕漏了你，确认一下。
【在 z***t 的大作中提到】
: 没说二叉树
: 可以是 n-1叉
: 1 -2- 3
: -4- 5
: -6- 7
: ……
: -2n-2-- 2n - 1
: 对不对 都不用证明
|
T*******x
发帖数: 8565 | 32 把你给漏了。你哪冒出来的？呵呵。
【在 c****8 的大作中提到】
: 你就是干苦力的命，认了吧，琢磨数学没用
: 盹盹盹
:
: ：任意一棵树，图论中的树，呵呵，假设有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 的大作中提到】
: 每个节点的数值定义为该点的高度。
: 把这个树排成上下震荡的，并且从左到右振幅越来越小。
: 加入一个新的节点的时候保持该节点右侧振幅不变，左侧振幅加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 的大作中提到】
: 你这个算法，可能还是没描述清楚，或者是没有完全走通。
: 咱们来看看丙烷结构树：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 的大作中提到】
: 从头开始一个个加节点来构造结果，保持一下属性：和最大节点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 的大作中提到】
: 你不要想要插入几。只管把该加的节点加上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 的大作中提到】
: 任意一棵树，图论中的树，呵呵，假设有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 的大作中提到】
: This problem has remained unsolved since 1967. It’s still open.
: https://youtu.be/v5KWzOOhZrw
: 哈哈。
:
: node
|
|
|
T*******x
发帖数: 8565 | 41 嗯。也不错了。我觉得好问题就是这样，它让你一个species一个species研究，内容博
大精深。
【在 b******r 的大作中提到】
: 呃，中计了，我对图论一无所知。
: 仔细想了下我的办法只对caterpillar tree 有效。。
:
:
: This problem has remained unsolved since 1967. It’s still open.
:
: https://youtu.be/v5KWzOOhZrw
:
: 哈哈。
:
: node
:
|
