Вариант 76: задачи 126, 146. Граф задан списком ребер (каждый элемент списка – это тройка чисел

  • ID: 21957 
  • 3 страницы

Фрагмент работы:

Вариант 76: задачи 126, 146. Граф задан списком ребер (каждый элем…

Задача 126

Граф G задан списком ребер (каждый элемент списка – это тройка чисел: номера двух смежных вершин и вес ребра, их соединяющего). Требуется

а) Нарисовать граф G.

б) Найти степенную последовательность графа G.

в) Найти матрицу смежности графа G.

г) Обозначить ребра и найти матрицу инцидентности графа.

д) Определить количество компонент связности графа.

е) Найти четыре простых цикла.

ж) Найти минимальный остов графа и его вес.

Список ребер с весами

А)

Б) Степенью вершины v называется число инцидентных ей ребер.

В) матрица смежности A(G)

Г) матрица инцидентности I(G), элементы которой задаются следующим образом:

Д) Граф называется связным, если любые две вершины u и v в нем можно соединить (u,v) маршрутом.

Е) Если начало простой цепи совпадает с ее концом, то такая цепь называется простым циклом.

Ж) Остовом графа называется связный подграф без циклов, содержащий все вершины исходного графа.

Задача 146

Найти минимальный автомат, эквивалентный данному

0 1

1 4,1 9,0

2 5,0 8,1

3 7,0 4,1

4 8,1 5,1

5 4,1 3,0

6 1,0 6,1

7 5,0 2,1

8 1,0 6,1

9 6,0 4,1

Решение