Составители:
Рубрика:
78
совместимость членов экипажа. Путем тестирования установлены пары кандидатов,
присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты
тестирования отражены в таблице. (Если на пересечении I строки j столбца находится
знак «+», то участие I и j кандидатов в одной экспедиции нежелательно.) Разделите
кандидатов на две группы для участия в экспедициях.
1 2 3 4 5 6 7 8 9 10
1 + + +
2 + +
3 + +
4 + +
5 + +
6 + +
7 + + +
8 + + +
9 + +
10 + + +
Ориентированные графы и мультиграфы
127. Решите задачу 35. Граф может быть орграфом или мультиграфом.
128. В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший
король хочет ввести на дорогах одностороннее движение, так чтобы, выехав из любого
города, в него нельзя было вернуться. Можно ли так сделать?
129.
Докажите, что на ребрах связного графа можно так расставить стрелки, чтобы из
некоторой вершины можно было добраться по стрелкам до любой другой.
130.
Доказать, что связный граф можно обойти, проходя по каждому ребру дважды.
131. Изобразите матрицы смежности и инцидентности ориентированного графа:
132.
Дана матрица смежности. Изобразить граф, ей соответствующий.
а)
1 2 3 4 5 6 7
1 1 0 1 1 0 1 0
2 0 0 0 0 0 0 1
3 1 0 0 1 0 1 0
4 0 1 0 0 0 0 1
5 1 1 1 0 0 0 1
6 1 0 1 1 0 1 0
7 0 1 0 0 1 0 0
б)
1 2 3 4 5
1 1 2 0 0 1
2 0 0 3 0 0
3 0 0 2 1 0
4 1 0 1 0 1
5 1 0 0 0 0
133. Определите, какие из предложенных графов являются ориентируемыми.
Страницы
- « первая
- ‹ предыдущая
- …
- 76
- 77
- 78
- 79
- 80
- …
- следующая ›
- последняя »
