Adjacency matrix: 用矩陣來表達兩點之間的arcs數量
橫軸代表連出者 縱軸代表被連者
矩陣的次方: 矩陣的n次方矩陣代表從某點到某點之間length為n的walk數量，這還滿神奇的!
B是A從0次方到n-1次方相加起來的矩陣，如果B除了對角線之外沒有0那麼G則是connected graph
Incidence matrices: 表示點和線之間的關聯，縱軸為頂點，橫軸為邊。
incidence matrix如果用來表示digraph，則-1代表該點為該邊的tail，1為head，2則為loop。
Isomorphism: 兩張圖可用兩個方程式來對應，一個對應點，一個對應邊。如果所有點邊都可以找到對應者，則這兩張圖為相同的，G1 is isomorphic to G2。
如果兩graph互為isomorphic，那麼G1擁有degree為k的點，G2也一定會擁有degree為k的點。
如果G1擁有長度為k的cycle，那麼G2也一定會擁有長度為k的cycle
G1和G2也能畫出一樣的adjacency matrix(在特定頂點順序下)。
self-complementary: 如果G是simple graph，那麼g和g-bar為isomorphic的，即稱為self-complementary。
Eigenvalue和eigenvector:
A為一個n x n矩陣，λ為A的eigenvalue iff det(λI - A) = 0。
I為identity matrix。
The characteristic matrix of A = A - xI。
The characteristic equation of A = det(A - xI)。
The characteristic equation of A = det(A - xI) = 0。
Graph G的eigenvalue即為其adjacency matrix的eigen value。
Theorem: |λ| <= ∆(G)
對k-regular graph來說，因為k-regular graph的∆(G)一定為k，因此|λ| <= k for all eigenvalues。
Eigenvalues可以不只一個。
Ramanujan graphs?
橫軸代表連出者 縱軸代表被連者
矩陣的次方: 矩陣的n次方矩陣代表從某點到某點之間length為n的walk數量，這還滿神奇的!
Incidence matrices: 表示點和線之間的關聯，縱軸為頂點，橫軸為邊。
incidence matrix如果用來表示digraph，則-1代表該點為該邊的tail，1為head，2則為loop。
Isomorphism: 兩張圖可用兩個方程式來對應，一個對應點，一個對應邊。如果所有點邊都可以找到對應者，則這兩張圖為相同的，G1 is isomorphic to G2。
如果兩graph互為isomorphic，那麼G1擁有degree為k的點，G2也一定會擁有degree為k的點。
如果G1擁有長度為k的cycle，那麼G2也一定會擁有長度為k的cycle
G1和G2也能畫出一樣的adjacency matrix(在特定頂點順序下)。
self-complementary: 如果G是simple graph，那麼g和g-bar為isomorphic的，即稱為self-complementary。
Eigenvalue和eigenvector:
A為一個n x n矩陣，λ為A的eigenvalue iff det(λI - A) = 0。
I為identity matrix。
The characteristic matrix of A = A - xI。
The characteristic equation of A = det(A - xI)。
The characteristic equation of A = det(A - xI) = 0。
Graph G的eigenvalue即為其adjacency matrix的eigen value。
Theorem: |λ| <= ∆(G)
對k-regular graph來說，因為k-regular graph的∆(G)一定為k，因此|λ| <= k for all eigenvalues。
Eigenvalues可以不只一個。
Ramanujan graphs?
留言
張貼留言