群試問題

Abstract

本論文主要是討論有關群試的問題，群試的想法是在西元1942年，第二次世界大戰時因驗血問題(檢驗新兵是否感染梅毒)而產生的。Li是首次以組合眼光看待此問題的學者，他將問題描述如下：給定n個待測物所成集合V，其中有d物為瑕疵品，其所成的集合為D；我們的目的是要透過數次試驗將此D集合找出來。每一次的試驗皆是以下列的方式進行：自V中取出一部份X並對其做測試，測試結果有二，“負”的結果代表取出的X中不包含任何D中元素（即X中沒有瑕疵品），“正”的結果代表取出的X中至少包含一個D中的元素。這樣的試驗方法即稱為“群試”。我們的目標是決定在最差的情形下能找出D所需的最小測試次數M[d,n]。 我們可以將上述問題一般化如下：給定待測物所成集合V，以及樣本空間$S \subseteq 2^V$，要經過數次試驗將某一$D \in S$找出來。每一次試驗是從V取一部份X而後對其做測試，並且依照所選出的X將S分為兩部份：$S_1=\{D \in S:D \cap X = \emptyset\}$及$S_2= \{D \in S: D \cap X \neq \emptyset \}$。我們的目標是在最差的情況下找出D所需的最少測驗次數M[S]。本論文討論下述三種不同的樣本空間S。 第一種情況是當G=(V,S)是一圖型的情況，我們亦用M[G]表示M[S]。 Damaschke 證明了對任意圖型G，恆有$\lceil\log_2e(G)\rceil \le M[G] \leq \lceil\log_2 e(G)\rceil +1$，其中e(G)為G的邊數。已知有無限多個完全圖的測試次數必須達到上界；而Chang 和 Hwang則猜測G若是二分圖，則M[G]會達下界。在本論文的第二章中，我們證明了當二分圖G的邊數滿足$e(G)\leq 2^5$，或是在$k\ge 6$，且$e(G)\leq 2^5$ or $2^{k-1}<e(G)\leq 2^{k-1}+2^{k-3}+2^{k-4}+2^{k-5}+2^{k-6}+2^{k-7}+ 27\cdot 2^{\frac{k-8}{2}}-1$時，此猜測為正確的。此外，並證明了對一般所有的圖型G，若是在$k \geq 15$，且$2^{k-1}< e(G) \leq 2^{k-1} + 2^{k-9}+ 2^{k-15} + 2^{\frac{k+1}{2}} + 2^{\frac{k-5}{2}} + 2^{\frac{k-7}{2}} + 2^{\frac{k-9}{2}}$時，則M[G]亦會等於其所可達的最小值 $\lceil \log_2 e(G) \rceil$ 。 第三章則討論了在超圖H=(V,S)上的群試問題，我們亦用M[H]表示M[S]。Triesch證明了對任一r維的超圖H，其找一特定邊e所需的最少測試次數 有一上界:$\log_2 e(H) +r-1$，其中e(H)表示H的邊數。在本章中，我們證明了對所有的超樹H，均有$ M[H] = \lceil \log_2 e(H) \rceil$。 第四章中所討論的是另一類的群試問題，稱為連續正性質問題。在一n個元素的集合$V_n$中，其元素按照某種比較方法排成自小至大的順序。而每一個$V_n$中的元素都附有一狀態：正或負。如果$V_n$上的正元素在前述順序為連續排列，且至多只有d個，則稱此集合有d-連續正性質。連續正性質問題便是要在這樣的一個集合$V_n$中，試圖用最少的測試次數找出那些正元素。Colbourn證明了在這樣一個有d-連續正性質的n元素有序集合中，至少需$O(\log_2 d + \log_2 n)$次才能找出那些正元素。但是他並沒有提到正確的所須最小測試次數$M[C_{d,n}]$是多少。在第四章中，我們將給定並證明當d=1,2,3時$M[C_{d,n}]$的確定值，並在$d \geq 4$時給予$M[C_{d,n}]$一上界$\lceil \log_2 (nd)\rceil+6$。

This thesis studies group testing problems. The idea of group testing originated from the blood testing in 1942 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\subseteq 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 {\it negative} outcome indicates that $X\cap D=\emptyset$, and a {\it positive} outcome indicates that $X\cap D\neq\emptyset$. The goal is to minimize the number $M[d,n]$ of tests under the worst scenario. We may generalize the problem as follows. Consider a population $V$ of $n$ items and a sample space $S \subseteq 2^V$. The problem is to identify an unknown $D \in S$ by a sequence of group tests. Each test is on a subset $X$ of $V$ which partitions $S$ into $S_1=\{D \in S:D \cap X = \emptyset\}$ and $S_2= \{D \in S: D \cap X \neq \emptyset \}$. The goal is to identify the unknown $D$ using a minimum number $M[S]$ of tests under the worst scenario. Chapter 2 considers the case when $G=(V,S)$ is a graph. We also use $M[G]$ for $M[S]$. Damaschke proved that $\lceil\log_2 e(G)\rceil \leq M[G] \leq \lceil\log_2 e(G)\rceil +1$ for any graph $G$, where $e(G)$ is the number of edges of $G$. Chapter 2 gives an improved bound for general graphs $G$. Namely, if $G$ with $2^{k-1}< e(G) \leq 2^{k-1} + 2^{k-9}+ 2^{k-15} + 2^{\frac{k+1}{2}} + 2^{\frac{k-5}{2}} + 2^{\frac{k-7}{2}} + 2^{\frac{k-9}{2}}$ and $k\geq 15$, then $M[G]= \lceil \log_2e(G) \rceil$. While there are infinitely many complete graphs $G$ with $M[G]=\lceil \log_2e(G) \rceil +1$, it was conjectured by Chang and Hwang that $M[G]=\lceil \log_2 e(G) \rceil$ for all bipartite graphs $G$. Chapter 2 also verifies the conjecture for bipartite graphs $G$ with $e(G)\leq 2^5$ or $2^{k-1}<e(G) \leq2^{k-1}+2^{k-3}+2^{k-4}+2^{k-5}+2^{k-6}+2^{k-7}+ 27\cdot 2^{\frac{k-8}{2}}-1$ for $k\ge 6$. Chapter 3 considers group testing on hypergraphs $H=(V,S)$. We also use $M[H]$ for $M[S]$. Triesch proved for any hypergraph $H=(V,E)$ of rank $r$, it is the case that $ M[H] \leq \log_2 e(H) +r-1,$ where $e(H)$ means the number of edges of $H$. This chapter proves that for any hypertree $H=(V,E)$, we have $ M[H] = \lceil \log_2 e(H) \rceil.$ Chapter 4 considers another kind of group testing called the consecutive positive problem. In a set $V_n$ of $n$ items, with linear order $\prec$, each item has an associated {\it state} positive or negative. The set $V_n$ has the {\it d-consecutive positive property} if the set of positive items is a consecutive set (under the order $\prec$), and contains at most $d$ items. Chapter 4 studies the problem of finding these consecutive positive items from $V_n$. Colbourn proved that this can be accomplished with $O(\log_2 d + \log_2 n)$ times for at most $d$ consecutive positives in a linearly ordered $n$-set of items. Colbourn didn't give the exact value of times needed. Chapter 4 gives the exact values for $d=1,2,3$, and gives an upper bound $\lceil \log_2 (nd)\rceil+6$ for $d \geq 4$.