Операции на графах
Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 27.11.2008 |
| Размер файла | 106,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2. G1(G2G3) = (G1G2)G3.
Рассмотрим выполнение операции произведения графов в матричной форме.
Пусть G1(X,E1) и G2(Y,E2) - два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1G2 имеет nxny вершин, а его матрица смежности вершин - квадратная матрица размером (nxny) (nx ny). Обозначим через a = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z=(xiyj) c z=(xkyl). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
a =a(ij)(kl) = a1,ik a2,jl, (3)
де a1,ik, a1,ik - элементы матрицы смежности вершин графов G1 и G2 соответственно.
Пример 5. Выполнить операцию произведения на графах, приведенных на рис. 5.
Составим матрицы смежности вершин исходных графов.
|
x1 |
x2 |
y1 |
y2 |
y3 |
|||||||
|
x1 |
0 |
1 |
y1 |
1 |
1 |
0 |
|||||
|
A1 |
= |
x2 |
1 |
0 |
A2 |
= |
y2 |
0 |
0 |
1 |
|
|
y3 |
0 |
1 |
0 |
Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).
|
x1y1 |
x1y2 |
x1y3 |
x2y1 |
x2y2 |
x2y3 |
||||
|
x1y1 |
a1,11 a2,11 |
a1,11a2,12 |
a1,11 a2,13 |
a1,12a2,11 |
a1,12 a2,12 |
a1,12 a2,13 |
|||
|
x1y2 |
a1,11 a2,21 |
a1,11 a2,22 |
a1,11 a2,23 |
a1,12 a2,21 |
a1,12 a2,22 |
a1,12 a2,23 |
|||
|
A |
= |
x1y3 |
a1,11 a2,21 |
a1,11 a2,22 |
a1,11 a2,23 |
a1,12 a2,31 |
a1,12 a2,32 |
a1,12 a2,33 |
|
|
x2y1 |
a1,21 a2,11 |
a1,21 a2,12 |
a1,21 a2,13 |
a1,22 a2,11 |
a1,22 a2,12 |
a1,22 a2,13 |
|||
|
x2y2 |
a1,21 a2,21 |
a1,21 a2,22 |
a1,21 a2,23 |
a1,12 a2,21 |
a1,12 a2,22 |
A1,12 a2,23 |
|||
|
x2y3 |
a1,21 a2,31 |
a1,21 a2,32 |
a1,21 a2,33 |
a1,22 a2,31 |
a1,12 a2,32 |
A1,12 a2,33 |
Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A2 на один из элементов a1,ij матрицы A1. С учетом этого матрицу A можно представить так:
|
x1y1 |
x1y2 |
x1y3 |
x2y1 |
x2y2 |
x2y3 |
||||
|
x1y1 |
a1,11A2 |
a1,12A2 |
|||||||
|
x1y2 |
|||||||||
|
A |
= |
x1y3 |
|||||||
|
x2y1 |
a1,21A2 |
a1,22A2 |
|||||||
|
x2y2 |
|||||||||
|
x2y3 |
Таким образом, матрица смежности вершин графа G1G2 имеет вид:
|
x1y1 |
x1y2 |
x1y3 |
x2y1 |
x2y2 |
x2y3 |
||||
|
x1y1 |
0 |
0 |
0 |
1 |
1 |
0 |
|||
|
x1y2 |
0 |
0 |
0 |
0 |
0 |
1 |
|||
|
A |
= |
x1y3 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
x2y1 |
1 |
1 |
0 |
0 |
0 |
0 |
|||
|
x2y2 |
0 |
0 |
1 |
0 |
0 |
0 |
|||
|
x2y3 |
0 |
1 |
0 |
0 |
0 |
0 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1G2, представленный на рис. 5.
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука, Физматлит, 2000.- 544 с.- ISBN 5-02-015238-2.
3. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.- 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).
Подобные документы
Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Множеством именуется некоторая совокупность элементов, объединенных по какому-либо признаку. Над множествами определяют операции, во многом сходные с арифметическими. Операции над множествами интерпретируют геометрически с помощью диаграмм Эйлера-Венна.
реферат [15,8 K], добавлен 03.02.2009Понятие множества, его обозначения. Операции объединения, пересечения и дополнения множеств. Свойства счетных множеств. История развития представлений о числе, появление множества натуральных, рациональных и действительных чисел, операции с ними.
курсовая работа [358,3 K], добавлен 07.12.2012Особенности системы индексных обозначений. Специфика суммирования в тензорной алгебре. Главные операции в алгебре, которые называются сложением, умножением и свертыванием. Применение операции внутреннего умножения. Симметричные и антисимметричные объекты.
реферат [345,7 K], добавлен 07.12.2009Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Сущность теории графов и ее применение на современном этапе в различных отраслях науки и техники, особенно в экономике и социологии. Понятие дерева, его разновидности, характерные свойства. Операции, совершаемые над графами и возможности их реализации.
контрольная работа [1,6 M], добавлен 08.12.2009Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Определение понятия множеств Г. Кантора, их примеры и обозначения. Способы задания, включение и равенство множеств, операции над ними: объединение, пересечения, разность, дополнение, их определение и наглядное представление на диаграмме Эйлера-Венна.
реферат [70,9 K], добавлен 11.03.2009Сущность теории множеств и особенности ее практического применения. Операции над множествами и их главные закономерности. Порядок нахождения области определения функции, участков ее возрастания и убывания. Определение вероятности исследуемого действия.
контрольная работа [46,5 K], добавлен 02.12.2011
