Двудольный граф

Cтраница 2

Для двудольных графов эти два свойства эквивалентны, что дает хорошую характеризацию обоих свойств. В случае недвудольных графов эти свойства не эквивалентны и поэтому, чтобы получить для каждого свойства хорошую характеризацию, нужны два отдельных результата. [16]

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

Модель двудольного графа в книге использована при выборе товарного ассортимента. [18]

Для двудольного графа G с дефицитом def ( G) О величина cr ( G) есть наибольшее целое число s, удовлетворяющее следующему условию для каждой вершины х G А: если мы добавим s новых вершин в множество А и соединим их с вершинами в Г ( х), то полученный в результате такой операции двудольный граф имеет неотрицательный избыток. [19]

Под двудольным графом мы понимаем граф, у которого вершины разделены на непересекающиеся множества А и В и каждое ребро соединяет вершину из Л с вершиной из В. [20]

Гиперграф ( а и его к лшгово представление ( б. [21]

В двудольном графе ( рис. 1.5 6) вершины 6 и 3 являются сочленениями графа. [22]

Так как двудольный граф не обязательно связен, а существование разрезов, по определению, требует связности, ответ-нет. Однако справедливо, что связный граф является двудольным тогда и только тогда, когда совокупность его ребер образует разрез. [23]

Значит, двудольный граф имеет совершенное 2-паросочетание тогда и только тогда, когда у него есть совершенное паросочетание. [24]

Определение 6.2. Двудольный граф СЫ ( А В Е назовем магистральным, если в результате удаления в нем всех висячих ребер полученный граф будет состоять из простой цепи и / или изолированных вершин. Здесь висячим считается ребро, инцидентное висячей вершине. Обработку графа G, при которой каждая вершина просматривается однократно, будем называть магистральной. Обработка магистральных двудольных графов характеризуется однократным просмотром каждой вершины. Заметим, в частности, что ребро и звездный граф, как связные компоненты графов, отражающих соответственно взаимосвязи типов 1: 1 и l: N, также являются магистральными. [25]

Пусть задан конечный ориентированный двудольный граф Г: А GI... Каждой вершине aft поставим в соответствие функции uk ( t), gk ( О, каждой вершине bt - функцию fi ( t, u) ( n) - переменной t и и ( и... [26]

В теории двудольных графов фундаментальную роль играет теорема Кенига, которую здесь мы приведем в матричной интерпретации. [27]

Важное свойство двудольных графов: все циклы имеют четную длину. Заметим, что здесь нуль считается четным числом, так что к двудольным графам относятся и деревья. [28]

В случае двудольных графов в работе [100] для оценки К была использована формула Я Sp ( ( BTB) - 1 / 2BTB), в которой матрица В описывает отношение инцидентности для вершин подмножеств У. Матрица ( 5TJ5) - 1 / 2 раскладывалась в степенной ряд по степеням матрицы С Е - BTB / f, где параметр j подбирался таким образом, чтобы собственные значения матрицы С по модулю не превосходили единицы. [29]

Обозначим вершины двудольного графа, отвечающие веществам Z -, a Rs - вершины, отвечающие реакциям. [30]

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