Сайт в помощь студенту Грамоте учиться – всегда пригодится

Cкачать полностью

Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС

 

 

 

 

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

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

 

 

 

 

 

 

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

 

 

 

 

 

 

Курск 2007


Задание:

  1. По заданным матрицам смежности вершин восстановить графы.
  2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
  3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
  4. Найти композицию графов  .
  5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
  6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
  7. Определить хроматические и цикломатические числа данных графов.
  8. Найти все базы графа.
  9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Выполнение:

 

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

 

x1

x2

x3

x4

x5

x6

x7

x1

0

1

0

0

0

0

1

x2

0

0

1

0

0

1

0

x3

0

1

0

1

0

0

0

x4

1

0

0

0

1

0

0

x5

1

0

0

0

0

0

1

x6

0

0

1

1

0

0

0

x7

0

0

0

0

1

1

0

A1

X2

 

G1(X1,A1)

 

x1

x2

x3

x4

x5

x6

x7

x1

0

1

1

0

0

0

0

x2

0

0

0

1

1

0

0

x3

0

1

0

0

0

0

1

x4

1

0

0

0

1

0

0

x5

0

0

0

0

0

1

1

x6

1

0

0

1

0

0

0

x7

0

0

1

0

0

1

0

A2