Show how to label a path of N vertices with the integers 1,2,.......,N such that
the absolute values of the difference of the labels of adjacent vertices are all different.
You can construct it inductively.
請問一下題目意思，以及該如何解答?
謝謝
Research Space for Linear Algebra & Discrete Mathematics
2 則留言:
題目的意思是要你對一條長的為 n 的 path編號1,2,...,n, 使得path中的任兩個相鄰點之間編號的絕對值差值皆相異
我的編號方法是
(1) 若n=2, 就左邊的點標1, 右邊的標2 (1,2)
(2) 若n=3, 就在原本的左右兩個點之間放3 (1,3,2)
(3) 考慮當有 n (n>2) 個點時的情形: 我們在之前編號的方式都是1放在path的最左邊, 那麼重新編號的方法就是先在 1 和 1 的右邊的node中間放一個新的點, 編號為 n (所以此時path最左邊的兩個點差值就是n-1), 然後再對 n 右邊的那 n-2 個點全部重新編號, 假設這新的path中的右邊那 n-1 個點所形成的subgraph就是原來那n-1個點的舊的path, 令每個其中的點對應在舊path上的label為x, 我們想對他編的新label為y, 那麼規則就是取 y=n+1-x, 如此一來我們就可以對這 n-2 個點編 2,3,...,n-1, 且可保證編號方式會唯一, 因為任取第 i 和第 i+1 的任兩個相鄰的點, i=3,...,n-1, 假設在舊的編號中 x(i)-x(i+1)=d, 那麼在新的path裡, 因為 y(i)=n+1-x(i), y(i+1)=n+1-x(i+1), 則 y(i)-y(i+1)=n+1-x(i)-(n+1-x(i+1))=x(i+1)-x(i)=-d, 因為原先編號中的每個d都相異, 新的-d自然也就都相異
例如:
(1,2) d--1;
(1,3,2) d=-2,1; since (1,3=4-1,2=4-2)
(1,4,2,3) d=-3,2,-1; (1,4=5-1,2=5-3,3=5-2)
(1,5,2,4,3) d=-4,3,-2,1; (1,5,2=6-4,4=6-2,3=6-3)
(1,6,2,5,3,4) d=-5,4,-3,2,-1 ...
謝謝，辛苦了~~打好長
張貼留言