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.