Графы. Теоретико-множественные операции

Теоретико-множественные операции на графах

Изложение темы приводится для случая неографов. Даны графы G1(S1, U1) и G2(S2, U2).
1. Объединением графов G1 и G2 называется граф G(S, U) = G1 ( G2 такой, что S = S1 ( S2,
U = U1 ( U2.
Таким образом, граф G состоит из вершин и ребер, входящий хотя бы в один из графов G1, G2.
2. Пересечением графов G1 и G2 называется граф G(S, U) = G1 ( G2 такой, что S = S1 ( S2,
U = U1 ( U2.
Таким образом, граф G состоит из вершин и ребер, общих для обоих графов G1, G2.
3. Дополнительным графом к графу G(S, U) называется граф , состоящий из того же того же множества вершин, что и граф G, и множества ребер , где Uп – множество ребер соответствующего полного графа.
Таким образом, в дополнительном графе две вершины инцидентны одному и тому же ребру в том и только том случае, когда в исходном графе G это ребро отсутствует.
4. Композицией графов G1 и G2 называется граф G(S, U) = G1 ( G2, в котором каждое ребро (xi, xj) присутствует тогда и только тогда, когда в графе G1 имеется ребро (xi, xp) ( U1, а в графе G2 – ребро (xp, xj) ( U2. При этом имеется в виду, что либо S = S1 = S2, либо S = S1 ( S2.
Таким образом, композиция графов – это композиция бинарных отношений, заданных на множествах ребер графов.
5. Удалением вершины v из графа G(S, U) называется операция, дающая граф G-v, в котором множество вершин есть S\{v}, а множество ребер U( = {u | u(U\E}, где E ( U и каждое ui ( E инцидентно вершине v.
Таким образом, при удалении вершины из графа происходит удаление как самой этой вершины из множества вершин, так и инцидентных ей ребер из множества ребер.
6. Удалением ребра u из графа G(S, U) называется операция, дающая граф G-u, в котором множество вершин совпадает с множеством вершин исходного графа, а множество ребер есть U\{u}.
7. Добавлением ребра u в граф G(S, U) называется операция, дающая граф G+u, в котором множество вершин совпадает с множеством вершин исходного графа, а множество ребер есть U ( {u}.
8. Стягиванием ребра u = (xi, xj) графа G(S, U), где u ( U, {xi, xj} ( S, называется операция, дающая граф с множеством ребер U\{u} при отождествлении вершин xi и xj одной вершине v, когда ребра, инцидентные вершинам xi и xj в исходном графе, становятся инцидентными вершине v полученного графа. Обозначение операции: G/u.





















Рис. 1. Примеры операций
13 EMBED Equation.3 1415

13 EMBED Equation.3 1415




Приложенные файлы

  • doc 5869639
    Размер файла: 576 kB Загрузок: 0

Добавить комментарий