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

Граф Н называется подграфом (или частью) графа 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. § 2 . Институт — динамическая система
  2. 2.2. Аудит витрат на придбання товарів та операцій з матеріальними цінностями
  3. ряд примеров приложений теории графов.
  4. 1.2. Построение модели операции
  5. НЕКОТОРЫЕ ПОЛИТИЧЕСКИЕИ СТРАТЕГИЧЕСКИЕ АСПЕКТЫ ФАШИСТСКОЙ АГРЕССИИ ПРОТИВ ПОЛЬШИ (ОПЕРАЦИЯ «ВЕЙС»)
  6. ПРЕОБРАЗОВАНИЕ ДАННЫХ
  7. ПОЛОЖЕНИЕ о ведомственных Комиссиях по борьбе с взяточничеством
  8. 13.3. Особенности учета кассовых операций в иностранной валюте и операций по валютному счету
  9. Матрицы графов.
  10. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  11. Операции над графами
  12. Планарные графы
  13. 3. ТЕОРИЯ ГРАФОВ
  14. 3.1.4. Примеры графов. Операции над графами
  15. 6.2.2 Применение теории графов
  16. [33] Порядок записи операций в учетных регистрах.
  17. + 41. учет кассовых операций