Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 有向圖的視線數
Bar visibility number of oriented graph
作者 曾煥絢
Tseng, Huan-Hsuan
貢獻者 張宜武
Chang, Yi-Wu
曾煥絢
Tseng, Huan-Hsuan
關鍵詞 有向圖
oriented graph
planar
日期 1997
上傳時間 18-Sep-2009 18:28:17 (UTC+8)
摘要 在張宜武教授的博士論文中研究到視線表示法和視線數。我們以類似的方法定義有向圖的表示法和有向圖的視線數。
     首先,我們定義有向圖的視線數為b(D) ,D為有方向性的圖,在論文中可得b(D)≦┌1/2max{△﹢(D),△﹣(D)}┐。另一個重要的結論為考慮一個平面有向圖D,對圖形D上所有的點v,離開點v的邊(進入的邊)是緊鄰在一起時,則可得有向圖的視線數在這圖形上是1(即 b(D)=1)。
     另外對特殊的圖形也有其不同的視線數,即對有向完全偶圖Dm,n ,b(Dm,n)≦┌1/2min{m,n}┐ ,而對競賽圖Dn ,可得b(Dn)≦┌n/3┐+1。
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 D.
     First we show that the bar visibility number, denoted by b(D),is at most ┌1/2max{△﹢(D),△﹣(D)}┐ if D is an oriented graph.And we show that b(D)=1 for the oriented planar graphs in which all outgoing (incoming) edges of any vertex v of D appear consecutively around v.For any complete bipartite digraph Dm,n ,b(Dm,n)≦┌1/2min{m,n}┐.For any tournament Dn,b(Dn)≦┌n/3┐+1.
參考文獻 REFERENCES
[1] J. A. Boundy and U. S. R. Murty, Graph theory with applications (1976).
[2] Yi-Wu Chang, Bar visibility number, Ph.D. thesis, University of Illinois, 92-102, (1994).
[3] S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, (1979).
[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).
[5] Y.-L. Lin and S.S. Skiena, Complexity aspects of visibility graphs, International journal of Computational Geometry & Applications.
<br>[6] L. A. Melnikov, Problem at the Sixth Hungarian Colloquium on Combinatorics, Eger, (1981).
[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).
[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).
[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).
[10] D. B. West, Degrees and digraphs, Introduction to Graph Theory, 46-49, (1996).
描述 碩士
國立政治大學
應用數學研究所
85751006
86
資料來源 http://thesis.lib.nccu.edu.tw/record/#B2002001695
資料類型 thesis
dc.contributor.advisor 張宜武zh_TW
dc.contributor.advisor Chang, Yi-Wuen_US
dc.contributor.author (Authors) 曾煥絢zh_TW
dc.contributor.author (Authors) Tseng, Huan-Hsuanen_US
dc.creator (作者) 曾煥絢zh_TW
dc.creator (作者) Tseng, Huan-Hsuanen_US
dc.date (日期) 1997en_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) B2002001695en_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 (描述) 85751006zh_TW
dc.description (描述) 86zh_TW
dc.description.abstract (摘要) 在張宜武教授的博士論文中研究到視線表示法和視線數。我們以類似的方法定義有向圖的表示法和有向圖的視線數。
     首先,我們定義有向圖的視線數為b(D) ,D為有方向性的圖,在論文中可得b(D)≦┌1/2max{△﹢(D),△﹣(D)}┐。另一個重要的結論為考慮一個平面有向圖D,對圖形D上所有的點v,離開點v的邊(進入的邊)是緊鄰在一起時,則可得有向圖的視線數在這圖形上是1(即 b(D)=1)。
     另外對特殊的圖形也有其不同的視線數,即對有向完全偶圖Dm,n ,b(Dm,n)≦┌1/2min{m,n}┐ ,而對競賽圖Dn ,可得b(Dn)≦┌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 D.
     First we show that the bar visibility number, denoted by b(D),is at most ┌1/2max{△﹢(D),△﹣(D)}┐ if D is an oriented graph.And we show that b(D)=1 for the oriented planar graphs in which all outgoing (incoming) edges of any vertex v of D appear consecutively around v.For any complete bipartite digraph Dm,n ,b(Dm,n)≦┌1/2min{m,n}┐.For any tournament Dn,b(Dn)≦┌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/#B2002001695en_US
dc.subject (關鍵詞) 有向圖zh_TW
dc.subject (關鍵詞) oriented graphen_US
dc.subject (關鍵詞) planaren_US
dc.title (題名) 有向圖的視線數zh_TW
dc.title (題名) Bar visibility number of oriented graphen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) REFERENCESzh_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