Спасибо огромное за выполненную работу,все очень качественно и быстро)))
Сандра
ЛГПУ
Узнайте стоимость индивидуальной работы
это быстро и бесплатно
Оформите заказ сейчас и получите скидку 100 руб.!
Графы Основные понятия
Тип
Реферат
Предмет
Математика
Просмотров
1601
Размер файла
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
|
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’’)
|
Порожденные подграфы
|
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
Похожие работы
Нет нужной работы в каталоге?
Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников 
Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.
Цены ниже, чем в агентствах и у конкурентов
Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит
Бесплатные доработки и консультации
Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки
Гарантируем возврат
Если работа вас не устроит – мы вернем 100% суммы заказа
Техподдержка 7 дней в неделю
Наши менеджеры всегда на связи и оперативно решат любую проблему
Строгий отбор экспертов
К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»
1 000 +
Новых работ ежедневно
Требуются доработки?
Они включены в стоимость работы 
Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован 
Иванна
Математика
История
Экономика
159599
рейтинг
рейтинг
3275
работ сдано
работ сдано
1404
отзывов
отзывов
Ludmila
Математика
Физика
История
157252
рейтинг
рейтинг
6079
работ сдано
работ сдано
2741
отзывов
отзывов
Svetlana
Химия
Экономика
Биология
105734
рейтинг
рейтинг
2110
работ сдано
работ сдано
1318
отзывов
отзывов
Константин Николаевич
Высшая математика
Информатика
Геодезия
62710
рейтинг
рейтинг
1046
работ сдано
работ сдано
598
отзывов
отзывов
Отзывы студентов о нашей работе
67 246 оценок
среднее 4.9 из 5
Сандра
ЛГПУ
Спасибо огромное за выполненную работу,все очень качественно и быстро)))
Анастасия
Финансовый университет при правительстве рф
Великолепно выполнения работа по трейдингу. Инвестиционный портфель.
Преподаватель отмети...
Юлия
Московский городской педагогический университет
реферат написан в соответствии со всеми критериями, у преподавателя вопросов не возникло, ...
Великолепно выполнения работа по трейдингу. Инвестиционный портфель.
Преподаватель отметил интересный подход к самому заданию. Немного сложно выполнена работа, если заказываете у исполнителя - то нужно хотя бы разбираться в предмете. Хотя в работе большая часть максимально доходчиво объяснялась. Однозначно рекомендую исполнителя
Анастасия
Финансовый университет при правительстве рф
реферат написан в соответствии со всеми критериями, у преподавателя вопросов не возникло, все засчитали. с заказом справились на 2 часа раньше, всем рекомендую данного эксперта ;)
Юлия
Московский городской педагогический университет
Последние размещённые задания
Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн 
Театрализованная деятельность как средство развития общения старших дошкольников со сверстниками.
Диплом, Педагогика и психология
Срок сдачи к 1 окт.
1 минуту назад
трассировка печатной платы, размещение всех компонентов на ней
Отчет по практике, электроника
Срок сдачи к 3 авг.
11 минут назад
11 минут назад
Сделать курсовую с рисунками на А3, далее см
Курсовая, Теория механизмов и машин (ТММ), механика
Срок сдачи к 1 сент.
11 минут назад
Написать отчет по практике.
Отчет по практике, Строительство и эксплуатация зданий и сооружений
Срок сдачи к 17 авг.
11 минут назад
Глубокая доработка курсовой по социологии: «Студенческая молодёжь в цифровой среде: освоение и практики использования»
Курсовая, Социология
Срок сдачи к 5 авг.
11 минут назад
11 минут назад
Здравствуйте! Мне нужно написать статью в журнале Scopus Q2 под этим...
Статья, Нефтегазовое дело
Срок сдачи к 9 авг.
11 минут назад
11 минут назад
11 минут назад
11 минут назад
Контрольная по базам данных (ответ в ворде + БД в Access)
Контрольная, Базы данных и экспертные системы
Срок сдачи к 6 авг.
11 минут назад
11 минут назад
11 минут назад
Расчет несимметричных трехфазных электрических цепей
Решение задач, Электроника и электротехника
Срок сдачи к 20 авг.
11 минут назад
Тема: Пути совершенствованиясистемы налогообложения предприятия малого бизнеса.
Диплом, Экономика: Налоги И Налогообложения.
Срок сдачи к 1 сент.
11 минут назад
диплом Стилистический синтаксис английской прозы в аспекте перевода с...
Диплом, Лингвистика
Срок сдачи к 31 дек.
11 минут назад
11 минут назад
Закажи индивидуальную работу за 1 минуту!
Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.
«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами
Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:
Мы ВКонтакте 
Трейлер о сайте
Принимаем к оплате
© 2011—2026 Всё сдал!