Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Օրիենտացված գրաֆների գագաթային համարակալում

Սարգսյան, Հովհաննես Էլֆիկի (2014) Օրիենտացված գրաֆների գագաթային համարակալում. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (698Kb) | Preview

    Abstract

    Կարգացուցակների տեսության խնդիրների կարևոր դաս են կազմում այսպես կոչված «Minimizing of total weighted completion time» (MTWTC) խնդիրները, որոնցում պահանջվում է տրված աշխատանքների մասնակի կարգավորված բազմության համար գտնել աշխատանքների կատարման այնպիսի պլանավորում, որը բավարարում է -ի վրա սահմանված մասնակի կարգին և մինիմիզացնում է աշխատանքների ավարտման պահերի որոշակի կշռված գումար: Հայտնի է, որ նշված խնդիրը համարժեք է ատենախոսությունում հետազոտվող կողմնորոշված գրաֆների մինիմալ գծային համարակալում ըստ երկարության (MINLAD) խնդրին1 և, հետևաբար, կամայական արդյունք, որը կիրառելի է MTWTC խնդիրների համար, վերաբերվում է նաև MINLAD խնդրին: Կողմնորոշված գրաֆների մինիմալ գծային համարակալում ըստ երկարության խնդրում տրված է կողմնորոշված գրաֆ, որի համար պահանջվում է գտնել նրա գագաթների բազմության այնպիսի ինյեկտիվ արտապատկերում թվային առանցքի ամբողջաթիվ աբսցիսներով կետերի բազմության վրա, որի դեպքում գրաֆի կողերի երկարությունների գումարը կլինի մինիմալ: Գրաֆների գագաթների գծային համարակալման խնդիրները լայնորեն կիրառվում են գերմեծ ինտեգրալային սխեմաների նախագծման փուլում: Սխեման կարելի է ներկայացնել գրաֆի տեսքով, որի գագաթները մոդուլներն են, իսկ կողերը` միացումները: Նախագծման տարբեր փուլերում առաջանում է անհրաժեշտություն մոդուլները տեղավորել հարթակի վրա այնպես, որ սխեմայի որոշակի պարամետրեր, ինչպիսիք են, օրինակ, ամենաերկար միացման երկարությունը, բոլոր միացումների երկարությունների գումարը և այլն, լինեն ինչքան հնարավոր է օպտիմալին մոտ: Գծային համարակալման խնդիրները նաև լայն կիրառություններ ունեն գրաֆների՝ մարդու աչքի համար ընկալելի ձևով պատկերման խնդիրներում, որտեղ նպատակներից մեկն է պատկերվող գրաֆի կողերի հատումների քանակի նվազեցումը: Հայտնի է նաև, որ երկկողմանի գրաֆների լայն դասի համար կողերի հատումների քանակի նվազեցումը համարժեք է գրաֆի գագաթների մինիմալ գծային համարակալում ըստ երկարության խնդրին: Диссертационная работа посвящена исследованию задачи минимального линейного размещения по длине ориентированных графов в классе транзитивно ориентированных графов. Эта задача тесно связана с одной из известных важных задач теории расписаний – задачи составления расписания выполнения работ из заданного частично упорядоченного множества работ при необходимости минимизации суммы взвешенных моментов их окончания. Большое практическое значение задача имеет как для случая ориентированных графов, так и для случая неоринтированниых графов. Основное прикладное значение задачи проявляется в технологических аспектах проектирования сверхбольших интегральных схем. Известно, что в задачах математического моделирования технологических процессов проектирования сверхбольших интегральных схем интегральную схему представляют в виде графа, вершины которого соответствуют модулям, а ребра соединениям. На различных этапах проектирования интегральной схемы возникает необходимость оптимизации различных параметров схемы, например, длины самого длинного соединения, суммы длин всех соединений и т.д. Из других практических применений можно отметить задачи построения хорошо воспринимаемых глазом человека изображений графов, которые для некоторых классов графов эквивалентны задачам минимизации числа вневершинных пересечений ребер при представлении графов на плоскости. The dissertation is devoted to an investigation of the problem of minimum linear arrangement of directed graphs in the class of transitive oriented graphs. This problem is closely linked with the one of the well known and important problems of scheduling theory the problem of creation of a schedule of the execution of works from the given partially ordered set of works with the necessity of minimizing of the weighted sum of their completions. The problem has a valuable practical significance for the case of undirected graphs. The main applied significance of the problem is manifested in technological aspects of chip designing. It is known that in mathematical modeling of technological processes of chip designing a chip is usually represented as a graph, the vertices of which correspond to modules, and edges to connections. On different stages of chip designing the necessity arises to optimize different parameters of the chip, for example, the longest length of a connection, the sum of lengths of all connections and so on. Among other practical applications we can note problems of construction of eye wellperceivable pictures of graphs, which for some classes of graphs are equivalent to problems of minimizing of the number of edge intersections in graph representations on a plane. Problems of considered kind firstly were applied by Harper for a solution of problems of mistake minimizing in construction of mistakecorrecting codes (Harper, L. H. 1964, Optimal assignments of numbers to vertices.

    Item Type: Thesis (PhD)
    Additional Information: Нумерация вершин ориентированных графов. Numbering of vertices of directed graphs.
    Uncontrolled Keywords: Саргсян Оганнес, Sargsyan Hovhannes
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 09 Mar 2017 16:29
    Last Modified: 10 Mar 2017 10:15
    URI: http://etd.asj-oa.am/id/eprint/4255

    Actions (login required)

    View Item