Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Лабораторная работа: Графы Основные понятия

Название: Графы Основные понятия
Раздел: Рефераты по математике
Тип: лабораторная работа Добавлен 13:10:06 23 июля 2010 Похожие работы
Просмотров: 30 Комментариев: 21 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать

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

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

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

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

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 = X1 YX2, A3 = A1 YA2

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

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 ’’)

X3

G2 ’’ (X2 ’’,A2 ’’)

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

X7

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита01:55:39 05 ноября 2021
.
.01:55:37 05 ноября 2021
.
.01:55:36 05 ноября 2021
.
.01:55:34 05 ноября 2021
.
.01:55:32 05 ноября 2021

Смотреть все комментарии (21)
Работы, похожие на Лабораторная работа: Графы Основные понятия

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(294399)
Комментарии (4230)
Copyright © 2005 - 2024 BestReferat.ru / реклама на сайте