Вариант 76: задачи 126, 146

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

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

Задача 126

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

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

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

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

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

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

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

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

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

(1,3,6), (1,7,8), (2,6,5),

(2,8,4), (3,5,3), (3,6,9),

(3,7,4), (4,7,5), (4,8,2),

(5,6,1), (5,7,3), (5,8,8),

(6,7,4), (7,8,1).

А)

[image]

Б) называется число инцидентных ей ребер. Степень вершины обозначается .Последовательность степеней вершин графа, записанных в каком-либо порядке, называется степенной последовательностью. Найдем степенную последовательность для графа . Выпишем степени всех вершин графа в соответствии с их номерами

(2,2,4,2,4,4,5,5)

В)

[image]

[image]

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

[image]

[image]

В каждом столбце матрицы инцидентности только два элемента отличные от 0 (или один, если ребро является петлей).

Д) Граф называется , если любые две вершины и в нем можно соединить () маршрутом. Легко видеть, что отношение связности на множестве вершин является отношением эквивалентности. Данное отношение разбивает множество вершин графа на классы, объединяющие вершины, которые можно связать друг с другом маршрутом. Такие классы называются .

Графсвязный, т.к. любые 2 его вершины можно соединить маршрутом. Т.е. онимеет одну компоненту связности.

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

Маршрут называется если в нем нет совпадающих ребер и

Вершин, кроме, может быть, начала и конца цепи.

(1,3,7,1), (5,6,8,5), (4,7,1,3,6,8,4), (5,6,2,8,5).

Ж) графа называется связный подграф без циклов, содержащий все вершины исходного графа. Подграф содержит часть или все ребра исходного графа. Задача о минимальном остове формулируется следующим образом: во взвешенном связном графе найти остов минимального веса.

Построение остова начнем с ребра (). Порядок присоединения ребер к остову (2,8),(2,6),(5,6),(3,5),(4,7),(1,3)

1+4+5+1+3+5+6=25

Задача 146

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