Навигация
Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 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
|
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
|
G2(X2,A2)
Похожие работы
... можно строить схемы замещения реальных элементов цепи. 3. Топологические элементы схем Кроме рассмотренных элементов существуют топологические элементы, которые позволяют описать структуру цепи. Основные понятия: 1) Ветвь – соответствует участку цепи, в котором все элементы стоят последовательно, т.е. по которому протекает один и тот же ток. 2) Узел – место соединения трех и более ветвей ...
... В СМО без отказов заявка либо сразуназначается на обслуживание, если в момент ее поступлениясвободен хотя бы один канал обслуживания, либо безусловнопринимается в очередь на обслуживание. Потоки событий. Типы потоков Переход системы в некоторое состояние Si называетсясобытием. В процессе работы система неоднократно можетвозвращаться в состояние Si. Последовательность ...
... некая иерархическая структура. Третья идея ССА широкое использование графических нотаций, что облегчает понимание сложных систем. В результате можно дать следующее определение ССА: структурным системным анализом называется метод исследования, проектирования и описания сложных систем в виде иерархии "черных ящиков" с помощью графических средств. Другие принципы ССА Методология ССА строится ...
... ; система — это единое и неразрывное целое, являющееся целостной системой для нижестоящих иерархических уровней, имеются фиксированные связи системы с внешней средой. Рассмотрим основные понятия, характеризующие строение и функционирование систем. Под элементом принято понимать простейшую неделимую часть системы. Ответ на вопрос, что является такой частью, может быть неоднозначным и зависит от ...
0 комментариев