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


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

в теории графов - разложение графа на непересекающиеся по ребрам остовные подграфы специального вида. В общем случае фактор есть остовный подграф, обладающий заданным свойством. Примером такого свойства является регулярность подграфа. Регулярный остовный подграф степени 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.
А. А. Сапоженко.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ФАКТОРИЗАЦИЯ" в других словарях:

  • Факторизация — Эта статья  о математической концепции. Другие значения термина в заглавии статьи см. на Фактор. Иллюстрация полинома x2 + …   Википедия

  • факторизация — факториз ация, и …   Русский орфографический словарь

  • Факторизация Ленстры с помощью эллиптических кривых — (англ. elliptic curve factorization method, сокр. ECM)  алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после… …   Википедия

  • Факторизация с помощью эллиптических кривых — (англ. elliptic curve method, сокр. ECM)  алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего… …   Википедия

  • факторизация методом квадратичного решета — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN quadratic sieve factoring …   Справочник технического переводчика

  • Факторизация целых чисел — Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики. В отличие от… …   Википедия

  • Рекорды факторизации целых чисел — Факторизация простого числа это процесс определения простых чисел, являющихся делителями данного числа. Числа общего вида Первой очень большой распределенной факторизацией была факторизация RSA 129. Это число было разложено между сентябрем 1993… …   Википедия

  • RSA-числа — это множество больших полупростых чисел (чисел, представимых в виде произведения двух простых чисел), используемых в конкурсе RSA Factoring Challenge. Конкурс заключался в нахождении простых множителей предложенных чисел, но в 2007 году был… …   Википедия

  • Отношение эквивалентности — У этого термина существуют и другие значения, см. Эквивалентность. Отношение эквивалентности ( ) на множестве   это бинарное отношение, для которого выполнены следующие условия: Рефлексивность: для любого в , Симметричность: если …   Википедия

  • Гохберг, Израиль Цудикович — Израиль Цудикович Гохберг Дата рождения: 23 августа 1928(1928 08 23) …   Википедия

Книги

Другие книги по запросу «ФАКТОРИЗАЦИЯ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.