找出最小競賽圖中所有的3迴圈

Finding All 3-cycles of Tournaments With Minimum Score Sequence

鄧偉華(Wei-Hwa Teng)

指導教授 ： 王有禮

國立暨南國際大學/科技學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6837/NCNU.2007.00035

摘要

在圖論(graph)的領域中，競賽圖(tournament)是一個相當有趣的研究。Brualdi and Li有一篇論文是探討相同分數序列競賽圖的特性，並推導出了競賽圖的最小分數序列(minimum score sequence)，及其中3迴圈(3-cycles)的個數為n – 2個。
本篇論文探討最小競賽圖(minimum tournament)與生成樹(spanning trees)間的關係。我們提出一個找尋最小競賽圖中所有的3迴圈的演算法，並且證明其所需要的時間複雜度為O(m + n)，其中n是點的個數，m是所有點的外分支度(out-degree)的總和。
在圖論(graph)的領域中，競賽圖(tournament)是一個相當有趣的研究。Brualdi and Li有一篇論文是探討相同分數序列競賽圖的特性，並推導出了競賽圖的最小分數序列(minimum score sequence)，及其中3迴圈(3-cycles)的個數為n – 2個。
本篇論文探討最小競賽圖(minimum tournament)與生成樹(spanning trees)間的關係。我們提出一個找尋最小競賽圖中所有的3迴圈的演算法，並且證明其所需要的時間複雜度為O(m + n)，其中n是點的個數，m是所有點的外分支度(out-degree)的總和。

關鍵字

競賽圖 ； 最小分數序列 ； 3迴圈 ； 生成樹

並列摘要

Tournaments have many interesting research topic in the field of graph theory. Brualdi and Li have proved that the number of 3-cycles of minimum tournaments formed by the minimum score sequence is n – 3。
In this thesis, we discuss the relation between a minimum tournament and its spanning tree. We propose an algorithm for finding all 3-cycles of minimum tournaments and prove that its time complexity is O(m + n), where n is the number of nodes and m is the total
number of out-degrees in the tournaments.

並列關鍵字

tournaments ； minimum score sequence ； 3-cycles ； spanning trees

參考文獻

參考文獻

[1] R. A. Brualdi and Q. Li, The interchange graph of tournaments with the same score vector, J.A. Bondy and U.S.R. Murty, Eds, Progress in Graph Theory. (Academic Press, Toronto, 1984)128-151.

[2] R. A. Brualdi, Upset in Round Robin Tournaments, Journal of combinatorial theory, Series B 35, 62-77(1983).

[3] R. A. Brualdi and J. Shen, Landau’s Inequalities for Tournament Scores and a Short Proof of a Theorem on Transitive Sub-Tournaments, Journal of graph theory, volume 38, Issue 4 (p 244-254).

[4] R. Balasubramanian, Venkatesh Raman and G. Srinivasaragavan, Finding Scores in Tournaments, Journal of algorithms 24, 380-394(1997).