SUBGRAFURILE B-STABILE ÎN ORIENTAREA TRANZITIVĂ A GRAFURILOR

Abstract

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 𝐺𝐺.