Графы. Основные понятия
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
| Рубрика | Математика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 09.01.2009 |
| Размер файла | 85,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 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)
2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
|
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
||
|
а1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
а2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
а3 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
а4 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
а5 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
а6 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
а7 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
а8 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
а9 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
а10 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
а11 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
а12 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
а13 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
а14 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
B1
|
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
||
|
а1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
а2 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
а3 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
а4 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
а5 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
а6 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
а7 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
а8 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
|
а9 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
а10 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
а11 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
|
а12 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
а13 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
а14 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
B2
|
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
||
|
x1 |
1 |
1 |
0 |
0 |
0 |
0 |
-1 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
|
x2 |
-1 |
0 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
x3 |
0 |
0 |
-1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
|
|
x4 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
|
x5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
0 |
0 |
-1 |
0 |
|
|
x6 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
-1 |
|
|
x7 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
1 |
S1
|
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
||
|
x1 |
1 |
0 |
0 |
1 |
0 |
0 |
-1 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
|
x2 |
0 |
-1 |
1 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
x3 |
-1 |
1 |
0 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
x4 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
|
|
x5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
-1 |
1 |
|
|
x6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
1 |
0 |
-1 |
|
|
x7 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
S2
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||
|
x1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x3 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||
|
x1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x3 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
R1 R2
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||
|
x1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x3 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||
|
x1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x3 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
x7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Q1 Q2
3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
Объединение графов
G3(X3,A3)=G1(X1,A1) YG2(X2,A2); X3= X1YX2, A3= A1YA2
Пересечение графов
G3(X3,A3)=G1(X1,A1) ?G2(X2,A2); X3= X1?X2, A3= A1?A2
Кольцевая сумма графов
G3(X3,A3)=G1(X1,A1)G2(X2,A2)
4. Найти и построить композицию графов .
|
G1(Х) |
G2(Х) |
G1(G2(Х)) |
G2(G1(Х)) |
||
|
x1 |
(x1,x2), (x1,x7) |
(x1,x2), (x1,x3) |
(x1,x3), (x1,x6), (x1,x2), (x1,x4), |
(x1,x4), (x1,x5), (x1,x3), (x1,x6), |
|
|
x2 |
(x2,x3), (x2,x6) |
(x2,x4), (x2,x5) |
(x2,x1), (x2,x5), (x2,x7), |
(x2,x2), (x2,x7), (x2,x1), (x2,x4), |
|
|
x3 |
(x3,x2), (x3,x4) |
(x3,x2), (x3,x7) |
(x3,x3), (x3,x6), (x3,x5), |
(x3,x4), (x3,x5), (x3,x1), |
|
|
x4 |
(x4,x1), (x4,x5) |
(x4,x1), (x4,x5) |
(x4,x2), (x4,x7), (x4,x1), |
(x4,x2), (x4,x3), (x4,x6), (x4,x7), |
|
|
x5 |
(x5,x1), (x5,x7) |
(x5,x6), (x5,x7) |
(x5,x3), (x5,x4), (x5,x5), (x5,x6), |
(x5,x2), (x5,x3), (x5,x6), |
|
|
x6 |
(x6,x3), (x6,x4) |
(x6,x1), (x6,x4) |
(x6,x2), (x6,x7), (x6,x1), (x6,x5), |
(x6,x2), (x6,x7), (x6,x1), (x6,x5), |
|
|
x7 |
(x7,x5), (x7,x6) |
(x7,x3), (x7,x6) |
(x7,x2), (x7,x4), (x7,x3), |
(x7,x6), (x7,x7), (x7,x1), (x7,x4), |
G1(G2(Х))
G2(G1(Х))
5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
Остовные подграфы
G'1(X1,A1)
G'2(X2,A2)
Произвольные подграфы
G1'' (X1'',A1'')
G2'' (X2'',A2'')
Порожденные подграфы
G1P(X1P,A1P) G2P(X2P,A2P)
6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
Локальные степени графа G1
1 (х1)=2 ; 2 (х1)=2 ; (х1)=4 ;
1 (х2)=2 ; 2 (х2)=2 ; (х2)=4 ;
1 (х3)=2 ; 2 (х3)=2 ; (х3)=4 ;
1 (х4)=2 ; 2 (х4)=2 ; (х4)=4 ;
1 (х5)=2 ; 2 (х5)=2 ; (х5)=4 ;
1 (х6)=2 ; 2 (х6)=2 ; (х6)=4 ;
1 (х7)=2 ; 2 (х7)=2 ; (х7)=4 ;
Локальные степени графа G2
1 (х1)=2 ; 2 (х1)=2 ; (х1)=4 ;
1 (х2)=2 ; 2 (х2)=2 ; (х2)=4 ;
1 (х3)=3 ; 2 (х3)=2 ; (х3)=4 ;
1 (х4)=2 ; 2 (х4)=2 ; (х4)=4 ;
1 (х5)=2 ; 2 (х5)=2 ; (х5)=4 ;
1 (х6)=2 ; 2 (х6)=2 ; (х6)=4 ;
1 (х7)=2 ; 2 (х7)=2 ; (х7)=4 ;
Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.
Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.
7. Определить хроматические и цикломатические числа данных графов.
Хроматическое число г для графа G1 = 4
Хроматическое число г для графа G2 = 4
Цикломатические числа графов
V(G1)=m-n+r, где m - число рёбер (дуг);
n - число вершин;
r - число компонент связности.
V(G1)=14-7+1=8;
V(G2)=14-7+1=8;
8. Найти все базы графа.
Базы графа G1
B1={x1}
B2={x2}
B3={x3}
B4={x4}
B5={x5}
B6={x6}
B7={x7}
Базы графа G2
B1={x1}
B2={x2}
B3={x3}
B4={x4}
B5={x5}
B6={x6}
B7={x7}
9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.
Сильные компоненты связности G1
СК={x1, x2, x3, x4, x5, x6, x7}
Сильные компоненты связности G2
СК={x1, x2, x3, x4, x5, x6, x7}
Конденсация графа G1 Конденсация графа G2
Подобные документы
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011