Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Пример 2.8

Пример 1.30 | Пример 1.31 | N – раз. | Пример 2.1 | Пример 2.2 | Пример 2.3 | Пример 2.4 | Доказательство | Пример 2.5 | Пример 2.6 |


Читайте также:
  1. Fill in the missing numerals in the following sentences as in the example given for the first sentence. (Вставьте пропущенное имя числительное как в примере.)
  2. Gt; Часть ежегодно потребляемого основного напитала не должна ежегодно воз­мещаться в натуре. Например, Vu стойкости машины в течение года перенесена на
  3. IV. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПРИМЕРНОЙ ПРОГРАММЫ
  4. IX. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К СЕМИНАРСКИМ ЗАНЯТИЯМ. ПРИМЕР.
  5. VII. Примерный перечень тем рефератов и курсовых работ
  6. Актуальный пример разработки программы в случае моббинга
  7. Анализ логопедического занятия (примерная схема протокола)

На рис. 2.17 показано преобразование паросочетания R в паросочетание `R.


Рис. 2.17. Преобразование паросочетаний

 

Если граф , в свою очередь, имеет `R -увеличитель, то можно увеличить результат еще на 1 и т.д. Этот процесс можно использовать для решения задачи о наибольшем паросочетании. При этом процесс заканчивается, если выполняются условия следующей теоремы.

Теорема 2.11. Если количество ребер в паросочетании R меньше, чем p (G), то в графе GR = (V, E) существует R -увеличитель.

Доказательство. Пусть в G = GR паросочетание R не является наибольшим, т.е. в G есть другое паросочетание T с большим числом ребер, чем в R. Рассмотрим суграф H графа G с ребрами из множества: F = (R \ T) È (T \ R). Покажем, что степень каждой вершины этого суграфа не превышает двух. Действительно,

· все вершины суграфа H, не являющиеся инцидентными ребрам из множества F, изолированы;

· если некоторая вершина инцидентна ребру из паросочетания R, но не является инцидентной ребру из T, то ее степень равна единице, так как R – паросочетание;

· если некоторая вершина инцидентна ребру из паросочетания T, но не является инцидентной ребру из R, то ее степень равна единице, так как T – паросочетание;

· если некоторая вершина инцидентна ребру из множества (R \ T) и ребру из (T \ R), то она имеет степень 2, в противном случае должно существовать еще одно ребро, принадлежащее одному из рассмотренных множеств, это противоречит тому, что R и T – паросочетания.

Других вершин нет. Отсюда следует, что каждая компонента суграфа H представляет собой простую цепь или простой цикл с чередованием ребер из R и T. Среди этих компонент обязательно есть простая цепь нечетной длины, начинающаяся и оканчивающаяся ребрами паросочетания T, так как ребер в T больше, чем в R. Ясно, что это будет искомый R -увеличитель в GR.

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

Двудольным графом называется граф G, множество вершин V которого допускает разбиение: { V1, V2 }, где V1 и V2 содержат попарно несвязные вершины.

Двудольный граф более подробно записывается как G = (V1 , V2 , E), где
V1 È V2 = V, V1 Ç V2 = Æ, при этом ребра E могут соединять вершины только из V1 (цвета 1) с вершинами из V2 (цвета 2).

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


Дата добавления: 2015-07-20; просмотров: 45 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Пример 2.7| Пример 2.10

mybiblioteka.su - 2015-2024 год. (0.006 сек.)