區間數及其相關問題之研究

Abstract

一個集合族F的交集圖(intersection graph)是一個圖，它的點與F中的集合有一一對應的關係，兩不相同之點有邊相連的充份必要條件是它們所對應的集合相交。如果這個集合族為區間(interval)所成的集合，則所建構的圖稱為區間圖(interval graph)。區間數(interval number)及全區間數(total interval number)是區間圖的一般化概念，本論文旨在研究區間數、全區間數以及其相關問題。 在第一章中，我們介紹術語、區間圖的特質及什麼是區間圖的一般化--區間數及全區間數。在第二章中，我們研究區塊圖(block graph)的k次方的區間數；我們證明了區塊圖(block graph)的k次方的區間數的上界為k+1，我們同時也判斷出那些區塊圖的k次方為區間圖。在第三章中，我們研究完全r分圖(complete r-partite graph)的全區間數；我們得出一個上界，並決定出某些完全r分圖的全區間數。在第四章中，我們研究區塊圖的全區間數，並發展出一個計算區塊圖的全區間數的演算法。在第五章中，我們研究一個圖的k次方的封閉性，並針對四種圖提出簡易的方法來證明它們有k次方的封閉性。在第六章中，我們得到子星圖(substar graph)的所有避免子圖，並發展出一個判斷弦圖(chordal graph)是否為子星圖的演算法。

The intersection graph of a family ${\cal F}$ of sets is the graph whose vertices have a one-to-one correspondence to the sets in ${\cal F}$, and two distinct vertices are adjacent if and only if their corresponding sets intersect. An interval graph is an intersection graph of intervals on the real line. c In Chapter 1, we introduce basic terminology and facts about interval graphs and their generalizations--interval numbers and total interval numbers. In Chapter 2, we study interval numbers of powers of block graphs. In particular, we prove that the interval number of the $k$th power of a block graph is at most $k+1$. We then characterize block graphs whose $k$th powers are interval graphs. In Chapter 3, we study total interval numbers of complete $r$-partite graphs. We give bounds of the total interval numbers of complete $r$-partite graphs and determine exact values for some cases. In Chapter 4, we study the total interval numbers of block graphs. We design an algorithm for finding the total interval number of a block graph. In Chapter 5, we give simple proofs for families of graphs closed under taking powers. In Chapter 6, we find the complete set of forbidden subgraphs for substar graphs. We design an algorithm to recognize whether a chordal graph is a substar graph.