![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Матрицы. Понятие трансверсали и покрывающего множестваСтр 1 из 2Следующая ⇒
Понятие трансверсали и покрывающего множества. Словарный ранг матрицы
Теорема Кёнига-Эгервари (1931 г.) вытекает из теоремы Форда-Фалкерсона для транспортных сетей. Она является частным случаем теоремы о различных представителях в теории графов. Пусть 1) 2) Один из подходов к изучению трансверсалей состоит в исследовании так называемой (0, 1)-матрицы, то есть матрицы произвольного размера [
Элементы такой матрицы интерпретируют как разрешенные ( Множество разрешенных элементов называется независимым, если эти элементы расположены в различных строках и столбцах, то есть множество независимо, если 1) 2) при Наибольшее число разрешенных элементов в матрице Будем называть строки и столбцы матрицы рядами или линиями. Совокупность строк и столбцов матрицы, для которой каждый единичный элемент попадает в какой-либо ряд, образуют покрывающее множество, то есть множество покрывающее, если
Для любых независимых множеств элементов
т.к. в независимое множество может входить не более одного элемента из каждого ряда.
2. Теорема Кёнига-Эгервари Теорема. Словарный ранг (0, 1)-матрицы Доказательство.Для данной (0, 1)-матрицы Вершины: источник вершины-строки вершины-столбцы Дуги: источник сток вершина-строка Пропускные способности: пропускные способности каждой дуги равна 1. Решим для построенной сети задачу о максимальном потоке, применяя алгоритм расстановки отметок. Предположим, что построен максимальный поток, то есть процесс расстановки отметок закончился, но сток Из определения потока следует, что на любой дуге он не превышает ее пропускной способности, то есть может равняться 0 или 1. Пусть
все дуги в «средней» части сети (без дуг, выходящих из источника, и дуг, входящих в сток), поток по которым равен 1. Из уравнения сохранения потока следует, что есть независимое множество элементов матрицы. Действительно, каждая вершина-строка, по построению сети, имеет только одну входящую дугу (от источника), поэтому для каждой такой вершины сумма значений потока по дугам, входящим в вершину, равна 0 или 1. Следовательно, и сумма значений потока по дугам, выходящим из вершины, также не превышает 1. Значит, для каждой вершины-строки Из уравнения сохранения для источника и стока имеем, что поток на дугах равен 1, а на остальных дугах в «средней» части сети поток равен нулю. Рассмотрим процедуру отметки вершин сети. На первом шаге алгоритма при просмотре вершины На втором шаге алгоритма в результате просмотра на первом шаге вершин-строк будут помечены вершины-столбцы, в которые ведут из них дуги. В силу максимальности потока, помеченным может оказаться только какой-либо столбец из множества На третьем шаге при просмотре помеченной вершины-столбца Пусть
причем вершина-строка
Так как процесс расстановки отметок остановился, то в «средней» части сети нет дуг, у которых начало помечено, а конец не помечен (это возможно только в вершине-стоке или вершине-источнике). Следовательно, каждая дуга либо имеет начало в множестве
Таким образом, построено независимое множество элементов и покрывающее множество рядов с одинаковым числом элементов. Теорема доказана.
|