![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Для графов и
их объединение
определяется как граф
, а пересечение
– как граф
.
Дополнением (дополнительным графом) к графу называется граф
, у которого множество вершин то же, что у G, а множество ребер является дополнением множества E до множества всех неупорядоченных пар вершин. Иначе говоря, две различные вершины смежны в графе
тогда и только тогда, когда они не смежны в графе G. Например,
.
Под суммой двух абстрактных графов понимают объединение графов с непересекающимися множествами вершин. Точнее говоря, имеется в виду следующее. Сначала вершинам графов-слагаемых присваиваются имена (пометки, номера) так, чтобы множества вершин не пересекались, затем полученные графы объединяются и пометки стираются (т.е. результат операции – тоже абстрактный граф). Операция сложения ассоциативна, то есть
для любых трех графов. Поэтому можно образовывать сумму любого числа графов, не указывая порядка действий с помощью скобок. Если складываются k экземпляров одного и того же графа G, то полученный граф обозначается через
. Например,
.
Соединением графов и
называется граф
, получаемый из их суммы добавлением всех ребер, соединяющих вершины первого слагаемого с вершинами второго. Например,
. На рисунке 1 слева изображен граф
справа – граф
.
Рис. 1.
Произведение графов
и
определяется следующим образом. Множеством вершин графа
является декартово произведение множеств
и
, то есть вершины этого графа – упорядоченные пары
, где
,
. Вершины
и
в графе
смежны тогда и только тогда, когда
и
смежна с
в графе
, или
и
смежна с
в графе
. С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух путей дает прямоугольную решетку – см. рисунок 2.
Рис. 2.
Другой пример – k- мерный куб , определяемый следующим образом. Вершинами его являются всевозможные упорядоченные двоичные наборы длины k. Всего, таким образом, в этом графе
вершин. Вершины
и
смежны в нем тогда и только тогда, когда наборы x и y различаются точно в одной координате. С помощью операции произведения граф
можно определить рекурсивно:
,
.
На рисунке 3 показано, как получается из
.
Рис. 3.
Дата публикования: 2014-11-26; Прочитано: 1089 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!