1.Удаление вершин. Опереция удаления вершины x из G состоит из удаления из G самой вершины x и всех инцидентных ей ребер.
2. Удаление ребра. Граф полученный в результате удаления ребра e их графа G обозн. G-e и имеет тоже множество вершин что и G и все ребра G за исключением e.
3.Объединение графов. Даны G1=(X1,E1), G2=(X2,E2). Объединение G1 и G2 это граф G=(X,E) G1"объедиение"G2=G=(X,E). X=X1"объедиение"X2, E=E1"объедиение"E2. G наз. дизъюнктивным объединением если X1 в пересечении с X2 пусто. |X|=|X1|+|X2|-|X1|пересечение|X2|; |E|=|E1|+|E2|-|E1|пересечение|E2|.
4. Декертово произведение. Даны G1=(X1,E1), G2=(X2,E2). Декартовопроизведение графов это G=(X,E), где X=X1*X2 две вершины (u1,v1) и (u2,v2) смежны в случае если: а) u1=v2 совпадают в графе G1; v1смежно с v2 в графе G2. б)u1смежно с u2 в G1; v1=v2 в G2. |X|=|X1|*|X2|; |E|=|X1|*|E2|+|X2|*|E1|.
5. Слияние вершин. Пусть дан G(X,E) и a,b принадлежит X. Слияние вершин a и b в графе G заключаеться в удалении этих вершин из G(а также инцидентные им ребра) и добавление новой вершины с смежной со всеми вершинами графа G с которыми были смежны вершины a и b.
6. Стягивание ребра. Пусть G=(X,E) и e=(a,b) его ребро. Операция стягивания ребра графа идентична операции слияния его концов.
7.Расчепление вершин. Дан G=(X,E) и любое x принадлежащее X. Окружение вершины x разобъем на 2 непересекающихся подмножества. N(x)=P объединение M, P пересечение M = пусто. Операция расщепления вершины x состоит в удалении из G вершины x и добавлени двух смежных вершин u смежно v, таких что вершина v смежна со всеми вершинами множества M, а u смежна со всеми вершинами из множества P
3 Операции на графах .Определения примеры .
Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, т. е. определены на одном графе.
Объединение графов G1 и G2 , обозначаемое как G1 G2 , представляет такой граф G3 = (Х1 Х2, A1 A2), что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 . Граф G3 , полученный операцией объединения графов G1 и G2 . Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .
Пересечение графов G1 и G2 , обозначаемое как G1 G2 , представляет собой граф G4 = (Х1 Х2, A1 A2). Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в G1 и G2 . Операция пересечения графов G1 G2 показана на рис. 2.2,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2 . показана на рис. 2.2.г.
Операция пересечения и кольцевой суммы: а – граф G1; б – граф G2; в – граф G1 G2 ; г – матрица смежности графа G1 G2 ; д – граф G1 G2 ; е – матрица смежности графа G1 G2
Кольцевая сумма двух графов G1 и G2 , обозначаемая как G1 G2 , представляет собой граф G5 , порожденный на множестве ребер A1 A2 . Другими словами, граф G5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G1 , либо в G2 , но не в обоих одновременно. Кольцевая сумма графов G1 и G2 , а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G1 и G2 .
Легко убедиться в том, что три рассмотренные операции коммутативны т. е. G1 G2 = G2 G1, G1 G2 = G2 G1, G1 G2 = G2 G1 , и многоместны, т. е. G1 G2 G3 G4 ..., G1 G2 G3 G4 ... и так далее.
Рассмотрим унарные операции на графе.
Удаление вершины. Если хi -вершина графа G = (X, A), то G–хi -порожденный подграф графа G на множестве вершин X–хi , т. е. G–хi является графом, получившимся после удаления из графа G вершины хi и всех ребер, инцидентных этой вершине. Удаление вершины х3 . Результирующая матрица смежности графа после выполнения операции удаления вершины хi получается путем удаления соответствующего i- го столбца и i-ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1)- го столбца и (i+1)-ой строки. В дальнейшем элементы графа могут быть переобозначены.
Удаление ребра или удаление дуги. Если ai -дуга графа G = = (X, A), то G-ai – подграф графа G, получающийся после удаления из G дуги ai . Заметим, что концевые вершины дуги ai не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Результирующая матрица смежности графа после выполнения операции удаления дуги ai получается путем удаления соответствующих элементов из исходной матрицы.
Замыкание или отождествление. Говорят, что пара вершин хi и xj в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные хi и xj , становятся инцидентными новой вершине. Например, результат замыкания вершины х1 и х2 ,г для графа G . Матрица смежности графа после выполнения операции замыкания вершин хi и xj получается путем поэлементного логического сложения i- го и j- го столбцов и i-ой и j- строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали .
Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин.