Facultatea de Matematică şi Informatică / Faculty of Methematics and Informatics
Permanent URI for this communityhttps://msuir.usm.md/handle/123456789/12
Browse
3 results
Search Results
Item SUBGRAFURILE B-STABILE ÎN ORIENTAREA TRANZITIVĂ A GRAFURILOR(2015) Grigoriu, NicolaeSe formulează rezultate noi ce țin de studierea problemei orientării tranzitive a grafurilor neorientate. Amintim că un graf 𝐺𝐺⃗ = 𝑋𝑋; 𝑈𝑈 este tranzitiv orientat dacă pentru oricare trei vârfuri 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 ∈ 𝑋𝑋 este satisfăcută relația de tranzitivitate: [𝑥𝑥, 𝑦𝑦] ∈ 𝑈𝑈 & [𝑦𝑦, 𝑧𝑧] ∈ 𝑈𝑈 ⇒ [𝑥𝑥, 𝑧𝑧] ∈ 𝑈𝑈 [3]. Graful neorientat 𝐺𝐺 = (𝑋𝑋; 𝑈𝑈) este tranzitiv orientabil dacă atribuind o anumită orientare muchiilor sale obținem un graf tranzitiv orientat. Un subgraf determinat de o mulțime de vârfuri 𝐴𝐴, se va numi subgraf stabil dacă pentru orice vârf 𝑥𝑥 ∈ 𝑋𝑋 ∖ 𝐴𝐴 se verifică una din relațiile: [𝑥𝑥, 𝑦𝑦] ∈ 𝑈𝑈𝐺𝐺 sau [𝑦𝑦, 𝑥𝑥] ∉ 𝑈𝑈𝐺𝐺, unde ∀𝑦𝑦 ∈ 𝐴𝐴.[1], [3] Definiția 1.[2] Subgraful stabil 𝐹𝐹 se numește subgraf B-stabil dacă pentru orice subgraf stabil 𝑀𝑀 din 𝐺𝐺 = (𝑋𝑋; 𝑈𝑈) are loc una din relațiile: 𝐹𝐹 ⊆ 𝑀𝑀 ∨ 𝐹𝐹 ∩ 𝑀𝑀 = ∅ Reieșind din definiția subgrafului B-stabil rezultă, că dacă 𝐺𝐺 nu conține subgraf stabil atunci acesta nu conține nici subgraf B-stabil. Lema 1. Dacă graful 𝐺𝐺 conține subgraf stabil, atunci 𝐺𝐺 conține și subgraf B- stabil. Teorema 1. Subgraful 𝐹𝐹 al grafului tranzitiv orientabil 𝐺𝐺 este B-stabil dacă și numai dacă orientarea tranzitivă 𝐹𝐹⃗ se construiește în mod independent de orientarea tranzitivă a întregului graf 𝐺𝐺.Item B-STABLE SUBGRAPHS IN UNDIRECTED GRAPHS(Valines SRL, 2004) Grigoriu, NicolaeIn this article special structures of stable subgraphs and some of their most important properties that will be necessary for calculation of the number of transitive orientations of an undirected graph are described.Item CLASE DE SUBGRAFURI STABILE ÎN ORIENTAREA TRANZITIVĂ A GRAFURILOR(CEP USM, 2015) Cataranciuc, Sergiu; Grigoriu, NicolaeÎ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.