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

Доказательство довольно простое:

(9.44)

Поскольку по нашему предположению закон ° ассоциативен (ведь мы рассматриваем С-морфизмы), тос другой стороны, опять же по предположению, на L также определен ассоциативный закон , следовательно, можно записать

(9.45)

Существование единиц. Существует правая единица где Ф = MOR (X, Y), такая что

(9.46)

и существует левая единицатакая, что

(9.47)

Выпишем эти единицы:

(9.48)

(9.49)

Можем записать

(9.50)

что фактически и доказывает утверждение (9.46). Аналогично можно доказать утверждение (9.47).

Нечеткая категория. Так как — такие нечеткие подмно-

жества, что их композиция ассоциативна и в силу определений (8.2) и (8.3) существуют левая и правая единицы, то для L-нечетких

С-морфизмов можно определить нечеткую категорию таких объектов, как X.

Таким образом, обычная категория — только частный случай не­четкой категории. Эту нечеткую категорию обозначим

(9.51)

Обычная подкатегория. Вспомним приведенное в начале § 7.8 опре­деление понятия категории.

Пусть X — множество объектов и Ф — множество морфизмов. Если

X' X и Ф'Ф — соответствующие морфизмы, то катего­рия С относительно X' будет называться обычной подкатегорией; в этом случае будем писать

С′ С. (9.52)

Нечеткая подкатегория. Если X — множество объектов и LФ —

множество нечетких морфизмов и если X' X и Ф' Ф, то нечеткая категория связанная с X', называется нечеткой подкатегорией.

5. ПРИКЛАДНЫЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ

5.1. Введение

Изучать теорию графов без учета возможных прило­жений— значит потерять основную ее сущность. Учиты­вая важность сказанного, мы разделили книгу на две части. Вторая часть посвящена краткому из - ложению некоторых прикладных задач. Цель настоящго раздела состоит в том, чтобы с помощью примеров научить читателя описывать модели научных и технических задач на языке теории графов и проиллюстрировать различные способы использования графов для формулировки и решения задач. После проработки каждого раздела читателю рекомендуется исследовать основные свойства рассмотренных графов. В некоторых случаях, таких, например, как в задаче о раскрашенных кубах, использование простой идеи графа, при правиль­ном его выборе, оказывается очень эффективным. Ре­шение этой задачи с помощью графов дает четкое объяс­нение головоломке, известной под названием «танталовы» муки («ложные надежды»), решение которой методом проб и ошибки оказывается очень громоздким. В других случаях проявляются более сложные графотеоретические свойства. Некоторые из этих свойств нашли приме­нение в промышленном и государственном управлении. Например, ПЕРТ является основным инструмен­том планирования, который обеспечивает наиболее эф­фективное достижение поставленных целей. Простое понятие графа возникает и используется в очень многих случаях.

Мы будем достаточно кратки при описании прикладных задач, так как подробное рас­смотрение большинства из них может занять целую книгу. Поэтому в некоторых подразделах мы ограничились только изложением основных идей в надежде, что чита­тель продолжит изучение предмета, обратясь к библио­графии. Наиболее близкие на наш взгляд родразделы мы попытались сгруппировать под общими заголовками. Однако предлагаемая группировка является достаточно гибкой и возможно, что читатель сможет найти гораздо более удачную.

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

Одной из наиболее значительных макромоделей ма­тематической экономики и материального обеспечения является модель «затраты — выпуск», связанная с именем Леонтьева. Эта модель, которую мы будем рассматривать с графотеореттической точки зрения, есть, по сути дела, современное представление знаменитой экономической таблицы (tab­leau economique), предложенной в 1758—1759 гг. Фран­суа Кенэ.

В модели «затраты — выпуск» на все операции в эко­номической системе, состоящей из т наборов элементов (учреждений, фирм, хозяйств), накладывается класси­фикационная сетка. Каждый набор элементов системы, в котором производятся (или потребляются) однотипные товары или услуги, называется отраслью промышленно­сти, сектором экономики или сферой экономической дея­тельности. Пусть на некотором историческом периоде в рамках цен, присущих этому периоду, хij≥0 обозначает объем товара, закупленного i-й отраслью у j-й (i, j=1, 2, .... m).

Назовем хij объемом затрат (потребления) товара j-го вида в i-й отрасли. Таким образом, xij будет являться мерой потока средств, поступающих от i к j, в обмен на ресурсы, поступающие от j к i.

Назовем

объемом выпуска отрасли i.

Пусть bij обозначает относительную величину затрат (потребления), т. е. bij= хij /xi ≥0 и называется удель­ной затратой j-го товара в i-й отрасли (i, j=1, ..., m). Будем считать, что существует баланс

для всех i=1, ..., m, т. е. сумма элементов i-й строки матрицы

затраты — выпуск точно равна сумме элемен­тов i-го столбца.

Рассмотрим теперь определенную выше матрицу B*=||bij|| (i, j=1,…,m) и любую главную подматри­цу В матрицы В* такую, что B=||bij||

(i, j=1,...,r и r<m). Тогда система х(I—B*)=θ, где θ — нуль-вектор порядка m, называется замкнутой моделью типа затра­ты— выпуск, а система х(I—В)=w, где В—любая под­матрица порядка r<m и w — неотрицательный вектор, будет называться незамкнутой моделью типа затраты — выпуск. Решение х незамкнутой или замкнутой модели называется допустимым тогда и только тогда, когда вектор х является конечным, неотрицательным, но нену­левым. Неотрицательный вектор w для незамкну­той модели строится как обусловленный «список то­варов» или «список окончательной потребности» для тех отраслей промышленности, которые соответствуют стро­кам и столбцам, содержащимся в В* и не содержащим­ся в В. Допустимые решения х моделей типа затраты — выпуск (незамкнутых или замкнутых) строятся как век­торы уровня производства (величины выпуска), опреде­ляющие выпуск каждой отрасли. Если для незамкнутой модели существует матрица, обратная матрице (I—В), то можно показать, что она представлена в виде известного степенного ряда

Попытаемся теперь дать графотеоретическую формулировку необходимых и достаточных условий существо­вания матрицы, обратной матрице (I—B) в незамкнутой модели типа затраты — выпуск. Для этого введем неко­торые дополнительные определения. Пусть D — ориентированный граф и H — сильно связный подграф D. Сильно связный подграф H будет называться макси­мальным в D тогда и только тогда, когда каждый силь­но связный подграф D либо является подграфом H, ли­бо не содержит вершин, общих с H. Сильно связный подграф H в D называется замкнутым в D тогда и толь­ко тогда, когда H является максимальным и каждая вершина D, достижимая (посредством ориентированного пути) из любой вершины H, содержится в H. Пусть А=||aij|| — неотрицательная квадратная матрица порядка п, т. е. aij ≥0 для i, j=1, .... п. Конечный ориентиро­ванный граф D(A) матрицы А определяется как граф, который состоит из п вершин α1, ..., αn и множества дуг (αk, αi) таких, что дуга (αi, αj) существует в D(A) тогда и только тогда, когда αij >0 в А. Можно показать, что ориентированные графы D(B*) и D(B), соответству­ющие введенным выше замкнутым и незамкнутым мо­делям, играют важную роль при исследовании протека­ния технологических процессов и движения потоков рeсурсов.