Графы и матрицы, связанные с графами: практическая часть

РефератПомощь в написанииУзнать стоимостьмоей работы

Задать некоторую ориентацию графа G. Для данного остова Т перенумеровать сначала ветви, а потом хорды графа. Найти матрицы инцидентности (В), фундаментальных циклов (Ф) и разрезов (К) графа G. Проверить условия ВФТ=0 и ФКТ=0; Так как элемент mij матрицы M=Ak равен числу маршрутов между вершинами Vi и Vj длины k, то искомое число маршрутов между V2 и V5 равно 3. (см. Приложение) Ответ: 3 маршрута… Читать ещё >

Графы и матрицы, связанные с графами: практическая часть (реферат, курсовая, диплом, контрольная)

Вариант № 2.

Даны следующие граф G и его остов T:

n = 7, m = 10.

Задачи:

Найти матрицу смежности графа G. С ее помощью найти число маршрутов из вершины V2 в вершину V5 длины 3;

Найти код Прюфера для остова.

Матрица смежности A размера n x n:


А.	V1.	V2.	V3.	V4.	V5.	V6.	V7.
V1.
V2.
V3.
V4.
V5.
V6.
V7.

Графы и матрицы, связанные с графами: практическая часть.

Так как элемент mij матрицы M=Ak равен числу маршрутов между вершинами Vi и Vj длины k, то искомое число маршрутов между V2 и V5 равно 3. (см. Приложение) Ответ: 3 маршрута.

Зададим ориентацию графа и пронумеруем ветви и хорды:

Матрица инцидентности размера n x m:


В.	E1.	E2.	E3.	E4.	E5.	E6.	E7.	E8.	E9.	E10.
V1.			— 1.
V2.	— 1.			— 1.
V3.		— 1.
V4.
V5.						— 1.
V6.							— 1.		— 1.
V7.								— 1.		— 1.

Матрица фундаментальных циклов размера (m-n+1) x m:


Ф.	E1.	E2.	E3.	E4.	E5.	E6.	E7.	E8.	E9.	E10.
Ф1.				— 1.
Ф2.					— 1.
Ф3.							— 1.
Ф4.								— 1.

Фундаментальные разрезы:

К1 К2 K3 K4.

{E1, E3} {E1, E2, E4} {E2, E5} {E6, E9}.

K5 K6.

{E7, E9, E10} {E8, E10}.

Матрица фундаментальных разрезов размера (n-1) x m:


К.	E1.	E2.	E3.	E4.	E5.	E6.	E7.	E8.	E9.	E10.
К1.			— 1.
К2.	— 1.			— 1.
К3.		— 1.			— 1.
К4.									— 1.
К5.										— 1.
K6.

Условия ВФТ=0 и ФКТ=0 проверены в системе Matlab.

граф матрица прюфер matlab.

Листинг кода Matlab:

%Матрица смежности:

A=[ 0 1 0 1 0 0 0;

1 0 1 1 0 0 0;

0 1 0 1 0 0 0;

1 1 1 0 1 1 1;

0 0 0 1 0 1 0;

0 0 0 1 1 0 1;

0 0 0 1 0 1 0; ];

%Матрица инцидентности:

B=[ 1 0 -1 0 0 0 0 0 0 0;

— 1 1 0 -1 0 0 0 0 0 0;

0 -1 0 0 -1 0 0 0 0 0;

0 0 1 1 1 1 1 1 0 0;

0 0 0 0 0 -1 0 0 1 0;

0 0 0 0 0 0 -1 0 -1 1;

0 0 0 0 0 0 0 -1 0 -1; ];

%Матрица фундаментальных циклов:

F=[ 1 0 1 -1 0 0 0 0 0 0;

0 1 0 1 -1 0 0 0 0 0;

0 0 0 0 0 1 -1 0 1 0;

0 0 0 0 0 0 1 -1 0 1; ];

%Матрица фундаментальных разрезов:

K=[ 1 0 -1 0 0 0 0 0 0 0;

— 1 1 0 -1 0 0 0 0 0 0;

0 -1 0 0 -1 0 0 0 0 0;

0 0 0 0 0 1 0 0 -1 0;

0 0 0 0 0 0 1 0 1 -1;

0 0 0 0 0 0 0 1 0 1; ];

%Нахождение числа маршрутов:

M=A³.

m=M (2,5).

%Проверка условий В (F')=0 и F (К')=0:

C1=B*(F').

C2=F*(K').

Результаты:

M =.

2 5 2 8 2 3 2.

5 4 5 8 3 4 3.

2 5 2 8 2 3 2.

8 8 8 8 8 8 8.

2 3 2 8 2 5 2.

3 4 3 8 5 4 5.

2 3 2 8 2 5 2.

m =.

C1 =.

0 0 0 0.

C2 =.

0 0 0 0 0 0.

Показать весь текст

Заполнить форму текущей работой

Другие работы

Пестициды. Общая характеристика, классификация. Правила работы и техника безопасности

В основу другой токсикологической классификации положена летальная доза препарата (в расчете на 70 кг массы человека): нетоксичные (LD более 1000 г), слаботоксичные (500−1000г), среднетоксичные (28−500 г), очень токсичные (4−28г), чрезвычайно токсичные (0,5−4 г), супертоксичные (менее 0,5 г) Основными объектами судебно-химического исследования при отравлении ядохимикатами являются биологические…

Реферат