【離散數學】六個經典問題

Matching：配對

配對問題通常由兩組具有關係的頂點組成，也就是說，所有第一組的頂點都只與第二組的頂點形成配對，而同一組內沒有任何的配對 (我們稱這樣的圖形為 bipartite graph)。而在配對問題中，我們的目標是：找到一個將兩組頂點一對一配對的方法，或證明這不可能。

Spelling checker：電腦查字典

當用電子辭典中查字典時，電腦會去比對你輸入的字是字典中的哪一個字，但電腦不會一一比對，而是用一種更快速的比對法。電腦中的字換算成編碼後，是有大小順序之分的，因此我們可以把要查的字先跟最中間編碼的字比較大小，知道該字在哪一邊後，可以再重複一次相同的動作，依此類推。

而這種查字典的方法事實上可以一個 Graph 表示，以頂點表示用來比較的字，而以directed edge 連接下一步要比對的字，我們稱這樣的 Graph 為 tree。我們發現在這樣的圖形中，任兩個頂點之間只有唯一一個 path 。

Network reliability：系統可靠性

在這種問題中，我們討論一個相連的系統的可靠性，例如移除某些頂點與連線是否會使剩餘的系統不相連，或是要維持系統相連的最小連線數量，事實上，最小連線數量的系統會是一個 tree，且若是有 n 個頂點，則此最小數量為 n-1。

Def：Degree

我們將一個頂點所接 (incident) 的連線數量稱為該頂點的 degree。

Street Surveillance：街道看守

若圖形中的點代表崗哨，線代表街道，每個崗哨可以看到每個與他相接的那段街道(隔一個崗哨就看不到了。)，要如何以最少的人力站哨以看守所有的街道？

也可以改成看守崗哨。

Def：Edge cover

若一個由 vertices 組成的集合 C 為 edge cover，則此 graph 中每一個 edge 皆可在 C 中找到與之相接 (incident) 的元素。

Scheduling meeting：行程安排

立法委員有許多委員會要開，然而各個委員會有一些重複的人，該如何安排開會時間，使得每個人都有開到該開的會，且開會時間最少。

我們用點表示委員會，將有共同成員的委員會用線相連，如此一來沒有線相連的點就可一起開會，問題就變成找出最少數量的這樣的組合。

Def：independent set (獨立集)

若一個由 vertices 組成之集合，其中任兩點間都沒有 edge 相連，則我們稱這個集合為 independent set of vertices。

上面的問題就變成：在讓所有會都被開完的情況下，找到最少的 independent sets。

Prop

G = (V , E)，若 I 為一個獨立集，若且惟若 V \ I 為一個 edge cover 。

cor：

I 為一個 graph 中元素最多的獨立集，若且惟若 V \ I 為元素最少的 edge cover。

Influence model：影響力

在這個模型中，用點代表人，使用 directed edge 指向所能影響的其他人，我們的問題是：如何找到最少的人，使最後所有人都直接或間接受到這些人的影響。

Def：directed path

一個 directed path 是一個由頂點組成的序列，而在序列中相鄰的任兩個頂點皆有同方向的 directed edge 。(或是由同方向而相連的 directed edge 組成)

Def：vertex basis

vertex basis 為可以用 directed path 指到所有頂點的最小(缺一不可)頂點集合。

directed path graph
我們可以根據原本的圖畫出另一個圖，頂點與原本一樣，而原本用 directed edge 連接可直接影響的人，現在我們用 directed edge 連接可直接或間接影響的人，也就是可以被原本的 directed path 指到的人，而新的圖就稱為 directed path graph。

這麼一來在新的圖中，問題就變成如何找到最少的人來與所有的人連線，也就是vertices cover。值得注意的是，原本的圖中的 vertices cover 也可以影響所有人，只是數量較多。

Note：vertex basis 的必要條件

若一個頂點沒有指向他的連線，那麼這個頂點必定包含於 vertex basis 中。