大雨在下我畫圖, 程式設計攏看無, 設計資源有包庇

點、縣、面所構成的世界

點、縣、面所構成的世界

Graph 圖

Graph 中文翻做「圖」。此處談及的「圖」並不是指圖片或者圖形。「圖」是一種用來記錄關聯、關係的東西。

一張圖由數個點( vertex )以及數條邊( edge )所構成。點與點之間,得以邊相連接,表示這兩點有關聯、關係。

點的大小形狀和線的粗細長短是無所謂的,我們只在乎它們如何連接。只要連接的關係對了,要怎麼畫都行,簡約、雅觀、平易近人即可!

兩點之間也可以有很多條邊,甚至有自己連到自己的邊。兩點之間有很多條邊,代表這兩點有很多項關聯。一個點有自己連到自己的邊,表示自己和自己有項關聯。

Isomorphism / Isomorphic 同構

Isomorphism 中文譯作「同構」, Isomorphic 中文譯作「同構的」。如果兩張圖的連接方式一模一樣時,則稱作「同構」。

圖上的邊可以是直的,也可以是彎彎曲曲的,也可以是交錯的。不論邊的形狀如何,都不會改變點與點之間的關聯、關係,終究都會是同構的圖。

圖上的點可以任意移動位置。不論點的位置如何,都不會改變點與點之間的關聯、關係,終究都會是同構的圖。

同構的圖擁有相同的資訊,所以不管選擇哪一張圖都是可以的,只要清楚易懂就可以了!


把一張圖上的點依序標示編號,然後建立一個方陣,來記錄連接資訊。方陣中的每一個元素都代表著某兩點的連接資訊。例如元素 (0,1) 記錄著第 0 點到第 1 點的連接資訊、元素 (4, 2) 記錄著第 4 點到第 2 點的連接資訊。如此一來,任意兩個點之間的資訊,都有對應的地方可用於記錄,纖悉無遺。

連接資訊可以是邊的數目,也可以是邊的權重,也可以儲存其他的資訊。

值得一提的是, adjacency matrix 可以用來記錄邊的權重。但是它卻沒辦法記錄點的權重,它也沒辦法同時記錄點和邊的權重。不過,要記錄點的權重,其實只要另外開一條陣列就行了,也不是什麼難事。

另外,當兩點之間的邊超過一條的時候, adjacency matrix 沒辦法記錄權重,因為 adjacency matrix 的一個格子只能存入一個數字,沒辦法同時間存入多個數字。我們可以修改 adjacency matrix 的構造以存入更多數字,只是這不在討論範圍之內,各位可自行研究。程式碼可以寫成這樣:

int graph[5][5];
void adjacency_matrix()
{
    for (int i=0; i<5; ++i)
        for (int j=0; j<5; ++j)
            graph[i][j] = 0;
 
    int a, b, c;    // 一條邊的端點、另一個端點、邊的權重
    while (cin >> a >> b >> c)
        graph[a][b] = c;
}

以上簡單介紹在電腦裡,其實延續我們現實世界三維概念講起,之前一點筆記,
3D看似複雜,但其實抽絲剝繭就是紀錄點和點之間的關係,而更構成了線;三條線構成了面;許多面賦予屬性(人皮、布料、磚瓦)就顯示成了我們現實熟悉的事物。當然這是超沒責任濃縮精華到不行的解釋。

其中若進一部還有很多可以進去玩,若介面可愛一點別太專業,當國中小的科學教材也不為過,在裏頭模擬地心引力、風場、流體力學、光學,開源免費的Blender全套解決。以上經過點線面部段衍伸,構成不同曲面、再賦予屬性,最後就成了…

老實說…我也不知道我到底是寫三小。

IBM Research        http://www.research.ibm.com/
Intel Research      https://www.intel.com/research/
AT&T Labs Research  https://about.att.com/sites/labs_research
Microsoft Research  https://www.microsoft.com/research/
Google Research     https://research.google.com/
Google Developer    https://developers.google.com/products/
Facebook Research   https://research.fb.com/
Mozilla Research    https://research.mozilla.org/
Disney Research     https://www.disneyresearch.com/
Pixar Research      http://graphics.pixar.com/research/
Autodesk Research   https://www.autodeskresearch.com/
Adobe Research      https://research.adobe.com/
NVIDIA Research     https://www.nvidia.com/en-us/research/
NVIDIA Developer    https://developer.nvidia.com/