Research Space for Linear Algebra & Discrete Mathematics
G=(V,E),planar <=>G不具subgraph與K5 orK3,3同胚?
1. nonlinear recurrenc relation不是指非常係數, 題目有提到constant coeffcient, 就是常係數, nonlinar是指它不是用linear combination作出來的recurrence relation, 例如an = (an-1)(an-2)就是nonlinear, 上課提的Catalan number的recurrence relation也是nonlinear, 不過它不是order three就是了, 至於可不可解, 上課有提醒過, 有非常多的recurrence relation都是不可解的, 所以才會有很多approximation的方法2. (a)顯然是錯的, 上課舉的不同構的例子好像全都是這種, 點數相同, 邊數相同, degree sequence相同(b)vertex connectivity = 3表示至少要去掉3個點才會造成disconnected, 因此就不會有articulation point, 沒有articulation point就是biconnected(e)如小白所說, 很有名的Kuratowski theorem就是planar graph的充要條件
謝謝同學和老師的解答可否再請問1.上面第一題他是二階遞迴但又只給一個初始該如何解呢?
所以是否有解不是初始條件的問題, 這裡的有解指的是general form或general closed form, 初始條件是讓解為唯一解, 任何的遞迴如果初始條件夠, 你丟給程式跑, 最後要求那一項都會求得出來
大概懂題目要問什麼了那我算出來的general solution是a_n = (c0+c1n)2^n而c0 c1可隨意代而我代c0=1 c1=0得a_n=2^n所以答true囉?
張貼留言
6 則留言:
G=(V,E),planar <=>
G不具subgraph與K5 orK3,3同胚?
1. nonlinear recurrenc relation不是指非常係數, 題目有提到constant coeffcient, 就是常係數, nonlinar是指它不是用linear combination作出來的recurrence relation,
例如an = (an-1)(an-2)就是nonlinear, 上課提的Catalan number的recurrence relation也是nonlinear, 不過它不是order three就是了, 至於可不可解, 上課有提醒過, 有非常多的recurrence relation都是不可解的, 所以才會有很多approximation的方法
2. (a)顯然是錯的, 上課舉的不同構的例子好像全都是這種, 點數相同, 邊數相同, degree sequence相同
(b)vertex connectivity = 3表示至少要去掉3個點才會造成disconnected, 因此就不會有articulation point, 沒有articulation point就是biconnected
(e)如小白所說, 很有名的Kuratowski theorem就是planar graph的充要條件
謝謝同學和老師的解答
可否再請問
1.上面第一題
他是二階遞迴但又只給一個初始該如何解呢?
所以是否有解不是初始條件的問題, 這裡的有解指的是general form或general closed form, 初始條件是讓解為唯一解, 任何的遞迴如果初始條件夠, 你丟給程式跑, 最後要求那一項都會求得出來
大概懂題目要問什麼了
那我算出來的general solution是
a_n = (c0+c1n)2^n
而c0 c1可隨意代
而我代c0=1 c1=0
得a_n=2^n
所以答true囉?
張貼留言