2014-02-12
11811
 |
1) Объединение двух графов G =(V, E) и G ¢=(V ¢, E ¢) есть граф S =(V ∪ V ¢, E ∪ E ¢).
На рисунке 15 показано объединение двух графов.
 |
2) Пересечение двух графов G =(V, E) и G ¢=(V ¢, E ¢) есть граф S =(V ∩ V ¢, E ∩ E ¢). См. рис.16.
3) Кольцевая сумма двух графов G Å G ¢ есть граф, не имеющий изолированных вершин и состоящий только из ребер, присутствующих либо в G, либо в G ¢, но не в обоих графах одновременно. Т.о. это Е Å Е ¢ реберно-порожденный граф. См. рис.17.
 |  | ||
4) Относительное дополнение подграфа до графа – это граф, в который входят те ребра основного графа, которых не было в подграфе, а множество вершин совпадает с множеством вершин основного графа. См. рис.18.
5) Абсолютное дополнение – это дополнение до полного графа на том же множестве вершин. Так для графа, изображенного в правой части равенства на рис.18, абсолютное дополнение будет изображаться так, как показано на рис.19.
 |
6) Удаление ребра – ребро удаляется из графа, а инцидентные ему вершины остаются. См.рис.20.
 |
7) Удаление вершины – вершина удаляется из графа вместе со всеми инцидентными ей ребрами. См. рис.21.
 |
8) Отождествление (замыкание) вершин – при замыкании двух вершин, эти вершины удаляются из графа и заменяются одной новой, при этом ребра, инцидентные исходным вершинам, теперь будут инцидентны новой вершине.
9) Стягивание ребра – ребро удаляется, а его концевые вершины отождествляются. На рисунке 23 последовательно стягиваются ребра е 1, е 3, е 2.
