CLASE DE SUBGRAFURI STABILE ÎN ORIENTAREA TRANZITIVĂ A GRAFURILOR

Abstract

În articol sunt analizate clasele de subgrafuri stabile, folosite la caracterizarea grafurilor tranzitiv orientabile și la studierea proprietăţilor acestora. Subgrafurile stabile reprezintă un suport în construirea orientării tranzitive a unui graf, precum şi pentru determinarea numărului acestora. De asemenea, sunt prezentate condiţiile necesare şi suficiente pentru ca un graf să fie tranzitiv orientabil.In the article there are analyzed the classes of the stable subgraphs, used for characterization of transitively orientable graphs and their properties. The subgraphs that we describe in this paper are a support for the constructions of the transitiveorientation of the graph, as well as the formula for the number of transitive orientations in a graph. In addition, we present necessary and sufficient conditions for a graph to be transitively orientable.