Фактор - граф
Cтраница 1
 |
Структурный граф и соответствующие ему скоростные графы Коутса и Мэзона, К 45 - 02 - 35. [1] |
Фактор графа и - [ on, соз, ws ], получаемого исключением из Га вершин соз, 0) 4, MS, определяется тремя петлями. [2]
Фактором графа G называется остовный подграф графа G, не являющийся вполне несвязным. Будем говорить, что граф G есть сумма г) факторов G -, если графы G, не имеют попарно общих ре бер, a G - их объединение. Такое разложение называется факторизацией графа G. Если граф G представляет собой сумму я-факто - ров, то их объединение называется п-факторизацией, а сам граф G называется п-факторизуемым. Если не оговаривается противное, то результаты этой главы или содержатся, или легко вытекают из теорем, представленных в монографии Кенига [ 2, стр. [3]
Проблема существования факторов графа очень старая. Еще в 1891 г. Петерсен [5] показал, что каждый кубический граф, не содержащий мостов, имеет I-фактор. [4]
Таким образом, фактор графа составляется из непересекающихся контуров таких, что в совокупности они содержат все вершины графа и каждая встречается один раз. Гамильтонов контур представляет собой фактор. [5]
Метод латинской композиции позволяет перечислить факторы графа, отыскивая элементарные контуры. [6]
ДО вершины MI через из и фактор графа Гт - [ он, Шз, coi ], состоящий из трех контуров-петель. [7]
Таким образом, для того чтобы найти факторы графа скоростей rffl, необходимо достроить структурное число графа Гт - сое, у которого удалена вершина 0, раскрыть его и выписать соответствующие подстановки. [8]
Предположим, что F - это / - фактор графа G. [9]
 |
Граф матрицы ( а и его факторы ( б. [10] |
Таким образом, задача топологического раскрытия определителя сводится к перебору всех факторов соответствующего матричного графа. [11]
Оказывается & - й член определителя в точности равен весу k - ro фактора графа. [12]
Полученные отображения соответствуют имеющимся в Гщ пути от вершины юе до соя и двум факторам графа Гщ - [ йе и5 ] - Этот факт не является случайным, он становится очевидным, если учесть, что удаление дуг, исходящих из вершины е 5, разрывает контур, проходящий через эту вершину. [13]
Если каждая вершина графа входит в один и только в один контур некоторого множества контуров, то такое множество называется фактором графа. [14]
В частном случае, когда при образовании обобщенных чисел учитывают только индексы адресов т п I, получают контурные числа, столбцы которых соответствуют факторам матричного графа. [15]
Страницы: 1 2