Полідерева зі слабко зв’язними реберними орграфами

Нехай 𝐷 = (𝑉 (𝐷), 𝐴(𝐷)) — орграф. Його реберним орграфом називатимемо орграф 𝐿(𝐷) з множиною вершин 𝑉 (𝐿(𝐷)) = 𝐴(𝐷) i множиною дуг 𝐴(𝐿(𝐷)) = {(𝛼, 𝛽) ∈ (𝐴(𝐷))2 : 𝛼 = (𝑎, 𝑏), 𝛽 = (𝑏, 𝑐), де 𝑎, 𝑏, 𝑐 ∈ 𝑉 (𝐷)}. Основну iнформацiю про ребернi орграфи можна знайти в оглядi [1]. Для довiльного орграфа 𝐷 вiдповiдний йому неорiєнтований граф позначатимемо як [𝐷]. Якщо [𝐷] зв’язний, то 𝐷 називається слабко зв’язним, або слабким. Полiдеревом називається орграф, який отримується з неорiєнтованого дерева деякою орiєнтацiєю його ребер. Витоком називається вершина орграфа, в яку не входить жодна дуга. Вiдповiдно стоком називається вершина, з якої не виходить жодна дуга. Якщо в полiдеревi точно один витiк (стiк), називатимемо його коренем полiдерева, а саме полiдерево — вихiдним (вхiдним). Множину витокiв полiдерева 𝑇 позначатимемо 𝑆𝑜(𝑇), а стокiв — 𝑆𝑖(𝑇). Для дерева 𝑋 множину його кiнцевих вершин, себто вершин ступеня 1, позначатимемо як Leaf(𝑋). Для неорiєнтованого графа 𝐺 число 𝑀1(𝐺) = ∑︀ 𝑥∈𝑉 (𝐺) 𝑑 2 𝐺(𝑥) називається першим заґребським iндексом 𝐺. Твердження 1. Нехай 𝑇 є полiдерево з 𝑛 ≥ 2 вершинами. Тодi 𝐿(𝑇) мiстить ∑︁ 𝑢∈𝑆𝑖(𝑇)∪𝑆𝑜(𝑇) (𝑑[𝑇] (𝑢) − 1) + 1. компонент слабкої зв’язности [2]. Твердження 2. Реберний орграф 𝐿(𝑇) полiдерева 𝑇 слабкий тодi й тiльки тодi, коли кожен витiк i стiк у 𝑇 є кiнцева вершина в [𝑇]. Твердження 3. Нехай 𝑋 є дерево таке, що |𝑉 (𝑋)| ≥ 2 та Leaf(𝑋) = 𝐴 ⊔ 𝐵 є розбиття його кiнцевих вершин. Тодi iснує орiєнтацiя 𝑇 дерева 𝑋 така, що 𝐴 є множина витокiв i 𝐵 є множина стокiв, тодi й тiльки тодi, коли 𝐴 й 𝐵 непорожнi. Теорема 1. Нехай 𝑋 є дерево з 𝑛 ≥ 3 вершинами. Тодi кiлькiсть орiєнтацiй 𝑇 зо слабкими реберними орграфами задається формулою 2 · ∏︁ 𝑢∈𝑉 (𝑋)∖ Leaf(𝑋) (2𝑑𝑋(𝑢)−1 − 1). Твердження 4. Нехай 𝑇 є вхiдне (або вихiдне) дерево з 𝑛 вершинами, 𝑢 - корiнь 𝑇. Тодi |𝐴(𝐿(𝑇))| = 𝑛 − 1 − 𝑑[𝑇] (𝑢). Наступний результат вiдповiдає на питання: яка найменша можлива кiлькiсть дуг серед усiх орiєнтацiй дерева 𝑋 зо слабкими реберними орграфами? Теорема 2. Нехай 𝑋 є дерево на 𝑛 ≥ 2 вершин. Тодi найменша кiлькiсть дуг в 𝐿(𝑇) серед орiєнтацiй 𝑇 дерева 𝑋 iз слабким 𝐿(𝑇) дорiвнює 𝑛 − 2. Знайдiмо тепер найбiльшу й середню кiлькiстю дуг у ребернiм орграфi серед усiх орiєнтацiй. Твердження 5. Нехай 𝑇 є та орiєнтацiя дерева 𝑋, що максимiзує кiлькiсть дуг в 𝐿(𝑇). Тодi 𝐿(𝑇) слабкий. Теорема 3. Нехай 𝑋 дерево. Тодi найбiльша кiлькiсть дуг в 𝐿(𝑇) серед усiх орiєнтацiй 𝑇 дерева 𝑋 дорiвнює ∑︁ 𝑢∈𝑉 (𝑋) ⌊︂ 𝑑𝑋(𝑢) 2 ⌋︂ · ⌈︂ 𝑑𝑋(𝑢) 2 ⌉︂ . Твердження 6. Нехай 𝑋 є дерево на 𝑛 вершин. Тодi середня кiлькiсть дуг в 𝐿(𝑇) серед орiєнтацiй 𝑇 дерева 𝑋 дорiвнює 𝑀1(𝑋) 4 − 𝑛 − 1 2 . Наслiдок 1. Нехай 𝑋 є дерево на 𝑛 вершин. Тодi середня кiлькiсть дуг в 𝐿(𝑇) серед орiєнтацiй 𝑇 дерева 𝑋 не менша вiд 𝑛−2 2 i не бiльша вiд (𝑛−1)(𝑛−2) 4 .