Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


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

Тип Реферат
Предмет Математика
Просмотров
1285
Размер файла
83 б
Поделиться

Ознакомительный фрагмент работы:

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

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

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

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

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

X3

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

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

X7

G1P(X1P,A1P) G2P(X2P,A2P)

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

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

11)=2 ; 21)=2 ; (х1)=4 ;

12)=2 ; 22)=2 ; (х2)=4 ;

13)=2 ; 23)=2 ; (х3)=4 ;

14)=2 ; 24)=2 ; (х4)=4 ;

15)=2 ; 25)=2 ; (х5)=4 ;

16)=2 ; 26)=2 ; (х6)=4 ;

17)=2 ; 27)=2 ; (х7)=4 ;

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

11)=2 ; 21)=2 ; (х1)=4 ;

12)=2 ; 22)=2 ; (х2)=4 ;

13)=3 ; 23)=2 ; (х3)=4 ;

14)=2 ; 24)=2 ; (х4)=4 ;

15)=2 ; 25)=2 ; (х5)=4 ;

16)=2 ; 26)=2 ; (х6)=4 ;

17)=2 ; 27)=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


Нет нужной работы в каталоге?

Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
История
Экономика
icon
146580
рейтинг
icon
3109
работ сдано
icon
1344
отзывов
avatar
Математика
Физика
История
icon
142254
рейтинг
icon
5881
работ сдано
icon
2654
отзывов
avatar
Химия
Экономика
Биология
icon
95082
рейтинг
icon
2030
работ сдано
icon
1273
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
53 940 оценок star star star star star
среднее 4.9 из 5
РГСУ
Получила за реферат 38 из 40 баллов. Огромное спасибо за работу, без доработок и досрочно....
star star star star star
Московский Университет имени С.Ю. Витте
Спасибо огромное за качественно выполненную работу!!!Работа была выполнена как всегда рань...
star star star star star
ТОГУ
Очень хороший исполнитель советую всем! Две работы выполнил и обе на отлично. Спасибо боль...
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

онлайн тест

Онлайн-помощь, иностранный язык

Срок сдачи к 31 июля

1 минуту назад

Решить 3 задачи по психологии

Решение задач, Психология

Срок сдачи к 24 июля

2 минуты назад

Отчет, НПС №41

Отчет по практике, Нефтегазовое дело

Срок сдачи к 17 июля

2 минуты назад

Тема: анализ предвзятости в моделях gpt и методы её уменьшения

Курсовая, Искусственный интеллект

Срок сдачи к 18 июля

2 минуты назад

лаб №2.2 измерение

Лабораторная, Геодезия

Срок сдачи к 15 июля

4 минуты назад

Нестандартные отели, 40страниц, больше книг, сайтов

Курсовая, туризм

Срок сдачи к 16 июля

4 минуты назад

2. Изучить заданную статью https://www. mdpi

Реферат, компьютерные сети

Срок сдачи к 16 июля

5 минут назад

Отчет от вожатой в школе

Отчет по практике, Педагогика

Срок сдачи к 31 июля

5 минут назад

Две самостоятельные работы по птицам

Лабораторная, зоология

Срок сдачи к 13 июля

5 минут назад

Отчет

Отчет по практике, Юриспруденция

Срок сдачи к 16 июля

6 минут назад

Самостоятельная работа по ботанике

Лабораторная, Ботаника

Срок сдачи к 13 июля

6 минут назад

за 800 руб

Другое, Психология

Срок сдачи к 14 июля

7 минут назад

Написать дипломную работу

Диплом, аэронавигация

Срок сдачи к 31 июля

8 минут назад

Написать научную статью

Статья, аэронавигация

Срок сдачи к 31 июля

8 минут назад
9 минут назад

Экзамен

Тест дистанционно, управление человеческими ресурсами

Срок сдачи к 17 июля

9 минут назад

Решить 4 вопроса

Контрольная, Английский язык

Срок сдачи к 15 июля

9 минут назад

дипломный проект

Диплом, строительство

Срок сдачи к 5 авг.

11 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно