НЕФТЬ-ГАЗ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
На главную >>


Теперь на нашем сайте можно за 5 минут создать свежий реферат или доклад

Скачать книгу целиком можно на сайте: www.nglib.ru.

Предложения в тексте с термином "Вид"

Любую булеву функцию можно представить в виде формулы над множеством связок {Л, V, ~1}.

(В действительности, становится иного вида матрица А(х)\) Но из приводимого ниже, принадлежащего Татту (1947), результата мы увидим, что матрица В(х)

Напомним, что каждый элемент в pf (A,(G)) имеет вид ±a,i1j1.

Из определения немедленно следует (это важно иметь в виду), что всегда справедливо неравенство |pf(As(G))| < Ф(С).

Кососимметрическая матрица, соответствующая получившейся ориентации, имеет вид

Кососимметрическая матрица смежности для этой ориентации имеет вид:

Многочлены, перечисляющие паросочетания 423 паросочетаний, имеет ряд примечательных свойств: m(G;*) = Чтобы обосновать такое название, запишем многочлен в виде: м где суммирование ведется по всем паросочетаниям М графа G и, как и прежде в этой книге, def(M) обозначает дефект паросочетания М.

Известно, что это числа вида 1^/dсоз(ттг/'(k + 1)), т = 1,.

Запишем производящий полином паросочетаний в виде

задаются рекуррентным соотношением вида: an+i = о„ + nan_i- Доказать, что g(G; 1) = an, n(G) = nan_!

15 представляет собой замечательный общий результат такого вида, из которого вытекает асимптотическая локальная нормальность распределения многих последовательностей, возникающих при рассмотрении специальных последовательностей графов.

представляя молекулу в виде неориентированного графа, в котором вершины соответствуют атомам, а ребра — химическим связям.

Чтобы упростить наш анализ, запишем данный алгоритм в более формальном виде.

Эти соображения мотивируют вид структуры данных, которые мы организуем следующим образом.

Описанный нами алгоритм (в том виде, в каком мы его представили) после каждого шага увеличения начинает работу на «пустом месте».

Значит, у1 является двойственным решением требуемого вида.

1, для графов общего вида экспоненциально велик.

Пусть G — двудольный граф с 2-разбиением (А, В) и со всеми ребрами вида аб, где а?

Имея в виду граф G, мы будем обозначать эти четыре множества соответственно как C(f, g), A(f, g), B(f, g) и D(f, g).

Чтобы проверить это неравенство, запишем его в виде

Этот набор чисел реализуем в виде набора степеней вершин простого графа тогда и только тогда, когда реализуем аналогичным образом набор чисел di-l,.

Доказанная нами лемма обеспечивает очень простой способ проверки реализуемости набора целых чисел в виде набора степеней вершин простого графа.

Как уже отмечалось в начале этого раздела, мы можем задаться следующим вопросом: «Реализуем ли заданный набор целых чисел в виде набора степеней вершин графа с определенными специальными свойствами?

» Здесь мы докажем один результат такого типа; другие подобные результаты сформулированы в виде упражнений.

Такая проблема была поставлена Эдмондсом под названием «задача о матчоиде» («Matchoid Problem») и Лоулером — в ином, но эквивалентном, виде под названием «задача о матроидном паросочетаний при разбиении множества на пары» («Matroid Parity Problem»).

Говоря о линейном полиматроиде, мы будем молчаливо подразумевать, что он задан нам в виде множества линейных подпространств линейного пространства над некоторым полем, причем каждое подпространство специфицируется одним из его базисов.

Будем говорить, что оракул «претворен в жизнь» знаменитой дельфийской прорицательницей Пифией и нашим любимым греческим героем Алгоритмосом, имея в виду, что существует полиномиальный по времени алгоритм отыскания числа паросочетания любого 2-полиматроида.

) восторжествует над ним, заявив, что 2-полиматроид, который она имела в виду, был на самом деле таким: ( 2\Х\, если \Х\ < k, /(*)=< 2Jt-l, ecjiK\X\ = k,X ^Х0, { 2k, если \Х\ = Х0 или \Х\ > k.

На этом пути задача минимизации субмодулярной функции / множества сводится к линейной программе следующего вида: максимизировать w • х при условиях: х > 0, х (Т) < /(Т) (для всех Т С 5).

Политоп этого вида часто называется полиматроидным политопом, или, коротко, полиматроидом.

Она может быть описана графом G, обладающим тремя видами ребер: «резисторы», «генераторы напряжения» и «генераторы тока».

Зафиксируем q независимых уравнений Кирхгофа вместе с q дополнительными уравнениями вида (11.

Из уравнений Кирхгофа для напряжений мы знаем, что напряжения можно представить в виде:

Подробности представляются читателю в виде ряда упражнений (11.

Задача о вершинном покрытии уже встречалась в этой книге в виде задачи линейного программирования (или, другими словами, линейной программы), двойственной задаче о паросочета-нии для двудольных графов, а также для некоторых других классов графов (см.

Однако эти графы имеют ряд важных структурных свойств, которые приводят к интересным следствиям для числа вершинного покрытия и в случае графов общего вида.

Теперь мы обобщим это определение на графы общего вида: полагаем о~(Х) = \Т(Х)\ — \Х\ для всех X С.

7, пытаясь найти описание политопа VP(G) в виде множества решений системы линейных неравенств.

В перефразированном виде оно гласит, что дополнение совершенного графа является тоже совершенным графом.

Эта ситуация может быть описана в общем виде следующим образом.

Де 523 г(Х) ранговая функция матроида X 62 г(Х,У) 278 ф симметрическая разность 41 cr(G) избыток графа G (общего вида) 554 избыток двудольного графа G 59 <г(х) 455 о-,- 444 дисперсия 431

3 представлен результат (не столь широко известный, как он этого заслуживает), гласящий, что всю информацию о потоках в графе можно эффективно хранить в виде дерева, которое строится по исходному графу за полиномиальное число шагов.

Можно спросить, к чему такие сложности, если на практике пропускные способности должны быть всегда представлены в виде рациональных чисел?

Например, если a — действительное алгебраическое число степени п, то числа из поля

Мы будем использовать потоко-эквивалентное дерево в таком виде, как оно представлено в разд.

Но [0, 1] х [0, 1] -Е есть объединение счетного числа множеств вида G х Н.

1, мы постараемся теперь найти размер наибольшего паросоче-тания для графа общего вида в случае, когда совершенного паросо-четания в нем нет.

Введем новый вид декомпозиции, которая называется колосковой декомпозицией.

Кроме того, мы покажем, как двудольный граф общего вида, обладающий совершенным паросочетанием, «собирается» из элементарных двудольных графов.

Читатель, хорошо знающий теорию графов, наверняка уже заметил, что подобная декомпозиция присутствует в следующем результате Уитни (1932): граф G 2-связен тогда и только тогда, когда его можно представить в виде: G = Р\ + PI + • • • + Рг, где Р\ — цикл, а каждое «слагаемое» Р,- (для г > 2) является простой цепью, соединяющей две различные вершины графа PI +.

К сожалению, не всегда удается получить декомпозицию такого графа в виде цепочки элементарных подграфов, каждый из которых строится из предыдущего путем добавления одной ости.

Одна из мер малости отражает тот факт, что минимальный граф не может содержать подграфы определенного вида.

7 мы сформулируем более общие задачи о паросочетаний в виде линейных программ.

Заметим, что число цепей вида (4), не больше чем г.

Ясно, что эта вершина не является в графе Gij ни изолированной, ни входящей в компоненту вида (2), ибо она инцидентна несовпадающим ребрам из паросочетаний F,- и FJ.

Итак, вершина v должна принадлежать такой компоненте графа Gij, которая является чередующейся цепью вида (4).

, принадлежащие одной и той же компоненте вида (4) графа Gij, причем это справедливо для всякой пары {l')j} С {1;2,3}.

2 это разложение можно записать в виде G[Gi U GI].

7, то исходными бикритическими строительными блоками-графами должны быть в точности блоки графа G*, (d) элементарные двудольные графы, используемые на последнем шаге этой конструкции при построении графа G, определяются однозначным образом в том смысле, что они должны быть графами вида G's, где S e P(G).

Колосковая декомпозиция графа G, начинающаяся с подграфа G', есть представление графа G в виде G = G' + PI +.

Каждый факторно-критический граф G может быть представлен в виде PQ + PI +.

Тогда G может быть представлен в виде PQ + Р\ +.

Мы называем граф G графом Халина, если его можно изобразить на плоскости в виде дерева Т, у которого степень каждой неконцевой вершины не меньше 3 и которое «окаймляется» циклом С, проходящим через концевые вершины дерева Т.

Подобно тому, как минимаксная теорема Кёнига для двудольных графов связывает паросочетания и покрытия, 2-паросочетания могут быть связаны с 2-покрытиями в случае графов общего вида.

Граф можно свести к графу такого вида, если исследовать, что происходит на ориентированных циклах.

Мы имеем в виду результаты Сеймора (1978) об упаковке 2-продуктовых разрезов и Линса (1981) об упаковке «корон».

Читателю следует иметь в виду, что число векторов, необходимых для порождения полиэдрального конуса, может быть экспоненциально большим относительно размерности и числа линейных неравенств, определяющих этот конус.

Точнее, если мы имеем и перечень векторов, порождающих конус, и совокупность линейных неравенств, определяющих тот же конус, то для доказательства принадлежности некоторого вектора данному выпуклому конусу достаточно представить этот вектор в виде неотрицательной комбинации заданных векторов.

Мы представляем вектор х в виде неотрицательной комбинации определяющих векторов, а затем доказываем, что эти определяющие векторы действительно содержатся в конусе.

Зная множество определяющих точек и систему линейных неравенств, мы имеем тем самым хорошую характеризацию политопа: если мы хотим показать, что некоторый вектор принадлежит политопу, то достаточно представить этот вектор в виде выпуклой комбинации определяющих точек; если же мы желаем доказать, что данный вектор не принадлежит политопу, то достаточно найти определяющее неравенство, которому этот вектор не удовлетворяет.

Данному утверждению эквивалентно следующее: неравенство является существенным для полноразмерного политопа, если оно справедливо для точек политопа1 и не может быть представлено в виде неотрицательной комбинации других достоверных неравенств.

Моцкин (1936) доказал, что всякий полиэдр можно представить в виде специальной суммы политопа и выпуклого полиэдрального конуса.

Как только набор определяющих точек и определяющих лучей найден, в нашем распоряжении оказывается эффективный способ обоснования принадлежности точки полиэдру: мы просто представляем ее в виде неотрицательной комбинации определяющих точек и лучей, причем коэффициенты, стоящие перед определяющими точками, должны давать в сумме 1.

Оказывается, что он, кроме того, легко представляется в виде последовательности простых манипуляций над столбцами матрицы, задающей полиэдр Р.

2) при |F(G)| ограничениях вида (7.

Соответствующая ему система неравенств вида (7.

Дать доказательства теоремы о максимальном потоке и минимальном разрезе и теоремы о целочисленном потоке, используя рассуждения такого же вида, как приведенные выше.

Сформулировать задачу о реберной раскраске двудольного графа в виде задачи целочисленного линейного программирования.

Это обстоятельство побуждает ввести еще два вида полиэдров.

Наиболее существенная часть этого утверждения (в которой устанавливается, что каждая грань в M(G) имеет описываемый ниже вид) является знаменитым результатом, полученным Эдмондсом (1965Ь).

Сначала покажем, что каждая грань политопа M(G) определяется неравенством указанного выше вида.

Пусть система неравенств имеет вид a, -x

Веря от выражения, стоящего в этом неравенстве слева, целую часть, мы приходим к неравенству вида (iii), соответствующему множеству 5.

Привести пример, показывающий, что теорема Визинга в данном выше виде для непростых графов не верна.

Напомним, что политоп дробных паросочетаний FM(G) графа G был определен как множество решений системы линейных неравенств следующего вида: z > О, (7.

Тогда точка w/1 является вершиной политопа FM(G) и каждая его вершина имеет такой вид.

Точка w/2 является единственной точкой политопа FM(G), максимизирующей такую линейную целевую функцию, коэффициенты которой имеют вид: се = we при we > О и се = — I при we = 0.

имеют вид а/2, где а — целое число).

Его базисность легко следует из того, что небазисные 2-паросочетания могут представлены в виде выпуклых комбинаций базисных 2-паросочетаний.

Тогда точка <р/1 является вершиной полиэдра FPC(G) и каждая его вершина имеет такой вид.

Рассмотрим совершенные паросочетания графа G, имеющие вид М/ U M,-+i U.




Главный редактор проекта: Мавлютов Р.Р.
oglib@mail.ru