Факторизация

143

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

Значения в других словарях
Факторизационная Теорема

критерий факторизации,- теорема теории статистич. Оценивания, указывающая необходимое и достаточное условия того, чтобы статистика Тбыла достаточной для семейства вероятностных распределений Пусть X- случайный вектор, принимающий значения в выборочном пространстве причем семейство вероятностных распределений доминировано нек-рой мерой и пусть Далее, пусть Т=Т(X)-статистика, построенная по вектору наблюдений Xи отображающая измеримое пространство в измеримое пространство В этих условия..

Факторизационные Тождества

в теории случайных блужданий - система многопараметрич. Тождеств, устанавливающих связи между различными характеристиками случайного блуждания. В качестве характеристик здесь фигурируют т. Н. Граничные функционалы - случайные величины, связанные с достижением блужданием нек-рых границ, напр. Супремум блуждания, момент первого достижения этого супремума, величина первого перескока через уровень и т. Д. Название Ф. Т. Связано с тем, что их получение основано на факторизации - представлении функ..

Факторкатегория

конструкция, аналогичная конструкции фактормножества или факторалгебры. Пусть -произвольная категория, и в классе морфизмов Моrзадано отношение эквивалентности ~, удовлетворяющее следующим условиям. 1) если то начала и концы морфизмов и совпадают. 2) если п произведение определено, то Через обозначается класс эквивалентности морфизма Фактор категориeй категории по отношению ~ наз. Категория (обозначаемая у к-рой те же объекты, что и у а для любой пары объектов A, В множество морфизмов Н..

Факторкольцо

кольца Rпо идеалу I- факторгруппа аддитивной группы кольца Rпо подгруппе I с умножением (a + I)(b + I) = ab + I. Ф. Оказывается кольцом и обозначается R/I. Отображение где является сюръективным кольцевым гомоморфизмом, к-рый наз. Естественным (ср. Алгебраическая система). Важнейший пример Ф. Кольцо вычетов по модулю п- Ф. Кольца целых чисел по идеалу Элементами кольца можно считать числа {0, 1, ..., n-1}, где сумма и произведение определяются как остатки от деления обычных суммы и произ..

Дополнительный поиск Факторизация Факторизация

Добавить комментарий
Комментарии
Комментариев пока нет

На нашем сайте Вы найдете значение "Факторизация" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Факторизация, различные варианты толкований, скрытый смысл.

Первая буква "Ф". Общая длина 12 символа