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

а)

б) Степенная последовательность: 6,4,4,4,4,4,2,2

в)

Матрица смежности

г)

Матрица инцидентности

д) Граф связен. Одна компонента связности.

е) Четыре простых цикла: 1,2,5; 1,5,6; 1,6,4; 4,8,7

ж)

Воспользуемся алгоритмом Крускала. Отметим два ребра наименьшего веса 1

Из трех ребер веса 2 лишь добавление двух не приводит к образованию циклов

Из двух ребер веса 3 лишь добавление одного не приводит к образованию циклов

Из трех ребер длины 5 одно приводит к образованию цикла, а добавление двух других одновременно приводит к появлению цикла. Добавим ребро номер 11.

Добави...