Математическая энциклопедия

ФАКТОРИЗАЦИЯ

в теории графов - разложениеграфана непересекающиеся по ребрам остовные подграфы специального вида. В общем случае фактор есть остовный подграф, обладающий заданным свойством. Примером такого свойства является регулярность подграфа. Регулярный остовный подграф степени kназ. k-фактором; 1-фактор наз. также совершенным паросочетанием. Граф наз.k-факторизуемым, если он может быть представлен как объединение своих непересекающихся по ребрам k-факторов.
В теории графов рассматриваются вопросы о существовании факторов того или иного вида в произвольном графе, о числе факторов, о возможности Ф.данного типа для различных классов графов. Известно, напр., что полный граф с четным числом вершин и полныйграф двудольныйс одинаковым числом вершин в каждой доле являются 1-факторизуемыми. Связный граф является 2-факторизуемым тогда и только тогда, когда он является регулярным графом четной степени. Граф Gимеет 1-фактор тогда и только тогда, когда число его вершин четно и не существует такого подмножества вершинU,что число компонент связности с нечетным числом вершин графаG - U,получающегося из G удалением вершин множестваU,превышает |U|.Всякий двусвязвый регулярный граф степени 3 может быть разложен на непересекающиеся 1-фактор и 2-фактор.
Примерами нерегулярных факторов являются ос-товныедеревьяи леса, остовные плоские подграфы (см.Графа укладка)и т. п. С разложением графа на остовные леса связана числовая характеристика, называемая древесностью,- это наименьшее число непересекающихся по ребрам остовных лесов, объединением к-рых является граф. Древесность произвольного графа Gравна


гдеgk-наибольшее число ребер в k-вершинныx подграфах графаG.

Лит.:[1] Xарари Ф., Теория графов, пер. с англ., М., 1973.
А. А. Сапоженко.

  1. факторизация—Начальная форма Факторизация единственное число женский род именительный падеж неодушевленное...Морфологический разбор существительных
  2. факторизация—факторизация факторизация и...Орфографический словарь
  3. факторизация—факторландыру...Орысша-қазақша «Математика» терминологиялық сөздік
  4. факторизация—Орфографическая запись слова факторизация Ударение в слове факторизация Деление слова на слоги перенос слова факторизация Фонетическая транскрипция слова факторизация [ф...Полный фонетический разбор слов
  5. факторизация—факторизация и...Русский орфографический словарь
  6. факторизация—factorization факторизация ж.u мат.ufactorization...Русско-английский политехнический словарь
  7. факторизация—ж.factorization factoring...Русско-английский психологический словарь
  8. факторизация—f....Русско-английский словарь математических терминов
  9. факторизация—factorization...Русско-английский словарь по машиностроению
  10. факторизация—ж. факторизация группы факторизация матрицы факторизация полюсов факторизация функции...Русско-английский словарь по физике
  11. факторизация—factorization вчт....Русско-английский словарь по электронике
  12. факторизация—factorisation factorization...Русско-английский технический словарь
  13. факторизация—фактарызаuцыя цыi...Русско-белорусский словарь математических, физических и технических терминов
  14. факторизация—фактарызацыя цыi...Русско-белорусский физико-математический словарь
  15. факторизация—factorizacin прогр....Русско-испанский экономический словарь
  16. факторизация—ж. матем. fattorizzazione f...Русско-итальянский политехнический словарь
  17. факторизация—...Русско-китайский словарь
  18. факторизация—матем. факторизаця...Русско-украинский политехнический словарь
  19. факторизация—Ударение в слове факторизацияУдарение падает на букву аБезударные гласные в слове факторизация...Ударение и правописание
  20. факторизация—Rzeczownik факторизация f Informatyczny faktoryzacja f...Универсальный русско-польский словарь
  21. факторизация—Фриц Фрикция Фрик Фриз Фри Фракция Фракия Фрак Фраза Фра Фотка Фот Фортка Форт Форзац Фора Фок Фита Фира Фикция Физия Физиократ Физико Физик Физиатр Физа Фиат Фиакр Фация...Электронный словарь анаграмм русского языка