Эйлеровы графы. Цикломатическое число

Практические задания

Задание 1

Для показанного на рисунке 9 указать гамильтонов и негамильтонов контуры.


Рисунок 9

Задание 2

В ориентированном графе, показанном на рисунке 10, найти контуры длины 3, 4, 5, гамильтов контур.


Рисунок 10

Задание 3

Для выполнения заданий необходимо определить и записать в таблице К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.

Таблица К1
a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16
                
a17a18a19a20a21a22a23a24a25a26a27a28a29a30a31a32
                
a33a34a35a36a37a38a39a40a41a42a43a44a45a46a47a48
                

Таблица К2
 
15
101520
 0 1 0 0 01 0 0 1 10 1 0 0 10 0 1 0 0
20+0 0 1 0 0 1 0 1 1 11 0 0 1 10 0 0 1 1
40+0 0 0 0 01 0 0 0 00 0 1 1 10 0 0 1 0
60+0 1 0 0 11 0 1 0 11 0 1 1 00 1 1 0 1
80+0 1 0 0 00 0 1 1 00 1 1 1 01 1 1 0 1
100+0 1 1 1 00 0 1 0 01 1 0 0 11 0 1 0 0
120+1 0 1 0 01 0 1 1 01 0 0 0 11 0 0 0 1

I) Символами а1 - а28 заполнить квадратную матрицу 7х7 (диагональные и наддиагональные элементы). Продолжить полученную треугольную матрицу симметричным образом.

a1a2a3a4a5a6a7
 a8a9a10a11a12a13
  a14a15a16a17a18
   a19a20a21a22
    a23a24a25
     a26a27
      a28

1) Рассматривая полученную матрицу как матрицу соседства вершин неориентированного графа G с вершинами 1, 2, 3, 4, 5, 6, 7, построить изображение графа. (Рекомендация: расположите вершины графа в вершинах правильного семиугольника).

2) Построить матрицу инциденций графа G.

3) Удалив петли (если они есть), найти цикломатическое число полученного графа.

II) Символами а11 - а38 заполнить наддиагональные элементы квадратной матрицы 8x8(диагональные элементы - нулевые). Продолжить полученную треугольную матрицу симметричным образом.

0a11a12a13a14a15a16a17
 0a18a19a20a21a22a23
  0a24a25a26a27a28
   0a29a30a31a32
    0a33a34a35
     0a36a37
      0a38
       0

1) Рассматривая полученную матрицу как матрицу соседства вершин

неориентированного графа G с вершинами 1 - 8, построить изображение графа G.

2) Определить цикломатическое число графа G.

3) Выделить какой-либо остов графа G.

4) Построить базис циклов графа G.

Задание 4

Постройте сомостоятельно остов и базис циклов неориентированных графов, заданных списком ребер:

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)}

Определите цикломатическое число графа