Дискретно-непрерывная математика (стр. 1 )

Парадигма развития науки

Методологическое обеспечение

А. Е. Кононюк

ДИСКРЕТНО-НЕПРЕРЫВНАЯ МАТЕМАТИКА

Книга 7

Графы

Часть 3

Киев

«Освіта України»

2015

УДК 51 (075.8)

ББК В161.я7

К213

Рецензенты:

— к-т физ.-мат. наук, доц. (Национальный тех—нический университет «КПІ»);

— д-р физ.-мат. наук, проф.,

— к-т техн. наук, доц. (Киевский университет эко—номики, туризма и права);

— д-р техн. наук, проф. (Национальный ави— ационный университет).

К213 Дискретно-непрерывная математика. (Графы. К.7, Ч.3 (в 7 частях)). — В 15-и кн. Кн 7,— К.: Освіта України. 2015. — 541 с.

ISBN 978-966-373-693-8 (многотомное издание)

ISBN 978-966-373-694-5 (книга 7)

Многотомная работа содержит систематическое изложение математических дисциплин, исспользуемых при моделировании и исследованиях математических моделей систем.

В работе излагаются основы теории множеств, отношений, поверхностей, пространств, алгебраических систем, матриц, графов, математической логики, теории вероятностей и массового обслуживания, теории формальных грамматик и автоматов, теории алгоритмов, которые в совокупности образуют единную методолгически взамосвязанную математическую систему «Дискретно-непрерывная математика».

Для бакалавров, специалистов, магистров, аспирантов, докторантов и просто ученых и специалистов всех специальностей.

УДК 51 (075.8)

ББК В161.я7

ISBN 978-966-373-693-8 (многотомное издание) © , 2015

ISBN 978-966-373-694-5 (книга 7) © Освіта України, 2015

Оглавление

1. Бесконечные графы, цепи Маркова, паросочетания……………….....8 1.1.Бесконечные графы................................................................................8

1.2. Цепи Маркова……………………………………………………......12

1.3.Теорема о свадьбах…………………………………………………...18

1.4. Теория трансверсалей……………………………………………......22

1.5. Приложения теоремы Холла…………………………………….......25

1.6. Теоремa Менгерa…………………………………………………......30

1.7. Потоки в сетях……………………………………………………......36

1.8. Теория матроидов…………………………………………………....44

1.8.1. Ведение в теорию матроидов………………………………….....44

1.8.2. Примеры матроидов………………………………………….......49

1.8.3. Матроиды и теория графов……………………………………......54

1.8.4. Матроиды и теория трансверсалей…………………………….....60

1.9 Экстремальные множества и задачи покрытия и упаковки в матроидах……………………………………………………………........65

2. Нечеткие графы и нечеткие отношения……………………………...98

2.1. Нечеткие графы……………………………………………………..99

2.2. Нечеткое отношение………………………………………………..105

2.3. Композиция двух нечетких отношений…………………………...120

2.4. Нечеткое подмножество, индуцированное отображением……....129

2.5. Условные нечеткие подмножества………………………………...132

2.6. Свойства нечетких бинарных отношений………………………...141

2.7. Транзитивное замыкание нечеткого бинарного отношения……..151

2.8. Путь в конечном нечетком графе………………………………….159

2. 9. Нечеткие отношения предпорядка………………………………..163

2.10. Отношение подобия……………………………………………….167

2.11. Подотношение подобия в нечетком предпорядке………….170

2.12. Антисимметрия…………………………………………………....173

2.13. Нечеткие отношения порядка…………………………………….178

2.14. Антисимметричные отношения без контуров, порядковые отношения, порядковые функции нечеткого отношения порядка…..186

2.15. Отношения различия…………………………………………… 195

2.16. Отношения сходства………………………………………………199

2.17. Некоторые свойства отношений подобия и сходства………...213

2.18. Некоторые свойства нечетких отношений

совершенного порядка…………………………………………………..233

3. Законы нечеткой композиции………………………………………..242

3.1. Понятие закона композиции………………………………………242

3.2. Закон нечеткой внутренней композиции. Нечеткий группоид….244

3.3. Основные свойства нечетких группоидов………………………..250

3.4. Нечеткие моноиды…………………………………………………256

3.5. Нечеткая внешняя композиция……………………………………262

4. Обобщение понятия нечеткого множества и нечеткого графа….. 268

4.1. Введение …………………………………………………………...268

4.2. Операции на обычных множествах................................................269

4.3. Основные свойства множества отображений.................................272

4.4. Обзор некоторых основных структур..............................................275

4.5. Обобщение понятия нечеткого подмножества...............................289

4.6. Операции на нечетких подмножествах в случае,

когда L— решетка.....................................................................................308

4.7. Обзор некоторых понятий, необходимых для введения

понятия категории.....................................................................................312

4.8. Понятие категории.............................................................................335

4.9. Нечеткие С-морфизмы......................................................................346

5. Прикладные задачи теории графов.....................................................356

5.1. Введение…….....................................................................................356

5.2. Экономика и материальное обеспечение........................................356

5.3. Линейное программирование и потоки в сетях..............................361

5.4. Задачи типа ПЕРТ..............................................................................362

5.5. Примеры комбинаторных задач в теории графов……...................369

5.6. Минимальное число аварий на кирпичном заводе.........................382

5.7. Минимальное число пересечений в полных графах....................386

5.8. Задача соединения раскрашенных кубов........................................388

5.9. Задачи изменения состояний системы............................................390

5.10. Матричная форма задачи о переправе...........................................396

5.11. Задача деления треугольника.........................................................402

5.12. Игра двух лиц..................................................................................403

5.13. Игры на шахматной доске..............................................................407

5.14. Максимальные паросочетания.......................................................409

5.15. Анализ технических систем…………...........................................419

5.16. Сети связи........................................................................................424

5.17. Граф потока сигналов.....................................................................428

5.18. Переключательные сети (схемы)...................................................434

5.19. Объединение электростанций в энергосистему...........................436

5.20. Печатные схемы...............................................................................437

5.21. Идентификация в химии.................................................................439

5.22. Простая модель из органической химии.......................................443

5.23. Два примера из статистической механики....................................445

5.24. Генетическая задача........................................................................447

5.25. Графы и кибернетика......................................................................449

5.26. Применения в социологии..............................................................453

5.27. Математические модели разоружения..........................................457

5.28. Лингвистика……………………………………………………….460

5.29. Математические машины и цепи Маркова……………………...464

5.30. Группы и обыкновенные графы………………………………….469

5.31. Построение деревьев минимальной общей длины……………...471

5.32. Графы и собственные значения неотрицательных матриц…….472

5.33. Задача ранжирования……………………………………………..474

6. Потоки в сетях………………………………………………………..478

6.1. Введение…………………………………………………………….478

6.2. Основная терминология……………………………………………479

6.3. Отношения между потоками и операции над ними…………….481

6.4. Простые потоки…………………………………………………….483

6.5. Другое представление потока……………………………………..484

6.6. Потоки с ограничениями на дугах………………………………..486

6.7. Максимальный поток в транспортной сети………………………493

6.8. Максимальные потоки в сетях общего вида с ограниченными пропускными способностями дуг……………………………………...495

6.9. Потоки минимальной стоимости………………………………….499

6.10. Некоторые специальные задачи о потоках………………………505

9.11. Задачи о многопродуктовых потоках……………………………507

6.12. Стохастические потоки в сетях…………………………………..510

Ответы к упражнениям............................................................................513

Приложение А…………………………………………………………..519

Приложение Б……………………………………………………………522

ЛИТЕРАТУРA…………………………………………………………...536

1. Бесконечные графы, цепи Маркова, паросочетания

1.1.  Бесконечные графы

Здесь мы покажем, как можно обобщить не­которые определения, приведенные ранее, на случай бесконечных графов. Напомним, что бесконечным графом называется пара (V(G), E(G)), где V(G)— бесконечное множество элементов, называемых вершинами, a E(G) — бесконечное семейство неупорядоченных пар эле­ментов из V(G), называемых ребрами. Если оба множества V(G) и E(G) счетны, то G называется счетным графом. Заме­тим, что наши определения исключают те случаи, когда V(G) бесконечно, a E(G) конечно (такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин), или когда E(G) бесконечно, а V(G) конечно (такие объекты являются конечными графами с бесконечным числом петель или кратных ребер). Некоторые определения, данные ранее (таких понятий, как «смежный», «инцидентный», «изоморфный», «подграф», «объединение», «связный», «компонента»), переносятся на бесконечные графы. Степенью вершины v бесконечного графа называется мощность множества ребер, инцидентных v; степень вершины может быть конечной или бесконечной. Бесконечный граф, все вершины которого имеют конечные степени, называется локально конечным; хорошо известным примером такого графа является бесконечная квадратная решетка, часть которой изображена на рис. 1.