Для показанного на рисунке 9 указать гамильтонов и негамильтонов контуры.
В ориентированном графе, показанном на рисунке 10, найти контуры длины 3, 4, 5, гамильтов контур.
Для выполнения заданий необходимо определить и записать в таблице К1 значеня булевых переменных a1 - a48 (нули и единицы), исходя из следующих параметров:
Н - порядковый номер студента в списке группы;
Ф - число букв в фамилии студента.
Впишите свои параметры в табличку:
Н= | Ф= |
Значения а1 - а48 выбираются из таблицы К2 по следующему правилу:
а1 - а6 - 6 чисел подряд, начиная с позиции Н;
а7 - а16 - 10 чисел подряд, начиная с позиции Ф + 20;
а17 - а26 - 10 чисел подряд, начиная с позиции Н + Ф + 20;
а27 - а36 - 10 чисел подряд, начиная с позиции Н + 2Ф +40
а37 - а48 - 12 чисел подряд, начиная с позицииН + ЗФ +60.
a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | a13 | a14 | a15 | a16 |
a17 | a18 | a19 | a20 | a21 | a22 | a23 | a24 | a25 | a26 | a27 | a28 | a29 | a30 | a31 | a32 |
a33 | a34 | a35 | a36 | a37 | a38 | a39 | a40 | a41 | a42 | a43 | a44 | a45 | a46 | a47 | a48 |
| 10 | 15 | 20 | |||
0 1 0 0 0 | 1 0 0 1 1 | 0 1 0 0 1 | 0 0 1 0 0 | |||
20+ | 0 0 1 0 0 | 1 0 1 1 1 | 1 0 0 1 1 | 0 0 0 1 1 | ||
40+ | 0 0 0 0 0 | 1 0 0 0 0 | 0 0 1 1 1 | 0 0 0 1 0 | ||
60+ | 0 1 0 0 1 | 1 0 1 0 1 | 1 0 1 1 0 | 0 1 1 0 1 | ||
80+ | 0 1 0 0 0 | 0 0 1 1 0 | 0 1 1 1 0 | 1 1 1 0 1 | ||
100+ | 0 1 1 1 0 | 0 0 1 0 0 | 1 1 0 0 1 | 1 0 1 0 0 | ||
120+ | 1 0 1 0 0 | 1 0 1 1 0 | 1 0 0 0 1 | 1 0 0 0 1 |
I) Символами а1 - а28 заполнить квадратную матрицу 7х7 (диагональные и наддиагональные элементы). Продолжить полученную треугольную матрицу симметричным образом.
a1 | a2 | a3 | a4 | a5 | a6 | a7 |
a8 | a9 | a10 | a11 | a12 | a13 | |
a14 | a15 | a16 | a17 | a18 | ||
a19 | a20 | a21 | a22 | |||
a23 | a24 | a25 | ||||
a26 | a27 | |||||
a28 |
1) Рассматривая полученную матрицу как матрицу соседства вершин неориентированного графа G с вершинами 1, 2, 3, 4, 5, 6, 7, построить изображение графа. (Рекомендация: расположите вершины графа в вершинах правильного семиугольника).
2) Построить матрицу инциденций графа G.
3) Удалив петли (если они есть), найти цикломатическое число полученного графа.
II) Символами а11 - а38 заполнить наддиагональные элементы квадратной матрицы 8x8(диагональные элементы - нулевые). Продолжить полученную треугольную матрицу симметричным образом.
0 | a11 | a12 | a13 | a14 | a15 | a16 | a17 |
0 | a18 | a19 | a20 | a21 | a22 | a23 | |
0 | a24 | a25 | a26 | a27 | a28 | ||
0 | a29 | a30 | a31 | a32 | |||
0 | a33 | a34 | a35 | ||||
0 | a36 | a37 | |||||
0 | a38 | ||||||
0 |
1) Рассматривая полученную матрицу как матрицу соседства вершин
неориентированного графа G с вершинами 1 - 8, построить изображение графа G.
2) Определить цикломатическое число графа G.
3) Выделить какой-либо остов графа G.
4) Построить базис циклов графа G.
Постройте сомостоятельно остов и базис циклов неориентированных графов, заданных списком ребер:
1.{(1,2),(1,3),(1,5),(1,6),(2,3),(2,4),(3,4),(3,6),(4,7),(5,6),(6,7)}
2.{(1,2),(1,4),(1,5),(1,7),(2,3),(2,4),(3,4),(3,5),(3,7),(4,5),(5,7)}
3.{(1,2),(1,3),(1,5),(1,6),(2,3),(2,5),(3,4),(3,6),(4,5),(4,6),(5,6)}
4.{(1,2),(1,4),(1,5),(1,7),(2,5),(2,6),(3,4),(3,5),(3,7),(4,5),(5,6),(5,7)}
5.{(1,2),(1,4),(1,6),(1,7),(2,5),(2,6),(2,7),(3,4),(3,5),(3,7),(4,5),(5,6),(6,7)}
Определите цикломатическое число графа