Категория
Математика
Тип
реферат
Страницы
2 стр.
Дата
06.08.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
129484.zip — 107.83 kb
  • operacii-na-grafax_129484_1.rtf — 1184.52 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо




Текст работы

Admin
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
« Операции на графах
»
МИНСК, 2008
Операции на графах позволяют образовывать новые графы из н
е скольких более простых. В этом параграфе
будут рассмотрены операции на графах без параллельных ребер (дуг).
Объединение графов .
Пусть G 1 (X 1
,E 1 ) и G
2 (X 2 ,E
2 ) – произвольные графы. Объединением
G 1
G 2 графов G
1 и G 2
называется граф с множеством вершин X 1
X 2
, и с множ е ством ребер (дуг)
E 1 E
2 .
Рассмотрим операцию на примере графов G 1
(X 1 ,E 1 ) и G 2 (X
2 ,E 2 ) , приведе н ных на рис. 4.1. Множества вершин первого и второго графов соответс т венно равны X 1 = x 1
, x 2 , x 3
и X 2 = x
2 , x 3 , x 4
, а множество вершин резул ь
тирующего графа определится как X = X
1 X 2
= x 1 , x 2
, x 3 , x 4
. Аналогично определяем множества дуг графа:
E 1 = (x 1
, x 2 ), (x 1 , x
3 ), (x 2 , x
1 ), (x 3 , x 3
). E
2 = (x
2 , x
4 ), (x
3 , x
2 )
, (x
4 , x
2 ).
E = (x 1 , x
2 ), (x
1 , x
3 ), (x
2 , x
1 ), (x
3 , x
3 ), (x
2 , x
4 ), (x
3 , x
2 )
, (x
4 , x
2 ).
Результирующий граф G(X,E) =
G 1 (X 1 ,E
1 )
G 2 (X 2 ,E
2 ) также приведен на рис. 1.




Ваше мнение



CAPTCHA