StatusThe thesis was presented on the 13 April, 2016
Approved by NCAA on the 3 June, 2016
Abstract– 1.27 Mb / in romanian
2.13 Mb /
The thesis has been elaborated in Chisinau, Moldova State University, in 2016.
Thesis structure: The thesis is written in Romanian language and contains an introduction, three chapters, general conclusions and recommendations, a bibliography of 119 titles, 113 pages of main text. Obtained results were published in 14 scientific papers. The field of study: Graph theory
The aim of the research. Structural characterization of the transitively orientable graphs and elaboration of the algorithms for the transitive orientation construction based on these characterizations. Objectives: definition of the non-triangulates chains role in construction of the transitive orientations, examination of the B-stabile subgraph properties and their role in construction of the graphs factor, study of the complete sequence of the graphs factor for the transitive orientation problem, definition of a recurrence formula for calculation of the number of transitive orientations in a graph.
The scientific novelty and originality is reflected in the following: there was described a new class of the stable subgraphs and based on their properties there was defined the complete sequence of graphs factor, that are used for the solution of the transitive orientation of undirected graphs, as well for the problem of the counting the number of transitive orientations of a graph.
Important scientific problemsolved in the research consists in definition of a new class of stable subgraphs used for the study of the transitive orientation problem and structural characterization of the transitive orientable graphs, which leads to the obtaining of an efficient method for construction of transitive orientations of the graph and counting number of them.
The theoretical significance of the work is defined by the results which describe the structural characterization of transitive orientable subgraphs. It is proposed an efficient method of study of the transitive orientations based on a complete sequence of graphs factor.
The applicative value of the paper. There are proposed algorithms for construction of transitive orientations of an undirected graph, which completes the practical aspect of the studied problem for the solution of practical problems: testing of the source code of the programs, decomposition of the Petri nets, etc.