Инд работа6(остов графа)

Индивидуальная работа № 6

Деревья. Остов графа. Цикломатическое число графа.

Цикловой базис.

Для выполнения и защиты индивидуальной работы №6 необходимо изучить теоретический материал по данной теме.

Перечень основных вопросов по шестой индивидуальной работе:

1. Определения дерева, леса, корневого дерева.

2. Основные свойства деревьев.

3. Определения остова графа, хорды, цикломатического числа графа. Цикломатическое число дерева, леса. Построение остова графа.

4. Определение базиса циклов графа и его построение. Матрица базисных циклов.

1. Граф задан своей матрицей смежности. Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа. Выразить какой-либо цикл графа через базисные циклы. Составить матрицу базисных циклов.

I II III IV

V VI VII VIII

IX X

2. Из графа (см №1) выделить произвольный подграф с количеством ребер не менее 6, являющийся деревом. Найти диаметр, радиус, центр данного дерева. Найти цикломатическое число данного дерева.

3. Из графа (см№1) выделить подграф, у которого цикломатическое число: а) равно 1, б)равно 2. Для каждого полученного графа записать базис циклов графа, составить матрицы смежности и матрицы базисных циклов.