ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.12.2023
Просмотров: 105
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Получим итоговую таблицу:
| | T0 | T1 | L | M | S |
 | - | - | + | - | + |
 | - | + | - | - | - |
В каждом столбце есть « - », следовательно, система полная
29. Дан граф. Составить для данного графа структурную матрицу. Найти:
а) все простые пути из вершины i в вершину j;
б) совокупность всех сечений между вершинами i и j.
Решение:
Граф имеет ориентированные ребра (3,1), (3,4) и (4,2)
Структурная матрица S имеет вид:
Для получения минора М34 вычеркиваем из матрицы третью строку и четвертый столбец
=
Простые пути из вершины 4 в вершину 3:
Найдем сечения (
=
=
.39. Задана сеть и начальный поток f. Требуется построить максимальный поток, считая вершину с номером 1 источником и вершину с номером 4 стоком. Указать минимальное сечение, величина которого равна максимальному потоку.
Решение:
-
путь из s=1 в t=4 по которому поток может быть увеличен 1-2-4
Пометки вершин s=(0,
. Добавка к потоку 
Построим новый поток, увеличенный на 3:
-
путь из s=1 в t=4 по которому поток может быть увеличен 1-3-4
Пометки вершин s=(0,
. Добавка к потоку 
Построим новый поток, увеличенный на 3, при этом, не отправляя по потоку (3,2), а направив в поток (3,4):
-
путь из s=1 в t=4 по которому поток может быть увеличен 1-2-3-4
Пометки вершин s=(0,
. Добавка к потоку 
Построим новый поток, увеличенный на 2:
Больше поток увеличить нельзя
Дуги (1,4) (2,4), (3,4) – насыщенные
Дуги (1,2) и (2,3) ненасыщенные
Минимальное сечение 14+3=17 совпадает с величиной максимального потока.
49. На указанном множестве задано отношение. Для отношения нужно:
а) записать отношение R;
б) построить матрицу смежности и граф отношения;
в) проверить, является ли отношение рефлексивным, симметричным, транзитивным.
На множестве А={1,2,3,4,5,6} задано отношение R: xRy тогда и только тогда, когда |x-y| нечетное
Решение:
а) R={(1,2), (2,1), (1,4), (4,1), 1,6), (6,1), (2,3), (3,2), (2,5), (5,2), (3,4), (4,3), (3,6), (6,3), (4,5), (5,4), (5,6), (6,5)}
б) построим матрицу смежности
Построим граф отношения:
в) отношение не рефлексивно, так как (х, х)
Разность двух одинаковых чисел равна нулю
, а ноль – это четное число
Отношение симметрично, так как выполняется условие: если xRy, то и уRх, например: если (1, 2)
, то и (2, 1) Отношение не транзитивно, так как не выполняется условие, что если xRy, а уRz, то и xRz. Например: (1, 2)
, (2, 5) 