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

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

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

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

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

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

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

Проверил: доцентТомакова Р.А.

Курск 2007

Задание:

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

2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.

4. Найти композицию графов .

5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

7. Определить хроматические и цикломатические числа данных графов.

8. Найти все базы графа.

9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Выполнение:

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


	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₁	0	1	0	0	0	0	1
x₂	0	0	1	0	0	1	0
x₃	0	1	0	1	0	0	0
x₄	1	0	0	0	1	0	0
x₅	1	0	0	0	0	0	1
x₆	0	0	1	1	0	0	0
x₇	0	0	0	0	1	1	0

A₁

G₁(X₁,A₁)


	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₁	0	1	1	0	0	0	0
x₂	0	0	0	1	1	0	0
x₃	0	1	0	0	0	0	1
x₄	1	0	0	0	1	0	0
x₅	0	0	0	0	0	1	1
x₆	1	0	0	1	0	0	0
x₇	0	0	1	0	0	1	0

A₂

G₂(X₂,A₂)

2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.


	а₁	а₂	а₃	а₄	а₅	а₆	а₇	а₈	а₉	а₁₀	а₁₁	а₁₂	а₁₃	а₁₄
а₁	0	1	1	1	1	0	1	0	1	0	0	0	0	0
а₂	1	0	0	0	0	0	1	0	1	1	0	0	1	1
а₃	1	0	0	1	1	1	0	0	0	0	1	0	0	0
а₄	1	0	1	0	1	0	0	0	0	0	1	1	0	1
а₅	1	0	1	1	0	1	0	0	0	0	1	0	0	0
а₆	0	0	1	0	1	0	1	1	0	0	1	1	0	0
а₇	1	1	0	0	0	1	0	1	1	0	0	1	0	0
а₈	0	0	0	0	0	1	1	0	1	1	0	1	1	0
а₉	1	1	0	0	0	0	1	1	0	1	0	0	1	0
а₁₀	0	1	0	0	0	0	0	1	1	0	0	0	1	1
а₁₁	0	0	1	1	1	1	0	0	0	0	0	1	0	1
а₁₂	0	0	0	1	0	1	1	1	0	0	1	0	0	1
а₁₃	0	1	0	0	0	0	0	1	1	1	0	0	0	1
а₁₄	0	1	0	1	0	0	0	0	0	1	1	1	1	0

B₁


	а₁	а₂	а₃	а₄	а₅	а₆	а₇	а₈	а₉	а₁₀	а₁₁	а₁₂	а₁₃	а₁₄
а₁	0	1	0	1	1	1	1	0	1	0	0	0	0	0
а₂	1	0	1	1	1	1	0	1	0	0	0	0	0	0
а₃	0	1	0	1	0	0	1	1	0	0	0	1	1	0
а₄	1	1	1	0	0	0	1	1	1	0	0	0	0	0
а₅	1	1	0	0	0	1	0	0	0	1	1	0	0	0
а₆	1	1	0	0	1	0	0	0	0	1	1	0	0	0
а₇	1	0	1	1	0	0	0	0	1	0	0	1	1	0
а₈	0	1	1	1	0	0	0	0	0	0	1	0	1	1
а₉	1	0	0	1	0	0	1	0	0	1	0	1	0	1
а₁₀	0	0	0	0	1	1	0	0	1	0	1	1	0	1
а₁₁	0	0	0	0	1	1	0	1	0	1	0	0	1	1
а₁₂	0	0	1	0	0	0	1	0	1	1	0	0	1	1
а₁₃	0	0	1	0	0	0	1	1	0	0	1	1	0	1
а₁₄	0	0	0	0	0	0	0	1	1	1	1	1	1	0

B₂


	а₁	а₂	а₃	а₄	а₅	а₆	а₇	а₈	а₉	а₁₀	а₁₁	а₁₂	а₁₃	а₁₄
x₁	1	1	0	0	0	0	-1	0	-1	0	0	0	0	0
x₂	-1	0	1	1	-1	0	0	0	0	0	0	0	0	0
x₃	0	0	-1	0	1	1	0	0	0	0	-1	0	0	0
x₄	0	0	0	0	0	-1	1	1	0	0	0	-1	0	0
x₅	0	0	0	0	0	0	0	-1	1	1	0	0	-1	0
x₆	0	0	0	-1	0	0	0	0	0	0	1	1	0	-1
x₇	0	-1	0	0	0	0	0	0	0	-1	0	0	1	1

S₁


	а₁	а₂	а₃	а₄	а₅	а₆	а₇	а₈	а₉	а₁₀	а₁₁	а₁₂	а₁₃	а₁₄
x₁	1	0	0	1	0	0	-1	0	-1	0	0	0	0	0
x₂	0	-1	1	-1	0	0	0	1	0	0	0	0	0	0
x₃	-1	1	0	0	-1	1	0	0	0	0	0	0	0	0
x₄	0	0	-1	0	0	0	1	0	0	0	0	-1	1	0
x₅	0	0	0	0	0	0	0	-1	0	0	1	0	-1	1
x₆	0	0	0	0	0	0	0	0	1	-1	0	1	0	-1
x₇	0	0	0	0	1	-1	0	0	0	1	-1	0	0	0

S₂


	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₁	1	1	1	1	1	1	1
x₂	1	1	1	1	1	1	1
x₃	1	1	1	1	1	1	1
x₄	1	1	1	1	1	1	1
x₅	1	1	1	1	1	1	1
x₆	1	1	1	1	1	1	1
x₇	1	1	1	1	1	1	1
	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₁	1	1	1	1	1	1	1
x₂	1	1	1	1	1	1	1
x₃	1	1	1	1	1	1	1
x₄	1	1	1	1	1	1	1
x₅	1	1	1	1	1	1	1
x₆	1	1	1	1	1	1	1
x₇	1	1	1	1	1	1	1

R₁ R₂


	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₁	1	1	1	1	1	1	1
x₂	1	1	1	1	1	1	1
x₃	1	1	1	1	1	1	1
x₄	1	1	1	1	1	1	1
x₅	1	1	1	1	1	1	1
x₆	1	1	1	1	1	1	1
x₇	1	1	1	1	1	1	1
	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₁	1	1	1	1	1	1	1
x₂	1	1	1	1	1	1	1
x₃	1	1	1	1	1	1	1
x₄	1	1	1	1	1	1	1
x₅	1	1	1	1	1	1	1
x₆	1	1	1	1	1	1	1
x₇	1	1	1	1	1	1	1

Q₁ Q₂

3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.

Объединение графов

G₃(X₃,A₃)=G₁(X₁,A₁) YG₂(X₂,A₂); X₃= X₁YX_2, A₃= A₁YA₂

Пересечение графов

G₃(X₃,A₃)=G₁(X₁,A₁) ?G₂(X₂,A₂); X₃= X₁?X_2, A₃= A₁?A₂

Кольцевая сумма графов

G₃(X₃,A₃)=G₁(X₁,A₁)G₂(X₂,A₂)

4. Найти и построить композицию графов .

G₁(Х)

G₂(Х)

G₁(G₂(Х))

G₂(G₁(Х))

x₁

(x₁,x₂), (x₁,x₇)

(x₁,x₂), (x₁,x₃)

(x₁,x₃), (x₁,x₆),

(x₁,x₂), (x₁,x₄),

(x₁,x₄), (x₁,x₅),

(x₁,x₃), (x₁,x₆),

x₂

(x₂,x₃),

(x₂,x₆)

(x₂,x₄),

(x₂,x₅)

(x₂,x₁), (x₂,x₅),

(x₂,x₇),

(x₂,x₂), (x₂,x₇),

(x₂,x₁), (x₂,x₄),

x₃

(x₃,x₂),

(x₃,x₄)

(x₃,x₂),

(x₃,x₇)

(x₃,x₃), (x₃,x₆),

(x₃,x₅),

(x₃,x₄), (x₃,x₅),

(x₃,x₁),

x₄

(x₄,x₁), (x₄,x₅)

(x₄,x₂), (x₄,x₇),

(x₄,x₁),

(x₄,x₂), (x₄,x₃),

(x₄,x₆), (x₄,x₇),

x₅

(x₅,x₁), (x₅,x₇)

(x₅,x₆), (x₅,x₇)

(x₅,x₃), (x₅,x₄),</ p>

(x₅,x₅), (x₅,x₆),

(x₅,x₂), (x₅,x₃), (x₅,x₆),
x₆	(x₆,x₃), (x₆,x₄)	(x₆,x₁), (x₆,x₄)	(x₆,x₂), (x₆,x₇), (x₆,x₁), (x₆,x₅),	(x₆,x₂), (x₆,x₇), (x₆,x₁), (x₆,x₅),
x₇	(x₇,x₅), (x₇,x₆)	(x₇,x₃), (x₇,x₆)	(x₇,x₂), (x₇,x₄), (x₇,x₃),	(x₇,x₆), (x₇,x₇), (x₇,x₁), (x₇,x₄),

G₁(G₂(Х))

G₂(G₁(Х))

5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

Остовные подграфы

G₁(X₁,A₁)

G₂(X₂,A₂)

Произвольные подграфы

G₁ (X₁,A₁)

G₂ (X₂,A₂)

Порожденные подграфы

G_1P(X_1P,A_1P) G_2P(X_2P,A_2P)

Локальные степени графа G₁

₁ (х₁)=2 ; ₂ (х₁)=2 ; (х₁)=4 ;

₁ (х₂)=2 ; ₂ (х₂)=2 ; (х₂)=4 ;

₁ (х₃)=2 ; ₂ (х₃)=2 ; (х₃)=4 ;

₁ (х₄)=2 ; ₂ (х₄)=2 ; (х₄)=4 ;

₁ (х₅)=2 ; ₂ (х₅)=2 ; (х₅)=4 ;

₁ (х₆)=2 ; ₂ (х₆)=2 ; (х₆)=4 ;

₁ (х₇)=2 ; ₂ (х₇)=2 ; (х₇)=4 ;

Локальные степени графа G₂

₁ (х₁)=2 ; ₂ (х₁)=2 ; (х₁)=4 ;

₁ (х₂)=2 ; ₂ (х₂)=2 ; (х₂)=4 ;

₁ (х₃)=3 ; ₂ (х₃)=2 ; (х₃)=4 ;

₁ (х₄)=2 ; ₂ (х₄)=2 ; (х₄)=4 ;

₁ (х₅)=2 ; ₂ (х₅)=2 ; (х₅)=4 ;

₁ (х₆)=2 ; ₂ (х₆)=2 ; (х₆)=4 ;

₁ (х₇)=2 ; ₂ (х₇)=2 ; (х₇)=4 ;

Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.

Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.

7. Определить хроматические и цикломатические числа данных графов.

Хроматическое число г для графа G₁ = 4

Хроматическое число г для графа G₂ = 4

Цикломатические числа графов

V(G₁)=m-n+r, где m - число рёбер (дуг);

n - число вершин;

r - число компонент связности.

V(G₁)=14-7+1=8;

V(G₂)=14-7+1=8;

8. Найти все базы графа.

Базы графа G₁

B₁={x₁}

B₂={x₂}

B₃={x₃}

B₄={x₄}

B₅={x₅}

B₆={x₆}

B₇={x₇}

Базы графа G₂

B₁={x₁}

B₂={x₂}

B₃={x₃}

B₄={x₄}

B₅={x₅}

B₆={x₆}

B₇={x₇}

9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Сильные компоненты связности G₁

СК={x₁, x₂, x₃, x₄, x₅, x₆, x₇}

Сильные компоненты связности G₂

СК={x₁, x₂, x₃, x₄, x₅, x₆, x₇}

Конденсация графа G₁ Конденсация графа G₂

Не сдавайте скачаную работу преподавателю!

Данную контрольную работу Вы можете использовать для выполнения своих заданий.

Доработать Узнать цену работы по вашей теме

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Заказать работу:

!	Курсовая работа
!	Дипломная работа
!	Реферат
!	Решение задач
!	Отчет по практике
!	Контрольная работа

Другие популярные контрольные работы:

Контрольная работа	Концепция информатизации Российской Федерации
Контрольная работа	Причины агрессивного поведения. Методы работы с агрессивными детьми
Контрольная работа	Алгоритм выбора и реализации предпринимательской идеи
Контрольная работа	Системы управления взаимоотношения с клиентами
Контрольная работа	Учет материальных затрат в бухгалтерском учете
Контрольная работа	Геополитическое положение России
Контрольная работа	Особенности вознаграждения работников в организации
Контрольная работа	Виды запасов
Контрольная работа	Психоанализ
Контрольная работа	Экономико-географическая характеристика Печорского угольного бассейна 2

Сейчас смотрят :

Контрольная работа	Кадровый потенциал организации: проблемы формирования и развития
Контрольная работа	Вторая мировая война и Великая Отечественная война
Контрольная работа	Напівфабрикати з січеної натуральної і котлетної маси
Контрольная работа	Средние величины: виды, свойства, область применения
Контрольная работа	Семейное право

Контрольная работа по предмету "Математика"

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

Другие популярные контрольные работы:

Сейчас смотрят :