Cтраница 4
Рассмотрим граф G, вершинами которого являются буквы алфавита, а смежность вершин означает, что буквы могут быть перепутаны. Тогда максимальное число однобуквенных сообщений, которые можно послать, не опасаясь перепутать их, оче видно, равно a ( G) - максимальному числу независимых вершин в графе G. Ясно, что существует по крайней мере a ( Gk) таких слов ( образованных из максимального множества неперепутываемых букв), но их может быть и больше. Обозначим через a ( G) & максимальное число iWs, з 5, 4 2 и 5 4 неперепутываемы. [46]
Дело в том, что любой канал обладает одноэлементными максимальными множествами, а именно х, AX-Y. Это не имеет места для расширяющих множеств, а следовательно, и для ограниченных максимальных множеств. Читатель легко может построить примеры каналов, не имеющих для данных е, К соответствующих расширяющих множеств, а также каналов, представляющих каждый из возможных случаев, рассматривая их с точки зрения существования максимальных множеств. [47]
Ниже детально описан алгоритм 4.10, носящий имя Хопк-рофта - Карпа. В этом алгоритме вспомогательная бесконтурная сеть, а точнее вспомогательный бесконтурный граф, поскольку пропускные способности всех ребер равны единице, строится при помощи процедуры PGA. Далее проводится поиск в ширину в графе Нм, начиная от свободных вершин в X. Увеличение существующего паросочетания вдоль максимального множества кратчайших увеличивающих цепей с попарно различными множествами вершин реализуется процедурой ФАЗА. [48]
Метод Хопкрофта Карпа позволяет найти наибольшее паросочетание в двудольном графе Н с п вершинами за О ( п5 2) шагов. Детальное описание соответствующего алгоритма дается в книге [38], а идея метода состоит в следующем. Для заданного двудольного графа Н ( X, У, Е) строится вспомогательная бесконтурная сеть, пропускные способности всех дуг которой равны единице. Затем специальная процедура находит максимальное множество непересекающихся кратчайших чередующихся цепей. При этом существующее паросочетание увеличивается вдоль максимального множества путей из s в t с попарно различными подмножествами вершин во вспомогательной сети. [49]
Вспомогательной сети равен единице. Нетрудно заметить, что увеличивающая кратная цепь, найденная на каждой итерации главного цикла процедуры MAXPSA ( см. предыдущий раздел), имеет вид одиночной увеличивающей цепи. Теперь ясно, что во вспомогательной бескон-туриой сети длины / 2 поток идет вдоль максимального множества путей длины / 2 из s в t с попарно непересекающимися множествами промежуточных вершин. Этому множеству есте-ств нным образом соответствует максимальное множество чере - ДУКщихся цепей длины / с попарно непересекающимися множествами вершин ( под максимальным мы подразумеваем такое множество, которое нельзя увеличить на дополнительную чередующуюся цепь длины / и на множество вершин, не содер-жа. [50]