有向圖與阿貝爾群的性質測試

性質測試 (property testing)是一個在資訊學科中被廣泛研究的課題，其應用範圍涵蓋了網路拓樸與程式除錯等多個領域。Bender 與Ron 發展了一個性質測試的演算法，用來測試某些有向圖是否滿足強連通的性質，本論文將這個演算法稱之為BR 演算法。BR 演算法在應用上有諸多限制，只適用於滿足特定條件的某些有向圖。本論文發展了一個不受限制的演算法，可以測試任何一個有向圖是否具有強連通的性質。對於一個事先設定的有向圖H，Alon 與Shapira 證明了對於任一個有向圖G，如果我們需要大量移除G 的有向邊，才可以完全消除G 裡面與H 共構(isomorphic) 的子圖(subgraph)，則在有向圖G 中的H 共構子圖的數目有一個下界。對於一個有向子圖，如果其圖形的任一部分都不與H 形成共構，我們便稱之為無H 子圖。本論文利用Alon 與Shapira 的研究結果，發展了一個演算法，用以測試任一個有向圖是否存在一個由k 個點所組成的無H 子圖。相對於在應用上受到限制的BR 演算法，本論文所發展用來測試強連通性質的演算法，在應用上沒有限制但是效率會比較慢。因此對於滿足BR 演算法應用限制的少數有向圖，我們還是傾向用BR 演算法來測試其是否有強連通的性質；至於其他不滿足限制的有向圖，我們便使用本論文發展的演算法。當我們需要在兩者之間做選擇的時候，前述測試無H 子圖的演算法可以幫助我們選擇合適的強連通測試演算法。一個群的生成元可以用來生成整個群，而對於一個阿貝爾群而言，其生成元的數目是一個受到學界關注的研究題目。本論文利用前述的強連通測試演算法，發展了一個很有效率的演算法，可以測試任一個集合與一個二元運算的組合是否為一個生成元數目小於k 的阿貝爾群。

關鍵字

性質測試；隨機演算法；有向圖；強連通；阿貝爾群；生成元

並列摘要

Bender and Ron construct a restricted tester on the strong connectivity of digraphs (we call it the BR tester). We generalize the BR tester to test the strong connectivity of digraphs. For any digraph H and a digraph G being far from any H-free digraph, Alon and Shapira prove a lower bound of the number of H in G. After solving the problem of testing the strong connectivity of digraphs, we use Alon and Shapira's result to construct a randomized algorithm for testing digraphs with an H-free k-induced subgraph. Our strong connectivity tester has no restriction but must query about the input more times than the restricted BR tester. Suppose an input digraph satisfies the restrictions of the BR tester, using the BR tester to test the strong connectivity of this input digraph is more e±cient than using our strong connectivity tester. If we want to test the strong connectivity of a digraph, our randomized algorithm for testing digraphs with an H-free k-induced subgraph can help us determine which tester should be used to test the strong connectivity of the digraph: the BR tester or our strong connectivity tester. A generator set for a finite group is a subset of the group elements such that repeated multiplications of the generators alone can produce all the group elements. The number of generators of an abelian group is an important issue in many studies. In most cases, it is not easy to identify whether a group-like structure is an abelian group with k generators for a constant k. We construct an efficient randomized algorithm that, given a finite set with a binary operation, tests if it is an abelian group with a k-generator set. If k is not too large, the query complexity of our algorithm is polylogarithmic in the size of the groundset. Otherwise the query complexity is at most the square root of the size of the groundset.

並列關鍵字

Property testing ； Strong connectivity ； H-free subgraph ； Abelian ； Generator

參考文獻

[1] A. Abdollahi, A. Faghihi and A. M. Hassanabadi, 3-generator groups whose

elements commute with their endomorphic images are abelian, Communications

[2] A. Abdollahi, A. Faghihi and A. M. Hassanabadi, Minimal Number of Gener-

with Their Endomorphic Images, Communications in Algebra, 36(5) (2008), pp.

[3] S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric inter-

國際替代計量

有向圖與阿貝爾群的性質測試

全文下載

主題瀏覽