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

Пример 2.7

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


Читайте также:
  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.16 задан граф G, который содержит паросочетание R1 = { 2 } (рис. 2.16,б) и паросочетание R2 = { 1, 3 } (рис. 2.16,с).

 


Рис. 2.16. Граф G (а) и его возможные паросочетания: R1 = { 2 } (б); R2 = { 1, 3 } (в)

 

Одной из важных задач на графе является задача нахождения паросочетания (паросочетаний, если их несколько) с наибольшим количеством ребер. Число ребер такого паросочетания (наибольшего паросочетания) обозначается через p (G). Это число является инвариантом для графа G в том смысле, что для любого графа F, изоморфного G, имеем: p (F) = p (G). Для графа из примера 2.7 p (G) = 2.

Метод чередующихся цепей

Граф G с выделенным в нем паросочетанием R обозначают через GR, ребра R с инцидентными им вершинами называют толстыми, а остальные ребра и вершины графа GRтонкими. Иначе, вершины инцидентные ребрам паросочетания, называют насыщенными.

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

Чередующаяся цепь в GR называется R - увеличителем, если она соединяет тонкие (ненасыщенные) вершины.

Из этих определений следует, что концевые ребра R -увеличителя тоже тонкие.

С помощью R -увеличителя легко переделать паросочетание R графа G в другое паросочетание `R, содержащее на одно ребро больше, заменив в графе GR все тонкие ребра увеличителя на толстые, а все толстые ребра – на тонкие.


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


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

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