本研究之目的是針對單接頭的一般化運動鏈、運動鏈、及呆鏈進行數目合成。基於圖學理論和運動鏈矩陣，提出四種確認演算法來判斷運動鏈的類型，以及三種列舉演算法來合成各種類型的運動鏈。並根據所提出的演算法發展電腦軟體，合成與繪圖製各種一般化運動鏈、運動鏈、及呆鏈圖譜，作為機構概念設計或創意性機構設計之用。
首先介紹機構運動鏈與圖學理論相關術語與定義，舉例說明其涵義，據此針對單接頭運動鏈之數目合成方法，做詳細的文獻回顧與探討。接著，對本研究所用之基本理論與概念如連桿類配、縮桿類配、及多接頭連桿鄰接矩陣合成、連桿鄰接矩陣合成等舉例說明並探究。以機構運動鏈文獻與基本理論為基礎，提出確認分離連桿演算法來刪除分離連桿運動鏈，以及確認庫拉托夫斯基(Kuratowski)圖形演算法是來刪除非平面圖形，並提出一種繪圖演算法以進行繪製機構運動鏈與圖。基於以上述的確認演算法，本研究提出一種列舉演算法可合成與繪製所有一般化運動鏈圖譜。再者，利用三桿基本呆鏈與退化運動鏈演算法，檢驗運動鏈是否為退化運動鏈，並提出運動鏈與呆鏈列舉演算法，合成出各種運動鏈與呆鏈圖譜。最後，根據以上所提出的演算法，發展出一套電腦軟體供機構設計者使用，可產生各種連桿與接頭數目之非同構單接頭機構運動鏈圖譜。
藉由本研究所提出的演算法，不只可精確地獲得所有機構運動鏈圖譜，且可簡化機構概念設計程序。

This work provides four checking algorithms and three enumeration algorithms based on graph theory and kinematic matrices for the number synthesis and the construction of the necessary atlases of generalized kinematic chains, kinematic chains, and rigid chains for the conceptual design of mechanisms. Furthermore, a computer program is developed to synthesize and sketch the various atlases of generalized kinematic chains, kinematic chains, and rigid chains with simple joints based on the proposed algorithms.
Firstly, the fundamental definitions and terminology regarding kinematic chains of mechanisms and graph theory are introduced. The literature survey on the number synthesis of various kinematic chains with simple joints is reviewed and studied. Then, the basic theories and concepts such as link assortments, contracted link assortments, and the synthesis of multiple link adjacency matrices and link adjacency matrices are presented and illustrated with examples. The algorithm for checking cut-links is provided for the elimination of chains with cut-links. The algorithm for checking Kuratowski graphs is proposed to delete non-planar graphs. And, a sketching algorithm is developed to sketch kinematic graphs or chains based on the basic contracted graphs. According to these algorithms, an enumeration algorithm is proposed for the construction of generalized kinematic chains. Furthermore, two algorithms for checking three-bar basic rigid chains and degenerate kinematic chains are put forward to discard the degenerate kinematic chains. Then, two enumeration algorithms are proposed for the synthesis of kinematic chains and rigid chains. Finally, a computer program based on the proposed algorithms is developed to synthesize and sketch various non-isomorphic generalized kinematic chains, kinematic chains, and rigid chains with simple joints.
The proposed algorithms and computer programs not only can precisely obtain various atlases of generalized kinematic chains, kinematic chains, and rigid chains, but also can simplify the methodology for the conceptual design of mechanisms.

[1] R.C. Johnson and K. Towfigh, Application of number synthesis to practical problems in creative design, ASME paper, No. 65-WA-MD9, 1965.
[2] A.S. Hall, Jr., Generalized Linkages Forms of Mechanical Devices, ME261 Class notes, Purdue University, West Lafayette, Indiana, spring 1978.
[3] H.S. Yan, A methodology for creative mechanism design, Mechanism and Machine Theory, Vol. 27, No. 3, pp.235-242, 1992.
[4] H.S. Yan, Creative Design of Mechanical Devices, Springer-Verlag, Singapore, 1998.
[5] F. Freudenstein and E.R. Maki, The creation of mechanisms according to kinematic structure and function, Environment and Planning B, Vol. 6, pp. 375-391, 1979.
[6] L.W. Tsai, Mechanism Design: Enumeration of Kinematic Structures According to Function, CRC Press, Boca Raton, Florida, USA, 2000.
[7] J. Clark and D. A. Holton, A First Look at Graph Theory, World Scientific, Singapore, 1991.
[8] F. Harary, Graph Theory, Addison-Wesley, Reading, Massachusetts, 1969.
[9] F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, New York, 1973.
[10] F. Freudenstein and L.S. Woo, Kinematic structure of mechanisms, Basic Questions of Design Theory, North Holland, American Elsevier, New York, pp. 241-264, 1974.
[11] D.G. Olson, A.G. Erdman, and D.R. Riley, A systematic procedure for type synthesis of mechanisms with literature review, Mechanism and Machine Theory, Vol. 20, No. 4, pp. 285-295, 1985.
[12] C.R. Tischler, A.E. Samuel, and K.H. Hunt, Kinematic chains for robot hands— I. orderly number-synthesis, Mechanism and Machine Theory, Vol. 30, No. 8, pp. 1193-1215, 1995.
[13] T.S. Mruthyunjaya, Kinematic structure of mechanisms revisited, Mechanism and Machine Theory, Vol. 38, pp. 279-320, 2003.
[14] R. Simoni, A.P. Carboni, H. Simas, and D. Martins, Enumeration of kinematic chains and mechanisms review, Proceedings of the 13th World Congress on Mechanism and Machine Science, Guanajuato, Mexico, pp. 19-25, 2011.
[15] M. Grübler, Allgemeine Eigenschaften der zwanglaufigen ebenen kinematischen Ketten part I, Civilingenieur 29, pp. 167-200, 1883; part II, Verh. Ver. Bef. Gew., Vol. 64, pp. 179-223, 1885.
[16] H. Alt, Zur synthese der ebenen mechanismen, Journal of Applied Mathematics and Mechanics, Vol. 1, No. 5, pp. 373-398, 1921.
[17] K. Hain, Applied Kinematics, 2nd ed., McGraw-Hill, New York, 1967. Original German edition, Angewandte Getrieblehre, Hermann Schroedel, Hannover, Germany, 1952. Reference to K. Hain, Die analyse und synthese der achtgliedrigen Gelenkgetriebe, VDI Berichte 5, pp. 81-93, 1955.
[18] F.R.E. Crossley, A contribution to Gruebler’s theory in the number synthesis of plane mechanisms, ASME Transactions, Journal of Engineering for Industry, pp. 1-8, 1964.
[19] F.R.E. Crossley, On an unpublished work of Alt, Journal of Mechanisms, Vol. 1, pp. 165-170, 1966.
[20] G. Kiper, and D. Schian, Sammlung Der Grüblerschen Kinematischen Ketten Mit Bis Zu Zwolf Gliedern (English: Collection of Grüblerschen Kinematic Chains with up to Twelve Members), Z. VDI, (VID-Verlag Diisseldorf,) 1976.
[21] R. Franke, Vom Aufbau der Getriebe (3rd edition), Vol. I, VDI Verlag, Bremen-Blumenthal, Germany, 1958.
[22] T.H. Davies and F.R.E. Crossley, Structural analysis of plane linkages by Franke’s condensed notation, Journal of Mechanism, Vol. 1, pp. 171-183, 1966.
[23] S.L. Haas and F.E. Crossley, Structural synthesis of a four-bit binary adding mechanism, ASME Transactions, Journal of Engineering for Industry, Vol. 91(1), pp. 240-249, 1969.
[24] A.H. Soni, Structural analysis of two general constraint kinematic chains and their practical applications, ASME Transactions, Journal of Engineering for Industry, Vol. 93, pp. 231-238, 1971.
[25] F.R.E. Crossley, The permutations of kinematic chains of eight members or less from the graph-theoretic viewpoint, Developments in Theoretical and Applied Mechanisms, Vol. 2, Pergamon Press, Oxford, pp. 467-486, 1964.
[26] F. Freudenstein and L. Dobrjanskyj, On a theory for the type synthesis of mechanisms, Proceedings of the 11th International Congress of Applied Mechanics, pp. 420-428, 1966.
[27] L. Dobrjanskyj and F. Freudenstein, Some applications of graph theory to the structural analysis of mechanisms, ASME Transactions, Journal of Engineering for Industry, Series 89(B), pp. 153-158, 1967.
[28] W. Huang and A.H. Soni, Application of linear and nonlinear graphs in structural synthesis of kinematic chains, ASME Transactions, Journal of Engineering for Industry, pp. 525-532, 1973.
[29] M. Mayourian and F. Freudenstein, The development of an atlas of the kinematic structures of mechanisms, ASME Transactions, Journal of Mechanisms, Transmissions, and Automation in Design, pp. 1-4, 1984.
[30] D.G. Olson, T.R. Thompson, D.R. Riley, and A.G. Erdman, An algorithm for automatic sketching of planar kinematic chains, ASME Transactions, Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 107, pp. 106-111, 1985.
[31] W.J. Sohn and F. Freudenstein, An application of dual graphs to the automatic generation of the kinematic structures of mechanisms, ASME Transactions, Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 108, No. 3, pp. 392-398, 1986.
[32] K. Sugimoto, A. Hara, and S. Sakaue, An algorithm for the automatic generation of kinematic chains, JSME International Journal, Vol. 30, No. 269, pp. 1805-1811, 1987.
[33] I. Tempea, Type synthesis of plane kinematic chains with 11 links and L3=5 degree of freedom, Proceedings of the 8th World Congress on the Theory of Machines and Mechanisms, Prague, Czechoslovakia, August 26-31, pp. 63-66, 1991.
[34] N.P. Belfiore and E. Pennestri, Automatic sketching of planar kinematic chains, Mechanism and Machine Theory, Vol. 29, No.1, pp. 177-193, 1994.
[35] S.H. Nie, A.H. Liao, A.H. Qiu, and S.G. Gong, Addition method with 2 links and 3 pairs of type synthesis to planar closed kinematic chains, Mechanism and Machine Theory, Vol. 58, pp. 179-191, 2012.
[36] M.A. Pucheta, N.E. Ulrich, and A. Cardona, Automatic sketching of non-fractionated kinematic chains, Mechanism and Machine Theory, Vol. 68, pp. 67-82, 2013.
[37] M.A. Pucheta, N.E. Ulrich, and A. Cardona, Combined graph layout algorithms for automated sketching of kinematic chains, Proceedings of the ASME 2012 International Design Engineering Technical Conferences, DETC2012-70665.
[38] H.J. Lee and Y.S. Yoon, Automatic method for enumeration of complete set of kinematic chains, The Japan Society of Mechanical Engineers International Journal, Series C, Vol. 37, No. 4, pp. 812-818, 1994.
[39] L.S. Woo, Type synthesis of plane linkages, ASME Transactions, Journal of Engineering for Industry, pp. 159-170, 1967.
[40] F. Freudenstein, The basic concepts of Polya’s theory of enumeration, with application to the structural classification of mechanisms, Journal of Mechanisms, Vol. 3, pp. 275-290, 1967.
[41] F.Y. Chen and W.K. Chen, On the realizability of permutational synthesis of mechanisms, ASME paper No. 70-Mech-58, 1970.
[42] I. Tempea, Contributions concerning the methods of determination of the necessary contracted graphs for the structural synthesis of planar kinematic chain, Proceedings of the 3rd World Congress on the Theory of Machines and Mechanisms, Vol. D, Paper D-18, pp. 251-272, 1971.
[43] D.J. Sanger, The structure of kinematic chains which contain links of maximum degree, Mechanism and Machine Theory, Vol. 9, pp. 115-121, 1974.
[44] H.S. Yan and Y.W. Hwang, A new algorithm for automatic sketching of kinematic chains, Proceedings of the 1989 ASME International Computers in Engineering Conference, pp. 245-250, 1989.
[45] H.S. Yan and C.H. Hsu, Contracted graphs of kinematic chains with multiple joints, Mathematical and Computer Modelling, Vol. 10, No. 9, pp. 681-695, 1988.
[46] G. Baranov, Classification, formation, kinematics, and kinetostatics of mechanisms with pairs of the first kind (in Russian), Proceedings of Seminar on the Theory of Machines and Mechanisms, Moscow, Vol. 2, pp. 15-39, 1952.
[47] N.I. Manolescu and I.I. Tempea, Method of determination of the number of structural-kinematic variants of KCsj by the operations of “grapization” (G), “joints simplifying” (JS) and “dyad amplifying” (DA), Proceedings of the 3rd World Congress on the Theory of Machines and Mechanisms, Vol. C, Paper C-12, pp. 145-162, 1971.
[48] N.I. Manolescu, A method based on Baranov trusses, and using graph theory to find the set of planar jointed kinematic chains and mechanisms, Mechanism and Machine Theory, Vol. 8, pp. 3-22, 1973.
[49] N.I. Manolescu, For a united point of view in the study of the structural analysis of kinematic chains and mechanisms, Journal of Mechanisms, Vol. 3, pp. 149-169, 1968.
[50] N.I. Manolescu, The unitary method of structural synthesis of all the planar jointed kinematic chains (KCMJSL), Proceedings of the 5th World Congress on Theory of Machines and Mechanisms, pp. 514-517, 1979.
[51] N.I. Manolescu, A unified method for the formation of all planar jointed kinematic chains and Baranov trusses, Environment and planning B, Vol. 6, pp. 447-454, 1979.
[52] T.S. Mruthyunjaya, Structural synthesis by transformation of binary chains, Mechanism and Machine Theory, Vol. 14, pp. 221-231, 1979.
[53] T.S. Mruthyunjaya, A computerized methodology for structural synthesis of kinematic chains: part 1-formulation, Mechanism and Machine Theory, Vo. 19, No. 6, pp. 487-495, 1984.
[54] T.S. Mruthyunjaya, A computerized methodology for structural synthesis of kinematic chains: part 2-application to several fully or partially known cases, Mechanism and Machine Theory, Vo. 19, No. 6, pp. 497-505, 1984.
[55] T.S. Mruthyunjaya, A computerized methodology for structural synthesis of kinematic chains: part 3-application to the new case of 10-link, three-freedom chains, Mechanism and Machine Theory, Vo. 19, No. 6, pp. 507-530, 1984.
[56] T.S. Mruthyunjaya, H.R. Balasubramanian, and K. Vijayananda, Computerized structural synthesis and analysis of eleven-link, two-freedom kinematic chains, Revue Roumaine des Sciences Techniques, Serie de Mecanique Appliquee, Vol. 37, No. 1, pp. 91-105, 1992.
[57] T.S. Mruthyunjaya and H.R. Balasubramanian, In quest of a reliable and efficient computational test for detection of isomorphism in kinematic chains, Mechanism and Machine Theory, Vol. 22, pp. 131-139, 1987.
[58] J. Denavit and R.S. Hartenberg, A kinematic notation for lower-pair mechanisms based on matrices, ASME Transactions, Journal of Applied Mechanics, Vol. 22, pp. 215-221, 1955.
[59] A. Raicu, Matrices associated with kinematic chains with from 3 to 5 members, Mechanism and Machine Theory, Vol. 9, pp. 123-129, 1974.
[60] T.S. Mruthyunjaya and M. R. Raghavan, Structural analysis of kinematic chains and mechanisms based on matrix representation, ASME Transactions, Journal of Mechanical Design, Vol. 101, pp. 488-494, 1979.
[61] H.S. Yan and Y.W. Hwang, Number synthesis of kinematic chains based on permutation groups, Mathematical and Computer Modelling, Vol. 13, No. 8, pp. 29-42, 1990.
[62] W.M. Hwang, Y.W. Hwang, and Y.Y. Liu, A method for the number synthesis of planar kinematic chains with simple joints, Journal of the Chinese Society of Mechanical Engineers, Taipei, Vol. 12, No. 2, pp. 166-176, 1991.
[63] W.M. Hwang and Y.W. Hwang, Computer-aided structural synthesis of planar kinematic chains with simple joints, Mechanism and Machine Theory, Vol. 27, No. 2, pp. 189-199, 1992.
[64] S. Mauskar and S. Krishnamurty, A loop configuration approach to automatic sketching of mechanisms, Mechanism and Machine Theory, Vol. 31, No. 4, pp. 423-437, 1996.
[65] C.F. Hsieh, Y.W. Hwang, and H.S. Yan, Generation and sketching of generalized kinematic chains, Proceedings of the ASME 2008 International Design Engineering Technical Conferences, DETC2008/VIB-49043.
[66] E.R. Tuttle and S.W. Peterson, Symmetry group theory applied to kinematic chain enumeration, Proceedings of the 10th Applied Mechanisms Conference, New Orleans, Louisiana 2, Vol. 4B, 1987.
[67] E.R. Tuttle, S.W. Peterson, and J. Titus, Enumeration of basic kinematic chains using the theory of finite groups, ASME Transactions, Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 111, No. 4, pp. 498-503, 1989.
[68] E.R. Tuttle, S.W. Peterson, and J.E. Titus, Further applications of group theory to the enumeration and structural analysis of basic kinematic chains, ASME Transactions, Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 111, No. 4, pp. 494-497, 1989.
[69] E.R. Tuttle, Generation of planar kinematic chains, Mechanism and Machine Theory, Vol. 31, No. 6, pp. 729-748, 1996.
[70] W.E. Fang and F. Freudenstein, The stratified representation of mechanisms, ASME Transactions, Journal of Mechanical Design, Vol. 112, pp. 514-519, 1990.
[71] E.A. Butcher and C. Hartman, Enumeration and classification of 12-bar planar simple-jointed kinematic chains using a hierarchical approach, Proceedings of the ASME 2002 International Design Engineering Technical Conferences, DETC2002/MECH-34253.
[72] E.A. Butcher and C. Hartman, Efficient enumeration and hierarchical classification of planar simple-jointed kinematic chains: application to 12- and 14-bar single degree-of-freedom chains, Mechanism and Machine Theory, Vol. 40, pp. 1030-1050, 2005.
[73] C.F. Earl and J. Rooney, The generation of kinematic structures for planar kinematic chains, Proceedings of the 6th World Congress on Theory of Machines and Mechanisms, pp. 133-136, 1983.
[74] W.H. Chieng and D.A. Hoeltzel, A combinatorial approach for the automatic sketching of planar kinematic chains and epicyclic gear trains, ASME Transactions, Journal of Mechanical Design, Vol. 112, pp. 6-15, 1990.
[75] V.K. Sethi and V.P. Agrawal, Hierarchical classification of kinematic chains: a multigraph approach, Mechanism and Machine Theory, Vol. 28, No. 4, pp. 601-614, 1993.
[76] A.C. Rao and P.B. Deshmukh, Computer aided structural synthesis of planar kinematic chains obviating the test for isomorphism, Mechanism and Machine Theory, Vol. 36, pp. 489-506, 2001.
[77] R.P. Sunkari and L.C. Schmidt, Structural synthesis of planar kinematic chains by adapting a Mckay-type algorithm, Mechanism and Machine Theory, Vol. 41, pp. 1021-1030, 2006.
[78] D. Martins, R. Simoni, and A.P. Carboni, Fractionation in planar kinematic chains: reconciling enumeration contradictions, Mechanism and Machine Theory, Vol. 45, pp. 1628-1641, 2010.
[79] Z. Huang, H.F. Ding, and Y. Cao, The novel characteristic representations of kinematic chains and their applications, Proceedings of the ASME 2005 International Design Engineering Technical Conferences, DETC2005-84282.
[80] H.F. Ding and Z. Huang, A unique representation of the kinematic chain and the atlas database, Mechanism and Machine Theory, Vol. 42, pp. 637-651, 2007.
[81] H.F. Ding and Z. Huang, A new theory for the topological structure analysis of kinematic chains and its applications, Mechanism and Machine Theory, Vol. 42, pp. 1264-1279, 2007.
[82] H.F. Ding and Z. Huang, The establishment of the canonical perimeter topological graph of kinematic chains and isomorphism identification, ASME Transactions, Journal of Mechanical Design, Vol. 129, pp. 915-923, 2007.
[83] H.F. Ding, Z. Huang, and D. Mu, Computer-aided structure decomposition theory of kinematic chains and its applications, Mechanism and Machine Theory, Vol. 43, pp. 1596-1609, 2008.
[84] H.F. Ding, J. Zhao, and Z. Huang, Unified topological representation models of planar kinematic chains, ASME Transactions, Journal of Mechanical Design, Vol. 131, pp. 114503-1~6, 2009.
[85] H.F. Ding, and Z. Huang, Isomorphism identification of graphs: especially for the graphs of kinematic chains, Mechanism and Machine Theory, Vol. 44, pp. 122-139, 2009.
[86] H.F. Ding, J. Zhao, and Z. Huang, The establishment of edge-based loop algebraic theory of kinematic chains and its applications, Engineering with Computers, Vol. 26, pp. 119-127, 2010.
[87] H.F. Ding, F.M. Hou, A. Kecskemethy, and Z. Huang, Synthesis of a complete set of contracted graphs for planar non-fractionated simple-jointed kinematic chains with all possible DOFs, Mechanism and Machine Theory, Vol. 46, pp. 1588-1600, 2011.
[88] H.F. Ding, A. Kecskemethy, and Z. Huang, Atlas database of 2-DOF kinematic chains and its application to the creative design of mechanisms, Proceedings of the ASME 2011 International Design Engineering Technical Conferences, DETC2011-47264.
[89] H.F. Ding, F.M. Hou, A. Kecskemethy, and Z. Huang, Synthesis of the whole family of planar 1-DOF kinematic chains and creation of their atlas database, Mechanism and Machine Theory, Vol. 47, pp. 1-15, 2012.
[90] H.F. Ding, W. Cao, A. Kecskemethy, and Z. Huang, Complete atlas database of 2-DOF kinematic chains and creative design of mechanisms, ASME Transactions, Journal of Mechanical Design, Vol. 134, pp. 031006-1~10, 2012.
[91] H.F. Ding, P. Huang, B. Zi, and A. Kecskemethy, Automatic synthesis of kinematic structures of mechanisms and robots especially for those with complex structures, Applied Mathematical Modelling, Vol. 36, pp. 6122-6131, 2012.
[92] H.F. Ding, B. Zi, P. Huang, and A. Kecskemethy, The whole family of kinematic structures for planar 2- and 3-DOF fractionated kinematic chains, Mechanism and Machine Theory, Vol. 70, pp. 74-90, 2013.
[93] H.F. Ding, P. Huang, J.F. Liu, and A. Kecskemethy, Automatic structural synthesis of the whole family of planar 3-degrees of freedom closed loop mechanisms, ASME Transactions, Journal of Mechanisms and Robotics, Vol. 5, pp. 041006-1~10, 2013.
[94] H.S. Yan and F. Harary, On the maximum value of the maximum degree of kinematic chains, ASME Transactions, Journal of Mechanism, Transmissions, and Automation in Design, Vol. 109, No. 4, pp. 487-490, 1987.
[95] F. Harary and H.S. Yan, Logical foundations of kinematic chains: graphs, line graphs, and hypergraphs, ASME Transactions, Journal of Mechanical Design, Vol. 112, pp. 79-83, 1990.
[96] A. Gagarin, G. Labelle, P. Leroux, and T. Walsh, Structure and enumeration of two-connected graphs with prescribed three-connected components, Advances in Applied Mathematics, Vol. 43, pp. 46-74, 2009.
[97] H.S. Yan and M.W. Hwang, Atlas of basic rigid chains, Proceedings of the 9th Applied Mechanisms Conference, Kansas City, Missouri, 1985.
[98] W.M. Hwang and Y.W. Hwang, An algorithm for the detection of degenerate kinematic chains, Mathematical and Computer Modelling, Vol. 15, No. 11, pp. 9-15, 1991.