1-фактор

Cтраница 2

Пусть п 3 и я-связный граф G не имеет 1-факторов. [16]

Если GC0 ( G), то граф G имеет 1-фактор. [17]

Хотя полные двудольные графы Кт п при тфп не имеют 1-факторов, графы Кп п 1-факторизуемы, как видно из следующего утверждения. [18]

Всякий двусвязный регулярный граф степени 3 может быть разложен на непересекающиеся 1-фактор и 2-фактор. [19]

То-гда граф G ( V, Н - Я) имеет 1-фактор. [20]

Байнеке и Пламмер [1] доказали, что каждый п-связный граф, имеющий 1-фактор, имеет по крайней мере п различных 1-факторов. [21]

Пусть граф О имеет 2-разбиение ( 11У) и Р - частичный 1-фактор графа О. [22]

Два 1-фактора блока. [23]

Предположим, что у графа G четное число вершин и нет 1-фактора. [24]

Это отношение комплементарности не имеет места, если мы ограничиваемся случаем 1-факторов. [25]

Тогда Fi f ( k - 2) и F является 1-фактором графа G. Отсюда следует, что G имеет по крайней мере k - f ( k - 2) 1-факторов. [26]

Во-вторых, можно обобщить методы, разработанные для решения задачи об 1-факторе. В-третьих, существует возможность получить более общие результаты, которые дополнительного смысла в частном случае 1-факторов не приобретают. [27]

Здесь Я состоит из ребер, принадлежащих г - 2k - 1 1-факторам на Bi. [28]

Из теоремы об / - факторе следует, что граф О имеет либо 1-фактор, либо / - барьер В ( 5, Т), но не то и другое одновременно. Если существует / - барьер В, то мы можем считать в силу теоремы VII. Тогда всякая нечетная компонента / - барьера В содержит нечетное число вершин. Обратно, если для некоторого 5 выполняется неравенство 5 / 1 ( 5), то очевидно, что пара ( 5 0) есть / - барьер графа С. [29]

Показать, что всякий 4-связный 5-однородный) граф с четным числом вершин имеет 1-фактор. [30]

Страницы: 1 2 3 4