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

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

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

Лабораторная работа № 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

 

X2

 

G2(X2,A2)


Информация о работе «Графы. Основные понятия»
Раздел: Математика
Количество знаков с пробелами: 6512
Количество таблиц: 11
Количество изображений: 15

Похожие работы

Скачать
11858
0
2

... можно строить схемы замещения реальных элементов цепи. 3. Топологические элементы схем Кроме рассмотренных элементов существуют топологические элементы, которые позволяют описать структуру цепи. Основные понятия: 1) Ветвь – соответствует участку цепи, в котором все элементы стоят последовательно, т.е. по которому протекает один и тот же ток. 2) Узел – место соединения трех и более ветвей ...

Скачать
15947
0
0

... В СМО без отказов заявка либо сразуназначается на обслуживание, если в момент ее поступлениясвободен хотя бы один канал обслуживания, либо безусловнопринимается в очередь на обслуживание. Потоки событий. Типы потоков   Переход системы в некоторое состояние Si называетсясобытием. В процессе работы система неоднократно  можетвозвращаться в состояние Si. Последовательность ...

Скачать
18316
0
0

... некая иерархическая структура. Третья идея ССА широкое использование графических нотаций, что облегчает понимание сложных систем. В результате можно дать следующее определение ССА: структурным системным анализом называется метод исследования, проектирования и описания сложных систем в виде иерархии "черных ящиков" с помощью графических средств. Другие принципы ССА Методология ССА строится ...

Скачать
27524
0
0

... ; система — это единое и неразрывное целое, являющееся целостной системой для нижестоящих иерархических уровней, имеются фиксированные связи системы с внешней средой. Рассмотрим основные понятия, характеризующие строение и функционирование систем. Под элементом принято понимать простейшую неделимую часть системы. Ответ на вопрос, что является такой частью, может быть неоднозначным и зависит от ...

0 комментариев


Наверх