Лабораторная работа: Графы. Основные понятия

Министерство образования и науки Российской Федерации

Курский государственный технический университет

Кафедра ПО ВТ и АС

Лабораторная работа № 1

Графы. Основные понятия

Выполнил: студент гр. ПО 62 Шиляков И.А.

Проверил: доцентТомакова Р.А.  

Курск 2007

Задание:

1.  По заданным матрицам смежности вершин восстановить графы.

2.  Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

3.  Найти и построить объединение, пересечение, кольцевую сумму заданных графов.

4.  Найти композицию графов  .

5.  Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

6.  Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

7.  Определить хроматические и цикломатические числа данных графов.

8.  Найти все базы графа.

9.  Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Выполнение:

1.     По заданным матрицам смежности вершин восстановить графы.