Attestation committee
Accreditation committee
Expert committee
Dispositions, instructions
Normative acts
MANPOWER TRAINING
Nomenclature
Institutions
Scientific councils
Seminars
Theses		 Scientific advisers
Scientists
Doctoral students
Postdoctoral students
CNAA logo

 română | русский | english


Transitively orientable graphs


Author: Grigoriu Nicolae
Degree:doctor of physics and mathematics
Speciality: 01.01.09 - Mathematical cybernetics and operation research
Year:2016
Scientific adviser: Sergiu Cataranciuc
doctor habilitat, professor, Moldova State University
Institution: Moldova State University

Status

The thesis was presented on the 13 April, 2016
Approved by NCAA on the 3 June, 2016

Abstract

Adobe PDF document – 1.27 Mb / in romanian

Thesis

CZU 519.83

Adobe PDF document 2.13 Mb / in romanian
143 pages

Keywords

transitively orientable graph, stable subgraph, non-triangulated chain, graph factor, transitive orientation, comparability graph.

Summary

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.

The implementation of the scientific results: The results might provide a basis for selecting the themes for students. The developed algorithms are implemented as a software in Javascript programming language.