Задать вопрос юристу

Операции над графами

Граф Н называется подграфом (или частью) графа G, если VH I VG, ЕH I ЕG. Подграф Н называется остовным подграфом, если VH = VG. Если множество вершин подграфа Н есть U, а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U, то Н называется подграфом, порожденным множеством U.

На рис.2.11 изображены граф G и три его подграфа Н1, Н2 и Н3 , среди которых Н3 является остовным, а Н2 – порожденным.


Граф Н называется объединением графов F и G, если V(H) = V(G)È È V(F) и E(H)= E(G) È E(F). В этой ситуации пишут Н = F È G. Объединение F ÈG называется дизъюнктным, если V(G) Ç V(F) = ?.


Введем операцию произведения графов. Пусть задано два графа G1 = (V1, E1), G2 = (V2, E2). Произведением графов называется граф, для которого – декартово произведение множеств вершин исходных графов, а E(G) определяется следующим образом: вершины (и1, и2) и (v1, v2) в графе G смежны тогда и только тогда, когда или и1 = v1, а и2 и v2 смежны в G2, или и2 = v2, а и2 и v2 смежны в G1 (рис. 2.12).

Очевидно, что ,

.

С помощью операции произведения можно определить п-мерный куб рекуррентно: .

Покажем, что это определение совпадает с данным ранее. Действительно, . Вершины графа можно представить векторами длины п из 0 и 1 таким образом, что две вершины будут смежны тогда и только тогда, когда соответствующие векторы различаются в одной координате.

Для произвольного графа G следующим образом определяется дополнительный граф (или дополнение) : , и две несовпадающие вершины смежны в тогда и только тогда, когда они не смежны в G: (рис. 2.13).

Граф, изоморфный своему дополнению, называется самодопол-нительным.

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме Операции над графами:

  1. 3.1.4. Примеры графов. Операции над графами
  2. 1.4. Логические операции с понятиями. Операции над классами (объемами понятий)
  3. Операции над понятиями (классами)
  4. 2.4.4. Кванторные операции над предикатами
  5. 2.4.3. Логические операции над предикатами
  6. §4. Операции над множествами
  7. Логические операции над вопросами
  8. Линейные операции над векторами в координатах.
  9. 3. ОПЕРАЦИИ НАД ТЕНЗОРАМИ
  10. 1.6. Операции над бинарными отношениями
  11. Свойства операций над высказываниями
  12. 12.2. ОПЕРАЦИИ НАД СЛУЧАЙНЫМИ СОБЫТИЯМИ
  13. Булевы операции над вопросами
  14. Линейные операции над векторами.
  15. Операции над комплексными числами
  16. Операции над множествами.
  17. Операции над событиями.