資工筆記

搜尋此網誌

Graphic Theory: Chapter 10

1月 06, 2019

取得連結
Facebook
X
Pinterest
以電子郵件傳送
其他應用程式

A的定義

Flow的定義

取得連結
Facebook
X
Pinterest
以電子郵件傳送
其他應用程式

留言

張貼留言

Graphic Theory: Chapter 8

Spanning tree: Tree T是graph G的spanning tree，如果T是G的subgraph且包含G的所有vertices的話 G為connected iff G擁有spanning tree。Spanning tree的數量不一定是1，但是如果G是tree的話，spanning tree的數量為1。 Cycle Cn的spanning tree數量為n。 Kirchhoff's matrix-tree theorem可以用來判斷，一個graph能夠建立出多少個spanning tree。請練習! BFS和DFS可以用來建立spanning tree，只要在每次搜尋中連線還沒被連線過的點即可 (填寫adjacency list時，一次填一個row，左邊是連出的項(head)，右邊是被連的項(tail)) Minimum spanning tree Prim's algorithm: 用來產生minimum spanning tree。但他好像不能找到所有spanning tree裡面最小的weight者阿，還是說他只能找到目前這個root的weight最小者？ Kruskal's algorithm: 每次選擇weight最小的邊且不會造成兩個重複的點加入。

Operating System: Chapter 10 TB

Multiple Choice 1. A source file is a sequence of functions, each of which is further organized as declarations followed by executable statements. What does the "as" mean here? And an executable file is a series of code sections that the loader can bring into memory and execute. 2. An object file is a sequence of bytes organized into blocks understandable by the system's linker. 3. The OS uses two internal tables to keep track of open files. System-wide and pre-process open table. 6. A shared lock behaves like a reader lock. An exclusive lock behaves like a writer lock; only one process at a time can acquire such a lock. For a shared lock, several processes can acquire the lock concurrently. So the locks are like some sort of interface to the processes? 8. Information in a sequential access file is processed in order, one record after the other. 9. The UNIX system uses a crude magic number to indicate roughly the type of the file. 11. Tree-structured di...

Graphic Theory (1)

A graph is a triple(V, E, g), where (i) V is a finite none empty set, called the set of vertices; (ii)E is a finite set(may be empty), called the set of edges; and (iii)For none empty set E, g is a function, called an incidence function, that assigns to each edge, , a one-element subset {v} or a two-element subset {v,w}, where v and w are vertices. 在text中將連結v,w兩點的edge表示為g(e) = {v,w} 的endpoint v 和 e incident(相連)，相連的兩點v和w為adjacent(相鄰)。兩個共享同一vertex的edge也稱作adjacent，如果g(e) = {v}，則e is a loop on the vertex v or at the vertex v. The incidence function 可用incidence table 來表達： edge | e1 | e2 | e3 | e4 | e5 | end vertices | v1,v2 | v1,v2 | v4,v3 | v3, v4 | v4,v1 | Let v be a vertex of a graph G. Then Ng(v)稱作all neighbors of v, 也可以簡寫為N(v)。使得那麼Ng[v] (或N[v])稱作 the set of closed neighbors of v. (它包含v自己) G is cal...

技術提供：Blogger

主題圖片來源：Storman