2.2.3. Унарные операции над графами
Для графа G=(V,E)частью графаназывается такой графH=(V’,E’), у которогоV’(H)V(G) иE’(H)E(G). Другими словами, этот граф, порожденный ребрами графаG. Частью графа является путь, цикл и т.п. Вместо термина «часть графа» часто используют термин «подграф (в слабом смысле)».
Подграф ( в сильном смысле)- для графаG=(V,E) такой графH=(W,U), у которого множество вершинW V, множество реберU E, причем если {x,y} Eиx,y W, то обязательно {x,y} U.
Если G1GиG1содержит все вершины графаG, тогдаG1называют каркасным подграфом. Каркасных подграфов может быть несколько.
Дополнением графаG=(V,E) называется графG’=(V,E’), у которого:
вершины исходного графа G,
ребра E’ являются ребрами, дополняющими графGдо полного графаKn.
Пример
G G’
Рис.2.2.5.
ГрафGи его дополнениеG’
Определение
Операцией декомпозиции графа G(V,E)называется представление его в виде последовательности графовG1,…,GSтаких, что:
число вершин одинаково у всех графов G1,…,GS;
число ребер E(G) графаG=(V,E) равно объединению ребер графовG1,…,GS:
E(G)= E(Gi).
Замечания
В качестве раздельных графов наиболее часто выбираются циклы, деревья, пути заданной длины и т.д.
О
перация
объединения раздельных графов является
операцией, обратной операции декомпозиции.
Определение
Операция построения реберного графа L(G)=(U,F) графаG=(V,E) состоит в следующем:
каждой вершине u Uреберного графаL(G) сопоставлено реброei E(G) графаG;
в
Пример
ершины вL(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графеG.
е1 е6
е2
е4 е5
е3
Вершины L(G):
U1={1,2},
U2={1,3}, U3={1,4},
U4={2,3},
U5={2,4},
U6={3,4}
Ребра L(G)
(определяются в соответствии со
вторым условием):
1 ребро L(G) ребра {1,2}и{1,3} смежны
в G: U1соединена ребром сU2 2 ребро L(G) ребра {1,2}и{1,4} смежны
в G: U1соединена ребром сU3 3 ребро L(G) ребра {1,2}и{2,4} смежны
в G: U1соединена ребром сU5 4 ребро L(G) ребра {1,2}и{2,3} смежны
в G: U1соединена ребром сU4 5 ребро L(G) ребра {1,2}и{1,3} смежны
в G: вариант был 6 ребро L(G) ребра {1,3}и{1,4} смежны
в G: U2соединена ребром сU3 7 ребро L(G) ребра {1,3}и{2,3} смежны
в G: U2соединена ребром сU4 8 ребро L(G) ребра {1,3}и{3,4} смежны
в G: U2соединена ребром сU6 9 ребро L(G) ребра {1,4}и{1,2} смежны
в G: вариант был 10 ребро L(G) ребра {1,4}и{1,3} смежны
в G: вариант был
11 ребро L(G) ребра {1,4}и{2,4} смежны
в G: U3соединена ребром сU5 12 ребро L(G) ребра {1,4}и{3,4} смежны
в G: U3соединена ребром сU6 13 ребро L(G) ребра {2,3}и{1,3} смежны
в G: вариант был 14 ребро L(G) ребра {2,3}и{1,2} смежны
в G: вариант был 15 ребро L(G) ребра {2,3}и{2,4} смежны
в G: U4соединена ребром сU5 16 ребро L(G) ребра {2,3}и{3,4} смежны
в G: U4соединена ребром сU6 17 ребро L(G) ребра {3,4}и{1,3} смежны
в G: вариант был 18 ребро L(G) ребра {3,4}и{2,3} смежны
в G: вариант был 19 ребро L(G) ребра {3,4}и{1,4} смежны
в G: вариант был 20 ребро L(G) ребра {3,4}и{2,4} смежны
в G: U5соединена ребром сU6
Определения
Срединный графM(G) получается из графаGвыполнением следующих операций:
новая вершина вставляется в каждое ребро графа G;
пары новых вершин соединяются ребрами в том случае, когда эти пары лежат на смежных ребрах графа.
Тотальный граф T(G) графа G строится следующим образом:
вершины T(G) являются объединением множества вершин и ребер графаG;
две вершины графа T(G) соединены ребром тогда и только тогда, когда соответствующие элементы графаGсмежны или индидентны.
k-ой степеньюGk графаG=(V,E) является граф с тем же множеством вершинV(G) и ребром между двумя вершинами тогда и только тогда, когда между ними имеется путь длиной самое большееk.
