Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 127
Текст из файла (страница 127)
В столбце Ьз нет ни одной (Ц, поэтому вершина из В, не имеюшая паросочетаюшего ребра, найдена. Следовательно, РАЗДЕЛ 16.2. Перосочетвное 713 искомая цепь построена. Теперь имеем матрицу. Используя метки ребер внизу и в самом крайнем столбце таблицы, возврашаемся назад и восстанавливаем цепь а4 — ~ Ь4 аз Ьз аь Ьз.
Заметим, что цепь не совпадает с построенной в примере 16.20. Она короче. Изменение статуса ребер (паросочетаюшие — на непаросочетаюшие и наоборот), как в примере !6.20, дает паросочетание, изображенное на рис. !6.36. а, еЬ, ° Ьа аз ° ьэ Рис. !6. 36 Для получения новой матрицы каждую 1 по ходу движения меняем на 1Ц, а каждую !1) — на 1.
В результате получаем такую матрицу. Используя приведенную выше процедуру для паросочетания из примера 16.21, начинаем с матрицы Ч'14 Глявл 1б. сети и в конце приходим к матрице Используя метки ребер внизу и в самом крайнем столбце таблицы, возвращаемся назад и восстанавливаем цепь аз- Ьз"-аз- Ь4 -аг- Ьз — аз- Ьз, которая совпадает с полученной в примере 1б.21.
Матрица нового паросочетання имеет следующий вид. ° УПРАЖНЕНИЯ 1. Для приведенных ниже двудольных графов найдите максимальное паросочетание, используя методы, изложенные в этой главе. Является ли каждое паросочетание полным? а) б) а 2. Выполните задание предыдущего упражнения для следующих графов. ° 1 в) а) б) г) а РАЗДЕЛ 1Б.2. Лерооочетвние 715 в) 716 ГЛАВА 1В.
Сети 3. Шесть человек ищут работу. Человек а готов выполнять работы А, Р и Р. Человек Ь готов выполнять работу С. Человек с готов выполнять работы В и Р. Человек г( готов выполнять работы А и Е. Человек е готов выполнять работы В и Р. Человек Г' — работу Е. Найдите паросочетание, согласно которому наибольшее количество людей получит работу, которую они готовы выполнять.
Все ли получат работу? 4. Шестеро девушек хотят выбрать партнера для танцев. Элис нравятся Чарльз и Эдвард; Бетти нравятся Альберт и Дэн; Клара предпочитает Чарльза и Эдварда; Донна любит танцевать с Дэном; Элизабет нравятся Барт и Эдвард. Подберите как можно большему числу девушек пару для танцев, которая была бы им по душе. Возможно ли каждой девушке подобрать парня, который ей нравится? 5.
Эмми входит в состав комитетов а и Ь. Брюс — комитетов а и с. Чарльз— член комитета Ь. Дэнис — член комитетов Ь, с и е. Эллен входит в состав комитетов д и е. Председатель студенческого совета планирует пригласить на совещание пятерых членов совета, входящих в различные комитеты. Возможно ли это? 6. Шестеро друзей собираются на маскарад. Все хотят быть в разных костюмах. Анне нравится костюм клоуна; Бену нравятся костюмы приведения и Франкенштейна; Кортни — клоуна и костюмы из вестернов; Денис хотел бы нарядиться приведением, Дракулой или Франкенштейном; Эллен предпочитает костюм клоуна, костюм из вестернов или Шерлока Холмса; Френк— костюм Дракулы и клоуна.
Есть ли возможность для всех пойти на маскарад в разных костюмах, причем в тех, которые им нравятся? 7. Составьте формальный алгоритм для нахождения максимального паросочетания М на двудольном графе С = (Ъ; Е) без использования матриц. 8. Составьте формальный алгоритм для нахождения максимального паросочетания М на двудольном графе С = (Ъ; Е) с использованием матриц. 16.3. СЕТИ ПЕТРИ В этом разделе продолжается рассмотрение двудольных графов с ориентированными ребрами.
Однако, в отличие от предыдущего раздела ориентация ребер допускается в обоих направлениях. Пусть С(Ь; Е) — двудольный ориентированный граф, в котором Ъ' = Р О Т. Множество Р называется множеством лозиг!ий, а множество Т вЂ” множеством переходов. Š— множество ориентированных ребер между Р и Т. В рассмотрение включено также множество функций М таких, что каждая функция р Б М ставит в соответствие неотрицательное целое число каждому элементу множества Р. Функция р называется разметкой графа С. Ориентированный граф, обладающий такими свойствами, называется сетью Петри.
Сети Петри используются главным образом для моделирования параллельных процессов: для моделирования компонентов компьютера, параллельных вычислений, в робототехнике и даже для описания музыкальных структур (см. (4!)). Вообще, сети Петри используются для нахождения дефектов в проекте системы, РАЗДЕЛ 16.3. Сети Петри 717 Рг О-~-О Рис. 16.37 Срабатывание перехода 1 — это удаление по одной метке из каждой позиции р„ так что имеется ориентированное ребро из р; в 1, и добавление метки в каждую позицию ру, так что имеется ориентированное ребро из ! в р . Например, срабатывание тг в приведенном выше примере приводит к сети Петри, изображенной на рис. 16.38. Рг 0- -0 1 Рис. !б.38 В сети Петри, изображенной на рис.
!6.39, срабатывание перехода с1 даст в результате сеть Петри, изображенную на рис. 16.40. 'О ~-о' О 'О [-О' Рг( ) Рис. 1б.39 Рис. 1б.40 В сети Петри, изображенной на рис. 16.41, срабатывание перехода сг даст в результате сеть Петри, изображенную на рис.
16.42. ~ОРг '0-! 11 0) Рг Рис. 16.41 Рис. 1б.42 хотя имеют и многие другие применения. Они обладают многими свойствами блок-схем и конечных автоматов, речь о которых пойдет дальше. Более подробно см. [85[. Каждая позиция в сети Петри обозначена кружком, а каждый переход— вертикальной линией. Если р — позиция, то 7" (р) называется разметкой позиции р. Разметка множества С показана на графе с помощью больших черных точек, называемых метками, помещенных в кружки, которые обозначают позиции.
Если кружок позиции р пуст, это означает, что в р меток нет, поэтому 7[р) = О. Рассмотрим граф, изображенный на рис. 16.37. В этой сети Петри р, и рг — позиции, а тг — переход. Позиция рг содержит одну метку, а рг меток не содержит. 718 ГЛКВА 16. Сети В сети Петри, изображенной на рис. 16.43, срабатывание перехода тг даст в результате сеть Петри, изображенную на рис.
16.44, поскольку имеется ориентированное ребро из 1, обратно в ры Рг О=-О Рис. 16.46 Рис. 16.44 Переход с может сработать, когда каждая позиция р, такая, что имеется ориентированное ребро из р, в с, содержит метку. Когда такая ситуация имеет место, говорят, что переход 1 разрешен. Переход тг в сети Петри, изображенной на рис. 16.45, не может сработать, поскольку в рг нет метки, О О' — ~ Оьрг 1 О ! Рис. 16.47 Рис.
16.46 Срабатывание перехода предполагается мгновенным и может произойти в любой момент, когда переход разрешен. Порядок срабатывания перехода ограничен только наличием достаточного количества меток, необходимых для разрешенности перехода. Вполне возможно, что в некоторый момент времени более В некоторых случаях необходимо, чтобы при срабатывании перехода удалялась или прибавлялась более чем одна метка.
Если при срабатывании перехода 1 из позиции р необходимо удалить более чем одну метку, то ориентированное ребро из р в т помечается таким количеством меток, которое следует удалить из р. Если меток нет, то их количество по умолчанию предполагается равным 1. Если при срабатывании перехода 1 в позицию р необходимо добавить более чем одну метку, то ориентированое ребро из 1 в р помечается таким количеством меток, которое нужно добавить в р. Если меток нет, то количество опять предполагается равным 1.
Если при срабатывании перехода с из позиции р следует удалить и меток, то р должна содержать, по крайней мере, и меток, чтобы переход 1 был разрешен. В сети Петри, изображенной на рис. 16.46, срабатывание перехода тг дает в результате сеть Петри, изображенную на рис. 16.47. Переход 1, не может сработать снова, поскольку в рг нет достаточного количества меток. РДЗДЕЛ тб.3. Сети Петри 719 чем один переход будет разрешен. В этом случае любой из них может сработать первым. Например, если моделируются несколько процессоров, имеющих общие данные и периферию, то неизвестно, когда одному из процессоров понадобится принтер или данные.
Сети Петри используются для проверки работоспособности системы даже в условиях такой неопределенности системы. Состоянием з сети Петри называется количество меток в каждой позиции, определяемое функцией Рн е М. Таким образом, состояние сети Петри — это то же самое, что и разметка сети Петри. Термин "состояние" используется при рассмотрении автоматов и других машин с конечным количеством состояний. Поскольку Рн полностью определяют состояние, будем их отождествлять. Срабатывание перехода изменяет текушее состояние на состояние, определяемое другой функцией и из М. Поэтому новое состояние сети Петри зависит от текушего состояния и сработавшего перехода.
Таким образом, и = б(Р„1), где б(Р;,С)— состоиние, полУченное из состоЯниЯ Рн Если в некотоРый момент вРемени не сУ- ществует разрешенного перехода, то функция состояния более не определяется, и процесс, описываюший сеть Петри, завершается. Рассмотрим сеть Петри, изображенную на рис. 16.48. При срабатывании перехода гг сеть Петри переходит в состояние, показанное на рис. 16.49. При срабатывании перехода 14 имеем сеть Петри, изображенную на рис. 16.50. р2 Ре Рис. 1б.48 Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
