Факторизація
Теоретично графів — розкладання графа на остовні підграфи спеціального виду, що не перетинаються по ребрах. У загальному випадку фактор є кістяковий подграф, що володіє заданою властивістю. Прикладом такої властивості є регулярність підграфії. Регулярний кістяковий подграф ступеня kназ. k-фактором; 1-фактор зв. також досконалим паросочетанням. Граф зв. k- факторизируемым, якщо може бути представлений як об'єднання своїх непересекающихся по ребрах k-факторов. Теоретично графів розглядаються питання існування чинників тієї чи іншої виду в довільному графі, про кількість чинників, про можливості Ф. даного типу для різних класів графів. Відомо, напр., що повний граф з парним числом вершин і повний дводольний граф з однаковим числом вершин у кожній частці є 1-факторизуемими. Зв'язковий граф є 2-факторизуемим тоді і лише тоді, коли він є регулярним графом парного ступеня. Граф G має 1-фактор тоді і тільки тоді, коли число його вершин парне і не існує такого підмножини вершин U, що число компонент зв'язності з непарним числом вершин графа G - U, що виходить з G видаленням вершин множини U, перевищує U. Будь-який двозв'язковий регулярний граф ступеня 3 може бути розкладений на 1-фактор і 2-фактор, що не перетинаються. Прикладами нерегулярних факторів є основні дерева і ліси, остовні плоскі підграфи (див. Графа укладання ) і т. п. З розкладанням графа на остовні ліси пов'язана числова характеристика, звана деревністю, - це найменша кількість остовних лісів, що не перетинаються по ребрах, об'єднанням до -Рих є граф. Деревність довільного графа G дорівнює де gk - найбільше число ребер в k-вершинних підграфах графа G. [1] Xарарі Ф., Теорія графів, пров. з англ., М., 1973. А. А. Сапоженка.