Відображення між графами, що зберігають ребра назад

Гомоморфiзмом графiв 𝐺 i 𝐻 називається вiдображення 𝑓 : 𝑉 (𝐺) −→ 𝑉 (𝐻) мiж множинами їхнiх вершин, яке зберiгає ребра: ∀𝑒 ∈ 𝐸(𝐺) маємо 𝑓(𝑒) ∈ 𝐸(𝐻). У роботi [1] розглядають дуальне поняття, когомоморфiзм, а саме, вiдображення у якому прообразом кожного ребра iз образу графа 𝐺 є ребро у оригiнальному графi. Природнiм звуженням цього класу вiдображень є клас вiдображень, якi зберiгають назад усi ребра, а не тiльки ребра з образу. Ми називаємо їх BEP (backward edge-preserving). Очевидно, що якщо вiдображення є BEP, то воно мусить бути когомоморфiзмом, але не навпаки. Для вiдображення 𝑓 : 𝑋 −→ 𝑌 та числа 𝑘 ∈ N ∪ {0}, позначатимемо Im𝑘 𝑓 = {𝑦 ∈ 𝑌 : |𝑓 −1 (𝑦)| = 𝑘}. BEP вiдображення мiж графами описуються наступним чином. Теорема 1. Вiдображення 𝑓 : 𝑉 (𝐺) → 𝑉 (𝐻) мiж двома графами 𝐺 та 𝐻 є BEP тодi i тiльки тодi, коли виконуються три умови: (1) Кожна вершина 𝑦 ∈ Im 𝑓, для якої |𝑓 −1 (𝑦)| ≥ 3, є iзольованою вершиною у графi 𝐻; (2) Для кожної зв’язної компоненти 𝐻′ графа 𝐻, такої що 𝑉 (𝐻′ ) ∩ Im1 𝑓 ̸= ∅, маємо 𝑉 (𝐻′ ) ⊂ Im1 𝑓, i звуження 𝑓 −1 на 𝑉 (𝐻′ ) є гомоморфiзмом з 𝐻′ у 𝐺; (3) Для кожної зв’язної компоненти 𝐻′ графа 𝐻, такої що 𝑉 (𝐻′ ) ∩ Im1 𝑓 = ∅ та |𝑉 (𝐻′ )| ≥ 2, множина 𝑉 (𝐻′ ) ∩ Im2 𝑓 є незалежним вершинним покриттям у 𝐻′ , i для всiх 𝑦 ∈ 𝑉 (𝐻′ ) ∩ Im2 𝑓 маємо 𝑓 −1 (𝑦) ∈ 𝐸(𝐺). У випадку коли граф 𝐻 є зв’язним, це твердження можна уточнити. Наслiдок 1. Нехай 𝐺 — граф, а 𝐻 — зв’язний граф з принаймнi двома вершинами. У такому разi вiдображення 𝑓 : 𝑉 (𝐺) → 𝑉 (𝐻) є BEP тодi i тiльки тодi, коли виконується одна з наступних умов: (1) Образ Im 𝑓 є незалежним вершинним покриттям у 𝐻, i для всiх 𝑦 ∈ Im 𝑓 маємо 𝑓 −1 (𝑦) ∈ 𝐸(𝐺); (2) Вiдображення 𝑓 бiєкцiя, причому 𝑓 −1 є гомоморфiзмом з 𝐻 у 𝐺. Зауваження 1. Нехай 𝑓 : 𝑉 (𝐺) → 𝑉 (𝐻) — це BEP-вiдображення, яке задовольняє першу умову з Наслiдку 1. Тодi множина ребер {𝑓 −1 (𝑦): 𝑦 ∈ Im 𝑓} є досконалим паросполученням у графi 𝐺. Крiм того, оскiльки образ Im 𝑓 є незалежним покриттям вершин у 𝐻, граф 𝐻 обов’язково має бути двочастковим.