1-фактор
Cтраница 3
Здесь и далее имеются в виду совершенные паросочетания в терми нологии Бержа, или 1-факторы в терминологии Харари. [31]
Нелегко выяснить, 1-факторизуем ли данный граф, или хотя бы установить существование какого-нибудь 1-фактора. Байнеке и Пламмер [ 11 показали, однако, что многие графы либо вообще не имеют 1-факторов, либо у них число 1-факторов не меньше двух. [32]
 |
Два 1-фактора блока. [33] |
Граф G на рис. 9.2 представляет собой блок, у которого в точности два 1-фактора, причем они имеют одно общее ребро. [34]
Равенство k 5 выполняется, поскольку ребро содержит 2 вершины и содержится в трех 1-факторах, так как 1-факторизация содержит пять 1-факторов. [35]
Рассмотрим теперь следующую структуру 3): точками служат вершины ( элементы множества А) и 1-факторы А; блоками являются ребра и 1-факторизации А. Инцидентность между вершинами и ребрами, а также между 1-факторами и 1-факториза-циями устанавливается по включению, тогда как инцидентность между ребрами и 1-факторами - по обратному включению. [36]
Граф G G - Vi, V2 ( n - 2) - связен и имеет 1-фактор F - Е, так что он имеет по крайней мере f ( n - 2) 1-факторов. Добавляя ребро Е к 1-фактору графа G, получаем 1-фактор графа G. [37]
Очевидно, что в случае, когда f ( v) 1 для всех вершин v, 1-факторы и совершенные 1-паросочетания являются одними и теми же образованиями. [38]
Если 2-связный граф G имеет l - фактор, то он имеет по крайней мере еще один 1-фактор. [39]
Нам нужно только указать разбиение множества X ребер графа / С2 на ( 2л - 1) 1-факторов. [40]
 |
Два 1-фактора блока. [41] |
Теорема 9.3. Если двусвязный граф имеет - фактор, то он имеет по крайней мере два различных 1-фактора. [42]
Каждый ( 2т I) - регулярный граф G, у которого K ( G) 2m, имеет 1-фактор, содержащий произвольно выбранное ребро. [43]
Используя теорему 9.4 ( Татт), показать, что граф, изображенный на рис. 9.5, не имеет 1-фактора. [44]
Удобно ввести отношение между ребрами А и ребрами X: ab - ху, если ab является ребром в 1-факторе с пометкой ху. [45]
Страницы: 1 2 3 4