Microsoft Word - tpel.doc Mathematical Problems of Computer Science 36, 104--114, 2012. 104 Necessary Conditions for Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root Armen Khachaturyan Yerevan State University e-mail: khachaturyanarmen@gmail.com Abstract In the graph theory the problem of the minimum placement of graph by the height, which is similarly formulated in [2] (the problem of minimum cut arrangement of graph), is known. The problem is NP-complete [3]. In the present paper a partial case of this problem, i.e. the problem of optimal permissible placement by the height of the transitive directed tree with one root (which is a such transitive directed graph, the arc base of which forms a directed tree with one root), is formulated. In this paper some new concepts are introduced and necessary conditions for optimal solving of the new formulated problem are given. Keywords: transitive directed graph, optimal placement. R e f e r e n c e s 1. A. H. Khachaturyan, “The optimal permissible placement by the height of the transitive oriented tree containing one vertex of branching”, Mathematical Problems of Computer Science, vol. 33, pp183-186, 2010. 2. M.R. Garey, D.S. Johnson, Computers and intractability: A guide to the theory of NP- completeness. San Francisco, CA: W.H. Freeman, 1979. 3. F. Gavril, “Some NP-complete problems on graphs,” Proc.11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD, pp. 91-95, 1977. 4. M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, “Complexity results for bandwidth minimization”, SIAM J. Appl. Math., vol. 34, pp. 477–495. 1978. 5. M. R. Garey, D. S. Johnson and L. Stockmeyer, “Some simplified NP-complete graph problems”, Theor. Comput. Sci., vol. 1, pp. 237–267. 1976. 6. Ch. H. Papadimitriou, “The NP-completeness of the bandwidth minimization problem”, Computing, v. 16, pp. 263–270. 1976. 7. A.V. Petrosyan, S. E. Markosyan, Yu. H. Shukuryan, Mathematical Problems of Automation and Projection of Calculating-Machine. Yer., (in Russian). 1977. 8. G.G. Geoletsyan, “Flat placement of the vertices of tree with minimization of width”, DAN Arm. SSR, issue 56, no. 4, pp. 202–207 (in Russian). 1973. 9. L. M. Goldberg and I. A. Klipker, “Minimum placement of trees on a line,” Technical Report, Physico-Technical Institute of Low Temperatures, Academy of Sciences of Ukraine SSR, 1976. A. Khachaturyan 105 10. Y. Shiloach, “A minimum linear arrangement algorithm for undirected trees” Report, Dept. Of Applied Mathematics, Weizmann Institute, Rehovot, Israel. 1976. 11. D. Adolphson and T.C. Hu, “Optimal linear ordering”, SIAM J. Appl. Math., vol. 25, no. 3, pp. 403–423. 1973. 12. C. Berge, The Theory of Graphs and Its Applications. New York: Wiley, 1962. Ø»Ï ³ñÙ³ïáí փոխանցական կողմնորոշ ͳéÇ Áëï µ³ñÓñáõÃÛ³Ý ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ ï»Õ³¹ñáõÃÛ³Ý ³ÝÑñ³Å»ßï å³ÛÙ³ÝÝ»ñ ². ʳã³ïáõñÛ³Ý ²Ù÷á÷áõÙ ¶ñ³ýÝ»ñÇ ï»ëáõÃÛ³Ý Ù»ç ѳÛïÝÇ ¿ ·ñ³ýÇ Áëï µ³ñÓñáõÃÛ³Ý ûåïÇÙ³É ï»Õ³¹ñÙ³Ý ËݹÇñÁ, áñÁ ѳٳñÅ»ù Ï»ñåáí Ó¨³Ï»ñåí³Í ¿ [2]-áõÙ (·ñ³ýÇ ÙÇÝÇÙ³É Ïïñí³Íùáí ϳñ·³íáñÙ³Ý ËݹÇñÁ): ÊݹÇñÁ NP-¹Åí³ñ ¿: êáõÛÝ ³ß˳ï³ÝùáõÙ Ó¨³Ï»ñåí³Í ¿ ³Ûë ËݹñÇ Ù³ëݳÏÇ ¹»åùÁ` Ù»Ï ³ñÙ³ïáí փոխանցական կողմնորոշ ͳéÇ (¹³ ³ÛÝ փոխանցական կողմնորոշ ·ñ³ýÝ ¿, áñÇ ³Õ»ÕÝ»ñÇ µ³½³Ý ϳ½ÙáõÙ ¿ Ù»Ï ³ñÙ³ïáí կողմնորոշ ͳé) Áëï µ³ñÓñáõÃÛ³Ý ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ ï»Õ³¹ñÙ³Ý ËݹÇñÁ: ²Ûë ³ß˳ï³ÝùáõÙ Ý»ñϳ۳óí»É »Ý áñáß³ÏÇ Ýáñ ѳëϳóáõÃÛáõÝÝ»ñ ¨ ïñí»É Ó¨³Ï»ñåí³Í ËݹñÇ ûåïÇÙ³É ÉáõÍÙ³Ý ³ÝÑñ³Í»ßï å³ÛÙ³ÝÝ»ñ: Íåîáõîäèìûå óñëîâèÿ îïòèìàëüíîé äîïóñòèìîé ðàññòàíîâêè ïî âûñîòå òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì À. Õà÷àòóðÿí Аннотация  òåîðèè ãðàôîâ èçâåñòíà ïðîáëåìà ìèíèìàëüíîé ðàññòàíîâêè ãðàôà ïî âûñîòå, êîòîðàÿ àíàëîãè÷íî ñôîðìóëèðîâàíà â [2] (ïðîáëåìà óïîðÿäî÷èâàíèÿ ãðàôà ñ ìèíèìàëüíûì ðàçðåçîì). Ïðîáëåìà NP-ïîëíà 3.  íàñòîÿùåé ñòàòüå ôîðìóëèðîâàí ÷àñòíûé ñëó÷àé ýòîé ïðîáëåìû: ïðîáëåìà îïòèìàëüíî äîíóñòèìîé ðàññòàíîâêè ïî âûñîòå òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì (ýòî òàêîé òðàíçèòèâíî îðèåíòèðîâàííûé ãðàô, áàçà äóã êîòîðîãî ñîñòàâëÿåò îðèåíòèðîâàííîå äåðåâî ñ îäíèì êîðíåì).  ðàáîòå ââåäåíû íåêîòîðûå íîâûå ïîíÿòèÿ è äàíû íåîáõîäèìûå óñëîâèÿ äëÿ îïòèìàëüíîãî ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è.