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

Существует довольно универсальный тип потока, в котором поступление требований происходит случайным образом и подчиняется пуассоновскому распределению

Важным свойством пуассоновских процессов является тот факт, что вероятность поступления более чем одного требования на малом интервале времени является пренеб­режимо малой по сравнению с вероятностью поступления (или непоступления) одного требования.

Время между поступлениями требований в пуассоновском процессе подчиняется экспоненциальному распреде­лению вида λe-λt. Таким образом, задачи, в которых по­ступления требований подчиняются пуассоновскому рас­пределению, а обслуживание—другому такому же распределению, можно изучать, считая, что интервалы между поступлениями требований и интервалы обслужи­вания распределены экспоненциально.

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

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

Упражнения

16. Интерпретируйте оба названных представления для парал­лельной и последовательной сети с ожиданием и нарисуйте диаграммы.

17. Перечислите десять возможных вариантов потоков в сетях, например стохастические потоки, потоки через губчатые трубки (т. е. потоки с потерями), потоки по деформируемым дугам.

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

Раздел 8

1. Если D(А) имеет контуры, то стяните один нз них, заменяя все его вершины одной псевдовершиной, и устраните все получающие­ся при этом петли. Стяните таким способом все контуры. (Полученный в результате граф будет представлять собой одну вершину, если исходный граф был сильно связным.) Убедитесь в том, что каждая конечная вершина (т. е. вершина, не являющаяся начальной ни для одной из дуг) полученного в итоге такого преобразования графа со­ответствует множеству вершин исходного графа, которое определяет замкнутый сильно связный подграф. Более того, так как преобразован­ный граф не содержит контуров, каждая его вершина, не являющаяся конечной, связана с конечной вершиной путем.

2. В случае, если х(I — B) =10 имеет допустимое решение, сформируйте

где р — нулевой вектор-столбец. Пусть х'—переменная соответству­ющая новой операции. Тогда

Если х — допустимое решение разомкнутой модели, то (х, 1) есть решение расширенной замкнутой модели.

3. Пусть матрице А соответствуют вершины v1, ... ,vn , a w — вершина, соотнесенная последней строке и столбцу. Так как х и у считаются положительными, существуют дуга (vi , w) и дуга (w, vi) для любого L

Следовательно, существуют контуры длины 2. Если есть хотя бы одна дуга вида (vi, v), то существуют также контуры дли­ны 3. Но тогда наибольший общий делитель длины контуров равен 1, откуда и следует примитивность. Чтобы убедиться в том, что индекс примитивности равен четырем для некоторых матриц А, предполо­жим, что существует только одна дуга вида (vi, v). Тогда не суще­ствует пути длины 3 из vj в vi.

4. Покажите, что если некоторая операция (vi, vj) не успе­вает закончиться до начала следующей за ней операции (vj, vk), то эти операции нельзя начинать в моменты Т( vi) и T(vj) соответ­ственно.

5. Заметьте, что T(vi)+X(vi) есть длина некоторого пути от ve до vn. Таким образом, эта сумма не превышает T(vn). Если на­блюдается равенство, то рассматриваемый путь обязательно является критическим.

7. Для нечетного случая имеем

и следовательно, максимальное число контуров равно

8. Используйте тот же метод, что и на рис. 8.15.

9. Используйте тот же метод, что и на рис. 8.15.

11. Структура рассматриваемого графа имеет вид, показанный на рисунке. Заметьте, что здесь имеется 60 пересечений, что соответ­ствует значению М′10.

12. Предположите, что кубы сложены так. что их номера сверху вниз равны 1, 2, 3 и 4. Стороны х. у, х' и у' (сверху вниз) можно окрасить следующим образом: GYBR, BGRY, BRYG и YBRG соответ­ственно.

13. Да, требуется меньше пересечений. Если устраняются разли­чия между С и К с помощью замены К на С, то в решении подпосле­довательность ММСК, (МС), МИСС, (СС) может быть заменена на ММСС, (СС), что устраняет одни круговой обход.

14. Начиная с v, пронумеруйте вершины числами от 1 до 8, двигаясь по часовой стрелке. Искомый путь проходит через вершины в следующем порядке: 143821856. Вершины 1 и 8 повторяются.

15. Это матрица смежности графа, показанного на рис. 5.20.

16. Это следует из того факта, что п элементов (диагональных) имеют фиксированные значения, а остальные (п2 — п) могут прини­мать любые из двух возможных значений.

17. Используйте в качестве V ориентированную матрицу смежности, в которой единичные элементы занимают следующие положе­ния: (1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 2), (4, 5), (5, 2), (5, 7), (6, 5), (7, 5). Для получения ответов возведите V в нужную. степень.

18. Если бы внутренняя вершина была покрыта более чем од­ним ребром из выбранного множества, то ее степень была бы боль­ше 2. Если бы внешняя вершина была покрыта более чем одним реб­ром, то граф не мог бы быть деревом.

19. Заметьте, что если бы внутренняя вершина не была покры­та, то две внешние вершины тоже оказались бы непокрытыми, так как каждое ребро соединяет внутреннюю вершину с внешней.

20. Рассмотрите простую цепь, проходящую через вершины v0, v1,..... vk, где v0—непокрытая внешняя вершина. Ребро, соединяю­щее v0 с v1, не принадлежит М, так как v0 не покрыта. Учитывая, что v1 имеет степень 2 и является покрытой, получаем, что ребро, соединяющее v1 с v2, должно принадлежать М. Повторяя проведенные рас­суждения, устанавливаем чередующуюся принадлежность ребер М.

21. В случае рис. 8.17 (включая пунктирную часть) можно най­ти паросочетания, которые оставляют только одну вершину непокры­той. Для рис. 5.15 существует совершенное паросочетание. В обоих случаях максимальное паросочетание не является единственным.

22. В общем случае на эти вопросы можно ответить, складывая а) строки или b) столбцы, вычисляя V2(c) и V+V2+V3+V4(d). Объясните почему.

25. Пусть ti обозначает i-й член. Если ti— ti+1>l, то вставьте

(ti— ti+1— 1) единиц после ti, если ti≤ ti+1, то вставьте ti — 1 единицу после ti. (Если ti —последний член, то действуйте так же, как в последнем случае.)

26. t 0 = 4.

27. Пусть v имеет петлю. Если граф содержит п вершин, то су­ществуют пути из любой вершины vi в v и из v в любую vj, кото­рые состоят не более чем из (п— 1) дуг. Таким образом, можно, полу­чить путь длины (2n — 2), взяв два таких пути и добавив к ним со­ответствующее число петель. (Сравните с обсуждением примитивных матриц, которое проводилось выше.)

28. Здесь имеется 4 автоморфизма. Верхние н нижние вершины можно либо переставить, либо оставить неизменными.

Независимо от этого левые и правые вершины также могут либо переставляться, либо остаться фиксированными.

29. Граф, соответствующий возведению вычетов в третью сте­пень, имеет петлю в каждой вершине. Граф, соответствующий возве­дению вычетов в квадрат, имеет следующие дуги: (0, 0), (1, 1), (2,4), (3,3), (4,4), (5, 1).

30.

* неопределенно.

31. Дуги графа образуют простой контур, который последова­тельно проходит через 0, 5, 4, 3, 2 и 1.

32. Перегруппируйте строки и столбцы (по отношению к исходному разделению) в следующем порядке: 1, 3, 2, 4, взяв

Вычислите В = Р-1АР и заметьте, что ее подматрицы соответствуют заданным. Заметьте также, что В2 является блочно-диагональной матрицей. Каждый ее диагональный блок равен