| dc.contributor.advisor | 張宜武 | zh_TW |
| dc.contributor.advisor | Chang, Yi-Wu | en_US |
| dc.contributor.author (Authors) | 曾煥絢 | zh_TW |
| dc.contributor.author (Authors) | Tseng, Huan-Hsuan | en_US |
| dc.creator (作者) | 曾煥絢 | zh_TW |
| dc.creator (作者) | Tseng, Huan-Hsuan | en_US |
| dc.date (日期) | 1997 | en_US |
| dc.date.accessioned | 18-Sep-2009 18:28:17 (UTC+8) | - |
| dc.date.available | 18-Sep-2009 18:28:17 (UTC+8) | - |
| dc.date.issued (上傳時間) | 18-Sep-2009 18:28:17 (UTC+8) | - |
| dc.identifier (Other Identifiers) | B2002001695 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/36394 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 應用數學研究所 | zh_TW |
| dc.description (描述) | 85751006 | zh_TW |
| dc.description (描述) | 86 | zh_TW |
| dc.description.abstract (摘要) | 在張宜武教授的博士論文中研究到視線表示法和視線數。我們以類似的方法定義有向圖的表示法和有向圖的視線數。 首先，我們定義有向圖的視線數為b(Ｄ) ，Ｄ為有方向性的圖，在論文中可得b(Ｄ)≦┌1/2max｛△﹢(Ｄ),△﹣(Ｄ)｝┐。另一個重要的結論為考慮一個平面有向圖Ｄ，對圖形Ｄ上所有的點v，離開點v的邊（進入的邊）是緊鄰在一起時，則可得有向圖的視線數在這圖形上是１（即 b(Ｄ)=1）。 另外對特殊的圖形也有其不同的視線數，即對有向完全偶圖Ｄm,n ，b(Ｄm,n)≦┌1/2min｛m,n｝┐ ，而對競賽圖Ｄn ，可得b(Ｄn)≦┌n/3┐+1。 | zh_TW |
| dc.description.abstract (摘要) | In [2], Chang stuidied the bar visibility representations and defined bar visibility number.We defined analogously the bar visibility representation and the bar visibility number of a directed graph Ｄ. First we show that the bar visibility number, denoted by b(Ｄ),is at most ┌1/2max｛△﹢(Ｄ),△﹣(Ｄ)｝┐ if D is an oriented graph.And we show that b(Ｄ)=1 for the oriented planar graphs in which all outgoing (incoming) edges of any vertex v of Ｄ appear consecutively around v.For any complete bipartite digraph Ｄm,n ，b(Ｄm,n)≦┌1/2min｛m,n｝┐.For any tournament Ｄn,b(Ｄn)≦┌n/3┐+1. | en_US |
| dc.description.tableofcontents | Contents ABSTRACT Chapter 0 INTRODUCTION….......………………………………………...........1 Chapter 1 BAR VISIBILITY NUMBER AND DEGREE…………....................4 1.1 Some basic results of b(D)………………………………..............4 1.2 S-T form Algorithm….....…………………………………...........7 Chapter 2 BAR VISIBILITY NUMBER OF ORIENTED PLANAR GRAPH14 2.1 Bar visibility Algorithm.………….....………………………......15 2.2 Bar visibility Algorithm of oriented planar graph………….........19 Chapter 3 BAR VISIBILITY NUMBER OF AND ............................24 Chapter 4 CONCLUSIONS………………………………………………….......28 REFERENCES .....................................................................................................30 | zh_TW |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#B2002001695 | en_US |
| dc.subject (關鍵詞) | 有向圖 | zh_TW |
| dc.subject (關鍵詞) | oriented graph | en_US |
| dc.subject (關鍵詞) | planar | en_US |
| dc.title (題名) | 有向圖的視線數 | zh_TW |
| dc.title (題名) | Bar visibility number of oriented graph | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | REFERENCES | zh_TW |
| dc.relation.reference (參考文獻) | [1] J. A. Boundy and U. S. R. Murty, Graph theory with applications (1976). | zh_TW |
| dc.relation.reference (參考文獻) | [2] Yi-Wu Chang, Bar visibility number, Ph.D. thesis, University of Illinois, 92-102, (1994). | zh_TW |
| dc.relation.reference (參考文獻) | [3] S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, (1979). | zh_TW |
| dc.relation.reference (參考文獻) | [4] A. Lempel, S. Even, and I. Cederbaum, An algorithm for planarity testing of graphs, in Theory of Graphs (Proceedings of an International Symposium, Rome, July 1966), (P. Rosenstiehl, ed.), 215-232, Gordon and Breach, New York, (1967). | zh_TW |
| dc.relation.reference (參考文獻) | [5] Y.-L. Lin and S.S. Skiena, Complexity aspects of visibility graphs, International journal of Computational Geometry & Applications. | zh_TW |
| dc.relation.reference (參考文獻) | <br>[6] L. A. Melnikov, Problem at the Sixth Hungarian Colloquium on Combinatorics, Eger, (1981). | zh_TW |
| dc.relation.reference (參考文獻) | [7] M. Schlag, F. Luccio, P. Maestrini, D. T. Lee, and C. K. Wong, A visibility problem in VLSI layout compaction, in Advances in Compution Research, Vol. 2 (F. P. Preparata, ed.), 259-282, JAI Press Inc.,Greenwich, CT, (1985). | zh_TW |
| dc.relation.reference (參考文獻) | [8] M. Sen, S. Das, A.B. Roy, and D.B. West, Interval digraphs: An analogue of interval graphs, J. Graph Theory, Vol. 13, 189-202 (1989). | zh_TW |
| dc.relation.reference (參考文獻) | [9] R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Discrete and Computational Geometry, Vol. 1, 321-341 (1986). | zh_TW |
| dc.relation.reference (參考文獻) | [10] D. B. West, Degrees and digraphs, Introduction to Graph Theory, 46-49, (1996). | zh_TW |
