1 |
Maximum Gap of Mixed Hypergraph郭威廷, Kuo, Wei-Ting Unknown Date (has links)
A mixed hypergraph is a triple H = (X; C;D), where X is the vertex set, and each of C;D is a list of subsets of X. A strict t-coloring is a onto mapping from X to {1, 2,…,t} such that each c belongs to C contains two vertices have a common value and each d belongs to D has two vertices have distinct values. If H has a strict t-coloring, then t belongs to S(H), such S(H) is called the feasible set of H, and k is a gap if there are a value larger than k and a value less than k in the feasible set but k is not.
We find the minimum and maximum gap of a mixed hypergraph with more than 5 vertices. Then we consider two special cases of the gap of mixed hypergraphs. First, if the mixed hypergraphs is spanned by a complete bipartite graph, then the gap is decided by the size of bipartition. Second, the (l,m)-uniform mixed hypergraphs has gaps if l > m/2 >2, and we prove that the minimum number of vertices of a (l,m)-uniform mixed hypergraph which has gaps is (m/2)( l -1) + m.
|
2 |
Gap in (l,m)-uniform mixed hypergraph楊瑞章 Unknown Date (has links)
(l,m)-uniform混和超級圖的色譜一定是是連續的, 利用一個技巧讓所有l大於二的(l,m)-uniform混和超級圖都存在一組C-edges 和 D-edges, 使得光譜不連續.最後提供一個演算法, 讓所有l和m 都大於二的(l,m)-uniform混和超級圖, 也存在一組 C-edges 和 D-edges, 使得光譜不連續. 這樣我們就已經討論完所有(l,m)-uniform混和超級圖( l , m 都要大於等於 2), 其光譜是否存在著有不連續的可能. / In this thesis, we study all existences of gap in every kind of (l,m)-uniform mixed hypergraph, where n > 1 and m > 1. We have to divide the topic into three parts: (2,m)-uniform mixed hypergraph where m > 1, (l,2)-uniform mixed hypergraph
where l > 2, and (l,m)-uniform mixed hypergraph where l > 2 and m > 2.
|
3 |
均勻混合超級圖的唯一著色 / The Unique colorability of a Uniform Mixed Hypergraph游喬任 Unknown Date (has links)
在本篇論文,我們去找一個唯一著色的均勻混合超級圖的點數及邊數的下界。
我們證明為一著色的均勻混合超級圖的點數必須超過(l-1)(m-1)+1而且我們提出一個方法來建構為一著色的均勻混合超級圖。如果一個混合超圖是個D為空集合的r-均勻超級圖,當r=2則它是唯一著色的。否則,D為空集合的均勻超級圖不會是唯一著色的。我們介紹兩種有系統的方法建構唯一著色的均勻混合超級圖並且達到我們的邊界。首先,我們是著保持均勻混合超級圖的唯一著色下去減少D邊的個數。然後我們減少D邊的個數。我們考慮r均勻的C超圖和D超圖並找他們邊的個數的範圍。 / In this thesis, we find the lower bounds of number of vertices and edges of
uniform mixed hypergraph which is uniquely colorable. We show that the size of vertex set of uniform mixed hypergraphs with unique coloring is more than (l-1)(m-1)+1 and we come up a way to construct uniquely colorable uniform mixed hypergraphs. If a mixed hypergraph is an r-uniform hypergraph with D empty, then it is uniquely colorable when r=2. Otherwise, an r-uniform hypergraph with D empty is not uniquely colorable. We will introduce two systematic ways to construct a uniform mixed hypergraph which is uniquely colorable and achieves our bounds. First,we reduce the number of C-edges such that uniform mixed hypergraphs keep being uniquely colorable. Then we reduce the number of D-edges. We consider r-uniform C-hypergraphs and D-hypergraphs and find the bounds on their number of edges.
|
4 |
完全C邊混合超圖的著色多項式 / The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edges吳仕傑 Unknown Date (has links)
在這篇論文中,我們利用分離-收縮法(splitting-contraction algorithm)獲得一個擁有完全C邊以及循環D邊特性的圖之著色多項式。 假如一個混合超圖在點集合上有主要的循環, 使得所有的C邊和D邊包含一個主循環(host cycle)的連接子圖, 則稱此圖為循環的(circular)。 對於每個l≧2, 所有連續l個點會形成一個D邊時, 我們把D記作D_l。 如此一來, 超圖(X,Φ,D_2)就是圖論中n個點的普通循環。
我們先觀察擁有完全C邊和循環D邊的超圖, 利用分離-收縮法的第一步, 找到遞迴關係式並且解它。 然後我們就推廣到一般完全C邊及循環D邊的超圖。 / In this thesis, we obtain the chromatic polynomial of a mixed hypergraph with complete C-edges and circular D-edges by using splitting-contraction algorithm. A mixed hypergraph H=(X,C,D) is called circular if there exists a host cycle on the vertex set X such that every C-edge and every D-edge induces a connected subgraph of the host cycle. For each l≧2, we denote D by D_l if and only if every l consecutive vertices of X form a D-edge. Thus the mixed hypergraph (X,Φ,D_2) is a simple classical cycle on n vertices.
We observe first a mixed hypergraph with complete C-edges and D_2. By the first step of the splitting-contraction algorithm, we can find out the recurrence relation and solve it. Then we generalize the mixed hypergraph with complete C-edges and circular D-edges.
|
Page generated in 0.0429 seconds