Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм поиска критического путиСодержание книги Поиск на нашем сайте Пусть дана сеть (рис. 16.2). Для каждого события i определим наиболее ранний срок его наступления t p(i) по следующему правилу: 1) t p(0)=0; 2) для i >0 t p(i) равно продолжительности самого длинного (0, i)-пути. Значения tp (i) определяют последовательно, переходя от источника к стоку. Так, для рассматриваемого примера (рис. 16.2) находим: t p(0) = 0, t p(1) = 1, t p(2) = 5, t p(3) = 11, t p (4) = 11, t p(5) = 16.
Итак, в нашем примере время выполнения проекта равно 16. Чтобы получить критический путь, будем направлении, от стока к источнику, по тем ребрам (k, i), которые определяли значения t p(i), т.е. для которых выполняется равенство t p(i) - tki = t p(k). В примере это ребра: (3, 5); (2, 3); (2,1). Таким образом, (1, 2, 3, 5) – критический путь.
Резервы времени Некритические работы допускают некоторое запаздывание в их выполнении. Резервом времени события i называется время t (i), на которое можно отложить наступление события i так, что это не увеличит времени выполнения всего проекта. Поздним временем наступления события i, называется время t п(i) = t p(i) + t (i). Поздние сроки наступления событий определяются последовательно, передвигаясь от стока к источнику. Сразу отметим, что для стока n t п(n) = t p(n), как и для всех других событий на критическом пути, которые не имеют резерва времени. Если для всех событий m, непосредственно следующих за событием i (т. е. таких, для которых существуют дуги (i, m)), t п(m) уже вычислены, то находим t п(i) = min{ t п(m) - tim }. При подсчете ранних и поздних сроков наступления событий результаты удобно записывать в вершинах (см. рис. 16.3). Поэтому каждую вершину будем изображать в виде круга, разбитого на три сектора. В нижнем секторе записывается номер события, в левом – раннее время наступления, в правом – позднее.
На рисунке проставлены найденные ранее t p(i), а также t п(i) для событий, находящихся на критическом пути. Далее находим: t п(4) = 16 – 3 = 13; t п(1) = min{11 – 2, 5 – 3} = 2. Таким образом, событие 1 имеет резерв времени t (1) = 2 – 1 = 1, а событие 4 – резерв времени t (4) = 13 – 11 = 2. ТИПОВОЙ РАСЧЕТ «ГРАФЫ» Задание
Граф G задан матрицей смежности. 1. Построить рисунок графа G. 2. Записать степенную последовательность графа G. Является ли граф G регулярным? 3. Является ли граф G связным? Чему равна его вершинная и реберная связность? 4. Осуществить поиск в ширину, начав с вершины 2. 5. Найти удаленности всех вершин. 6. Найти радиус и диаметр графа G; указать центры и периферийные центры. 7. Осуществить поиск в глубину, начав с вершины 3. Записать соответствующий обход и построить дерево путей. 8. Найти циклический ранг и ранг разрезов графа G. 9. Построить остов T графа G с максимально возможным числом концевых вершин. 10. Изобразить остов T как корневое дерево, выбрав в качестве корня центр T. Записать код полученного корневого дерева. 11. Построить фундаментальную систему циклов графа G, ассоциированную с остовом T. Какова мощность пространства циклов графа G? 12. Построить фундаментальную систему разрезов графа G, ассоциированную с остовом T. Какова мощность пространства разрезов графа G? 13. Является ли граф G двудольным? Если является, то укажите доли. 14. Является ли граф G эйлеровым? Если является, то укажите эйлеров цикл. Если нет, то определите, содержит ли G эйлерову цепь (укажите ее). 15. Является ли граф G гамильтоновым? Если является, то укажите гамильтонов цикл. Если нет, то определите, содержит ли G гамильтонову цепь (укажите ее). 16. Является ли граф G планарным? Если является, то постройте изоморфный плоский граф. Сколько граней он содержит? 17. Найдите хроматическое и реберно-хроматическое число графа G. Приведите соответствующие раскраски. 18. Найдите наибольшее паросочетание графа G. Является ли оно совершенным?
Варианты индивидуальных заданий
⎢0 1 0
⎢ 0 0 ⎢1 0 0 1) ⎢ ⎢1 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 0 1 0
⎢1 1 0 0
⎢ 0 0 0 ⎢0 0 0 1 2) ⎢ ⎢0 1 0 1 ⎢1 0 0 1 ⎢ ⎢1 0 1 0
⎢⎣1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1⎤
0 1⎥
1 ⎥ 0 1⎥ ⎥ 0 0⎥ 0 1⎥ ⎥ 1 0⎥
⎥ 0 0⎥⎦
⎢0 1 0
⎢ 0 0 ⎢1 0 0 3) ⎢ ⎢0 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 1⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 1 1
⎢1 1 0
⎢ 0 0 ⎢0 1 0 4) ⎢ ⎢1 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0⎤
0 1⎥
1 ⎥ 1 1⎥ ⎥ 0 0⎥ 1 1⎥ ⎥ 0 0⎥
⎥ 1 0⎥⎦
⎡0
⎢ ⎢0
⎢ ⎢1 5) ⎢ ⎢0 ⎢0 ⎢ ⎢1
⎢ ⎢⎣1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1⎤
0 0⎥
0 ⎥ 0 1⎥ ⎥ 1 0⎥ 0 1⎥ ⎥ 0 0⎥
⎥ 0 0⎥⎦ ⎡0 1 1
⎢1 1 0
⎢ 0 0 ⎢1 1 0 6) ⎢ ⎢1 1 0 ⎢0 0 1 ⎢ ⎢1 0 0
⎢⎣1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1⎤
1 0⎥
1 ⎥ 1 1⎥ ⎥ 0 0⎥ 1 1⎥ ⎥ 0 0⎥
⎥ 1 0⎥⎦
⎢1 1 0
⎢ 0 0 ⎢1 0 0 7) ⎢ ⎢1 0 0 ⎢0 0 1 ⎢ ⎢1 0 1
⎢⎣1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1⎤
0 0⎥
0 ⎥ 1 1⎥ ⎥ 0 0⎥ 1 1⎥ ⎥ 1 1⎥
⎥ 0 0⎥⎦ ⎡0 0 1 0
⎢1 1 0 0
⎢ 0 0 0 ⎢0 0 0 1 8) ⎢ ⎢0 1 0 1 ⎢0 0 0 1 ⎢ ⎢0 1 1 0
⎢⎣1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1⎤
0 1⎥
1 ⎥ 0 1⎥ ⎥ 1 0⎥ 0 1⎥ ⎥ 1 0⎥
⎥ 0 0⎥⎦
⎢0 1 0
⎢ 0 0 ⎢1 0 0 9) ⎢ ⎢1 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 0 1
⎢1 1 0
⎢ 1 0 ⎢0 0 0 10) ⎢ ⎢0 1 0 ⎢1 0 0 ⎢ ⎢1 0 1
⎢⎣0 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0⎤
⎥ 1⎥
⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 1⎥
⎥ 0⎥⎦
⎢1 1 0 0
⎢ 0 0 0 ⎢0 0 0 1 11) ⎢ ⎢0 1 0 1 ⎢0 0 0 1 ⎢ ⎢1 0 0 0
⎢⎣0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 0 1
⎢1 1 0
⎢ 1 0 ⎢1 0 0 12) ⎢ ⎢0 1 0 ⎢1 0 1 ⎢ ⎢1 0 0
⎢⎣0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0⎤
⎥ 0⎥
⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦
⎢0 1 0 1 0
⎢ 0 1 0 1 ⎢1 0 0 1 0 13) ⎢ ⎢0 1 0 0 0 ⎢0 1 0 1 0 ⎢ ⎢1 0 0 0 1
⎢⎣0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1⎤
0 0⎥
1 ⎥ 0 1⎥ ⎥ 1 0⎥ 0 1⎥ ⎥ 0 0⎥
⎥ 0 0⎥⎦ ⎡0 0 1
⎢1 1 0
⎢ 0 0 ⎢1 1 0 14) ⎢ ⎢1 1 0 ⎢0 1 1 ⎢ ⎢0 0 0
⎢⎣1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1⎤
1 0⎥
1 ⎥ 1 1⎥ ⎥ 0 0⎥ 0 1⎥ ⎥ 0 0⎥
⎥ 1 0⎥⎦
⎢1 1 0 0
⎢ 0 0 0 ⎢1 0 0 1 15) ⎢ ⎢1 0 1 1 ⎢0 0 1 1 ⎢ ⎢0 1 0 0
⎢⎣0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0⎤
0 0⎥
1 ⎥ 1 1⎥ ⎥ 0 0⎥ 0 0⎥ ⎥ 1 1⎥
⎥ 1 0⎥⎦ ⎡0 0 1 0
⎢1 1 0 0
⎢ 0 0 0 ⎢0 0 0 1 16) ⎢ ⎢0 1 0 1 ⎢0 0 0 1 ⎢ ⎢0 1 1 0
⎢⎣1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1⎤
⎥ 1⎥
⎥ 1⎥ ⎥ 0⎥ 0⎥ ⎥ 1⎥
⎥ 0⎥⎦
⎢0 1 0
⎢ 0 0 ⎢1 0 0 17) ⎢ ⎢0 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 1⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 1 1
⎢1 1 0
⎢ 0 0 ⎢0 1 0 18) ⎢ ⎢1 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0⎤
0 1⎥
1 ⎥ 1 1⎥ ⎥ 0 0⎥ 1 1⎥ ⎥ 0 0⎥
⎥ 1 0⎥⎦
⎡0
⎢ ⎢0
⎢ ⎢1 19) ⎢ ⎢0 ⎢0 ⎢ ⎢1
⎢ ⎢⎣1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1⎤
0 0⎥
0 ⎥ 0 1⎥ ⎥ 1 0⎥ 0 1⎥ ⎥ 0 0⎥
⎥ 0 0⎥⎦ ⎡0 1 1
⎢1 1 0
⎢ 0 0 ⎢1 1 0 20) ⎢ ⎢1 1 0 ⎢0 0 1 ⎢ ⎢1 0 0
⎢⎣1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1⎤
1 0⎥
1 ⎥ 1 1⎥ ⎥ 0 0⎥ 1 1⎥ ⎥ 0 0⎥
⎥ 1 0⎥⎦
⎢1 1 0
⎢ 0 0 ⎢1 0 0 21) ⎢ ⎢1 0 0 ⎢0 0 1 ⎢ ⎢1 0 1
⎢⎣1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1⎤
0 0⎥
0 ⎥ 1 1⎥ ⎥ 0 0⎥ 1 1⎥ ⎥ 1 1⎥
⎥ 0 0⎥⎦ ⎡0 0 1 0
⎢1 1 0 0
⎢ 0 0 0 ⎢0 0 0 1 22) ⎢ ⎢0 1 0 1 ⎢0 0 0 1 ⎢ ⎢0 1 1 0
⎢⎣1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1⎤
0 1⎥
1 ⎥ 0 1⎥ ⎥ 1 0⎥ 0 1⎥ ⎥ 1 0⎥
⎥ 0 0⎥⎦
⎢0 1 0
⎢ 0 0 ⎢1 0 0 23) ⎢ ⎢1 1 0 ⎢0 0 0 ⎢ ⎢1 0 1
⎢⎣1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 0 1 0
⎢1 1 0 0
⎢ 1 0 0 ⎢0 0 0 1 24) ⎢ ⎢0 1 0 0 ⎢1 0 0 1 ⎢ ⎢1 0 1 0
⎢⎣0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0⎤
⎥ 1⎥
⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 1⎥
⎥ 0⎥⎦
⎢1 1 0 0
⎢ 0 0 0 ⎢0 0 0 1 25) ⎢ ⎢0 1 0 1 ⎢0 0 0 1 ⎢ ⎢1 0 0 0
⎢⎣0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0⎤
⎥ 0⎥
⎥ 0⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦ ⎡0 0 1
⎢1 1 0
⎢ 1 0 ⎢1 0 0 26) ⎢ ⎢0 1 0 ⎢1 0 1 ⎢ ⎢1 0 0
⎢⎣0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0⎤
⎥ 0⎥
⎥ 1⎥ ⎥ 0⎥ 1⎥ ⎥ 0⎥
⎥ 0⎥⎦
⎢0 1 0 1 0
⎢ 0 1 0 1 ⎢1 0 0 1 0 27) ⎢ ⎢0 1 0 0 0 ⎢0 1 0 1 0 ⎢ ⎢1 0 0 0 1
⎢⎣0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1⎤
0 0⎥
1 ⎥ 0 1⎥ ⎥ 1 0⎥ 0 1⎥ ⎥ 0 0⎥
⎥ 0 0⎥⎦ ⎡0 0 1
⎢1 1 0
⎢ 0 0 ⎢1 1 0 28) ⎢ ⎢1 1 0 ⎢0 1 1 ⎢ ⎢0 0 0
⎢⎣1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1⎤
1
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2021-05-12; просмотров: 282; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.198 (0.01 с.) |
Эти значения находятся из соотношения: t p(i) = max{ t p(k) + tki }, т. е. для всех дуг (k, i), для которых i является концом, необходимо вычислить t p(k) + tki и выбрать наибольшее значение.
