圖上的群試

Abstract

群試的想法是在西元1943 年，第二次世界大戰時因驗血問題(檢驗新 兵是否感染梅毒) 而產生的。李周雄是首次以組合眼光看待此問題的學 者，他將問題描述如下：給定n 個待測物所成集合V，其中有d 物為瑕 疵品，其所成的集合為D; 我們的目的是要透過數次試驗將此D 集合找 出來。每一次的試驗皆是以下列的方式進行: 自V 中取出一部份X 並對 其做測試，測試結果有二，” 負” 的結果代表取出的X 中不包含任何D 中元素(即X 中沒有瑕疵品)，” 正” 的結果代表取出的X 中至少包含一 個D 中的元素。這樣的試驗方法即稱為” 群試”。我們的目標是決定在最 差的情形下能找出D 所需的最小測試次數M[d,n]。 本論文主要是討論有關群試的問題，需要兩個不同的待測物，相互作 用下才會產生瑕疵的情況。而樣本空間可表示成: 一個二分圖中的邊，邊 為相互作用的兩個待測物所形成，待測物就相當於圖中的點集合。這種 相關的研究最早是由張鎮華教授和黃光明教授所提出。他們的猜測：在 G 是二分圖且有2k 個邊的情況下，G 會存在一個導出子圖恰含有2k1 個邊。如果這個猜測是正確的，我們就可以用序列式演算法，在最少的 次數找出有瑕疵的複合物。這個猜測目前仍然還是一個尚未確定的問題， 它也激發了我在圖上作群試的研究。

The idea of group testing originated from the blood testing in 1943 by Dorfman. Li was the first who studied the combinatorial group testing as follows. Consider a population V of n items consisting of an unknown subset D Ď V of d defectives. The problem is to identify the set D by a sequence of group tests. Each test is on a subset X of V with two possible outcomes: a negative outcome indicates that X X D = H, a positive outcome indicates that X X D H. The goal is to minimize the number M[d; n] of tests under the worst scenario. This thesis mainly studies group testing on bipartite graphs. That is, the set of items are separated into two disjoint subsets and a defective complex comes from these two sets one from each. By associating each item with a vertex, the sample space can be represented by a bipartite graph where each edge represents a sample point of the space S(2; n). In order to show this problem, Chang and Hwang conjectured that a bipartite graph with 2k(k ą 0) edges always has a subgraph, induced by a subset of vertices, with exactly 2k1 edges. If this conjecture is true then a binary splitting algorithm can be applied to determine the defective complexes with minimum number of tests in sequential algorithm. While the conjecture remains open, it has stimulated my forthcoming reserach casting group testing on graphs.