Browsing by Author "Grigoriu, Nicolae"

Now showing 1 - 4 of 4

B-STABLE SUBGRAPHS IN UNDIRECTED GRAPHS
(Valines SRL, 2004) Grigoriu, Nicolae
In 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.
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.
GRAFURI TRANZITIV ORIENTABILE
(2016) Grigoriu, Nicolae; Cataranciuc,Sergiu
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.
SUBGRAFURILE B-STABILE ÎN ORIENTAREA TRANZITIVĂ A GRAFURILOR
(2015) Grigoriu, Nicolae
Se 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 𝐺𝐺.