1-фактор - Большая Энциклопедия Нефти и Газа, статья, страница 3
Самая большая проблема в бедности - то, что это отнимает все твое время. Законы Мерфи (еще...)

1-фактор

Cтраница 3


Здесь и далее имеются в виду совершенные паросочетания в терми нологии Бержа, или 1-факторы в терминологии Харари.  [31]

Нелегко выяснить, 1-факторизуем ли данный граф, или хотя бы установить существование какого-нибудь 1-фактора. Байнеке и Пламмер [ 11 показали, однако, что многие графы либо вообще не имеют 1-факторов, либо у них число 1-факторов не меньше двух.  [32]

33 Два 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]

41 Два 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