Please use this identifier to cite or link to this item: https://ah.lib.nccu.edu.tw/handle/140.119/95623
題名: 著色數的規畫模型及應用
作者: 王竣玄
貢獻者: 劉明郎
王竣玄
關鍵詞: 選點問題
著色問題
最小著色數
極大團

指派問題
node packing problem
graph coloring problem
chromatic number
maximal clique
clique
assignment problem
日期: 2002
上傳時間: 9-May-2016
摘要:   著色問題(graph coloring problem)的研究已行之有年,並衍生出廣泛的實際應用,但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型,其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型,其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式,取代原有的選點限制式,縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。
  The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.
摘要\r\nABSTRACT\r\n摘要-----iii\r\n目次-----v\r\n表目次-----vi\r\n圖目次-----vii\r\n第一章 緒論-----1\r\n  1.1 前言-----1\r\n  1.2 文獻回顧-----2\r\n第二章 建構著色問題的0/1整數規畫模型-----4\r\n  2.1 選點問題(NPP)-----4\r\n  2.2 著色問題(GCP)-----5\r\n  2.3 完全圖-----9\r\n  2.4 點著色有限制時的GCP-----12\r\n第三章 特殊指派問題-----14\r\n  3.1 問題描述-----14\r\n  3.2 尋找極大團的演算法-----18\r\n  3.3 實例及計算結果-----20\r\n第四章 結論與建議-----25\r\n參考文獻-----26\r\n附錄 GAMS程式-----28\r\n\r\n表目次\r\n表一 10件工作的時段-----21\r\n表二 人員被雇用的底薪要求-----21\r\n表三 每位人員執行每項工作所要求的薪資-----21\r\n表四 實例計算結果之比較-----24\r\n\r\n圖目次\r\n圖一 範例2.2中的圖形G=(V,E)-----9\r\n圖二 特殊指派問題範例的工作時間區段-----16\r\n圖三 工作1至工作7所生成的圖形H-----17\r\n圖四 G1是一個區間圖-----19\r\n圖五 G1的區間表示重新排序-----20\r\n圖六 工作的時段區間分佈圖-----22\r\n圖七 將不連續的工作時段區間重新命名-----22\r\n圖八 利用演算法3.1將工作時段的區間重新排序-----23\r\n圖九 實例問題的最佳指派-----24
參考文獻: Akkoyunlu, E. A., The enumeration of maximal cliques of large graphs, SIAM Journal on Computing 2, 1-6 (1973).\r\nBalakrishnan, R. and K. Ranganathan, A Textbook of Graph Theory, Springer, New York, NY (1991).\r\nBalas, E. and C. Yu, Finding a maximum clique in an arbitrary graph, SIAM Journal on Computing 15, 1054-1068 (1986).\r\nBalas, E. and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM Journal on Computing 20, 209-221 (1991).\r\nBron, C. and J. Kerbosch, Finding all cliques of an undirected graph, Communications of the ACM 16, 575-579 (1973).\r\nBrooke, A., D. Kendrick, and A. Meeraus, GAMS-A User’s Guide, The Scientific Press, Redwood City, CA (1988).\r\nChaudhry, S., S. McCormick, and I. D. Moon, Locating independent facilities with maximum weight: Greedy heuristics, Omega 14, 383-389 (1986).\r\nJoseph, D., J. Meidanis, and P. Tiwari, Determining DNA sequence similarity using maximal independent set algorithms for interval graphs, Algorithms Theory — SWAT ’92, 326-337 (1992).\r\nLeighton, F. T., A graph coloring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards 84(6), 489-496 (1979).\r\nMehta, N. K., The application of a graph coloring method to an examination scheduling problem, Interfaces 11(5), 57-61 (1981).\r\nMoon, I. D. and S. Chaudhry, An analysis of network location problems with distance constraints, Management Science 30, 290-307 (1984).\r\nMurray, A. and R. Church, Facets for node packing, European Journal of Operational Research 101, 598-608 (1997).\r\nNemhauser, G. L. and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, NY (1988).\r\nPadberg, M., On the facial structure of set packing polyhedra, Mathematical Programming 5, 199-215 (1973).\r\nPardalos, P. and J. Xue, The maximal clique problem, Journal of Global Optimization 4, 301-328 (1994).\r\nToregas, C., R. Swain, C. ReVelle, and L. Bergman, The location of emergency service facilities, Operations Research 19, 1363-1373 (1971).\r\nTucker, A., Applied Combinatorics, Wiley, New York, NY (1995).\r\nWeintraub, A., F. Barahona, and R. Epstein, A column generation algorithms for solving general forest planning problems with adjacency constraints, Forest Science 40, 142-161 (1994).\r\nde Werra, D., Extensions of coloring models for scheduling purposes, European Journal of Operational Research 92, 474-492 (1996).\r\nde Werra, D., On a multiconstrained model for chromatic scheduling, Discrete Applied Mathematics 94, 171-180 (1999).\r\nWelsh, D. J. A. and M. B. Powell, An upper bound to the chromatic number of a graph and its application to the timetabling problems, Computer Journal 10, 85-86 (1967).\r\nWest, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NY (1996).\r\nWood, D. C., A technique for coloring a graph applicable to large scale time-tabling problems, Computer Journal 12, 317-319 (1969).
描述: 碩士
國立政治大學
應用數學系
89751007
資料來源: http://thesis.lib.nccu.edu.tw/record/#A2010000326
資料類型: thesis
Appears in Collections:學位論文

Files in This Item:
File SizeFormat
index.html115 BHTML2View/Open
Show full item record

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.