GRAFURI TRANZITIV ORIENTABILE

Abstract

Caracterizarea structurală a grafurilor tranzitiv orientabile și elaborarea în baza acesteia a algoritmilor de construire a orientărilor tranzitive pentru grafurile neorientate cu restricții asupra muchiilor. Obiective: determinarea rolului lanțurilor netriangulate în construirea orientărilor tranzitive a grafurilor; examinarea proprietăților subgrafurilor B-stabile și rolul acestora la construirea grafurilor factor; studierea șirului complet de grafuri factor pentru descrierea problemei orientărilor tranzitive ale unui graf neorientat; determinarea formulei recurente de calcul a numărului de orientări tranzitive ale grafului; elaborarea algoritmilor pentru construirea orientărilor tranzitive cu restricții asupra muchiilor orientabile.

Структурная характеристика транзитивно ориентируемыx графов и разработка алгоритмов для построения транзитивной ориентаций с ограничениями по дугам графа; определения роли нетриангулированных цепей в построении транзитивных ориентаций; изучение свойств Б-стабильных подграфов для построения графов фактор, изучение полного ряда графов фактор для описания проблемы транзитивных ориентаций неориентированного графа; определения рекурсивной формулы для подсчета количество транзитивных ориентаций графа.

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.