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

Объединением графов G₁(V₁, E₁) и G₂(V₂, E₂) называется граф G(V, E) = , где V = , E = .Пересечением графов G₁(V₁, E₁) и G₂(V₂, E₂) называется граф G(V, E) = , где V = E = Дополнением графа G₁(V₁, E₁) называется граф G(V, E) = , где , E = Кольцевой суммой графов G₁(V₁, E₁) и G₂(V₂, E₂) называется граф G(V, E) = , где V = , E = . Подграфом графа G(V, E) называется граф G ¢(V ¢, E ¢), где . Подграф называется остовным подграфом графа G(V,E), если . Подграф называется собственным подграфом граф G, если .

34.Связанность, компоненты связанности, матрицасвязанности, выделение компонентов связанности.Две вершины называются связными, если существует маршрут между ними. Связность для вершин является бинарным отношением. Неориентированный граф называется связным, если между любыми двумя вершинами есть маршрут. Любой граф G можно разбить на непересекающиеся подмножества вершин по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств – несвязны. Тогда все выделенные таким образом подграфы называют компонентами связности графа G. При этом связный граф имеет одну компоненту связности. Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[s_ij] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[s_ij] порядка n, элементы которой равны

Поиск маршрутов в графах.

Алгоритм (Тэрри) поиска пути в связном графе, из вершины vi в вершину vj, где vi vj.

Исходя из вершины vi осуществлять последовательный переход от каждой достигнутой вершины к смежной ей вершине, по следующим правилам:

1. идя по произвольной дуге, всякий раз отмечать направление, в котором оно было пройдено;

2. исходя из некоторой вершины vk, всегда следовать только по дуге, которое не было пройдено или было пройдено в противоположном направлении;

3. для всякой вершины vk, отличной от vi, отмечать первую заходящую в vk дугу, если вершина vk встречается в первый раз;

4. исходя из некоторой вершины, vk, отличной от вершины vi, по первой заходящей в vk дуге идти лишь тогда, когда нет других возможностей.

Путь в орграфе из вершины vi в вершину vj, где vi ` vj , называется минимальным, если он имеет минимальную длину среди всех путей орграфа из vi в vj.

Деревья, свойства деревьев. Лес.

Граф называется деревом, если он является связным и не имеет циклов. Любые две различные вершины дерева можно соединить единственной (и притом простой) цепью. Число дуг дерева на единицу меньше числа его вершин. Пусть G – дерево. Тогда любая цепь в G является простой. Если какую-нибудь пару несмежных вершин дерева соединить дугой, то полученный граф будет содержать ровно одну цепь. Граф, все компоненты связности которого являются деревьями, называется лесом.

37.Остовное дерево, минимальное остовное дерево. Остовным деревом (остовом или каркасом) связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Замечание. Остовное дерево графа не единственно. Число дуг произвольного неорграфа G, которое надо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k, где m – число дуг, n – число вершин, k – число компонент связности графа G. Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Эйлеровы графы и циклы.

Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Связный граф называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым, при этом каждый эйлеров граф будет полуэйлеровым. Если граф обладает эйлеровым циклом, то он является связным, а все его вершины — четными.

39. Гамильтоновы графы и циклы.

Маршрутом (или путем) в графе G называется чередующаяся последовательность вершин и ребер v , e ₁, v ₁, …, v_{t −1}, e_t , v_{t +1}, в которой e_i = v_{i −1} v_i (1 ≤ i ≤ t ). Такой маршрут кратко называют ( v , v_t )-маршрутом и говорят, что он соединяет v c v_t ; в свою очередь вершины v , v_t — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v , v ₁, …, v _t своих вершин. Если v = v_t , то ( v , v_t )-маршрут называется замкнутым. Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром). Гамильтоновой цепью графа называется его простая цепь, которая проходит через каждую вершину графа точно один раз. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом. Граф называется гамильтоновым, если он обладает гамильтоновым циклом. Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (Hamilton W.), который в 1859 году предложил следующую игру-головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.

Планарные графы.

Граф называется плоским, если никакие два его ребра не пересекаются. Граф называется планарным, если он изоморфен некоторому плоскому графу. Любой планарный граф допускает плоское представление, в котором все ребра являются отрезками. Любой граф укладывается в трехмерном пространстве , т.е. любой граф можно изобразить в трехмерном пространстве так, чтобы его ребра не пересекались.

Лекция 2. Операции над графами

Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, т. е. определены на одном графе.

Просмотр содержимого документа
«Лекция 2. Операции над графами»

Лекция 2. Операции над графами

Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, т. е. определены на одном графе.

Объединение графов G₁ и G₂ , обозначаемое как , представляет такой граф , что множество его вершин является объединением Х₁ и Х₂ , а множество ребер – объединением A₁ и A₂ . Граф G₃ , полученный операцией объединения графов G₁ и G₂ , показан на рис. 2.1,д, а его матрица смежности – на рис. 2.1,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G₁ и G₂ .

Пересечение графов G₁ и G₂ , обозначаемое как , представляет собой граф . Таким образом, множество вершин графа G₄ состоит из вершин, присутствующих одновременно в G₁ и G₂ . Операция пересечения графов показана на рис. 2.2,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G₁ и G₂ . показана на рис. 2.2.г.

Рис.2.2. Операция пересечения и кольцевой суммы: а – граф G₁ ; б – граф G₂ ; в – граф ; г – матрица смежности графа ; д – граф ; е – матрица смежности графа

Кольцевая сумма двух графов G₁ и G₂ , обозначаемая как , представляет собой граф G₅ , порожденный на множестве ребер . Другими словами, граф G₅ не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G₁ , либо в G₂ , но не в обоих одновременно. Кольцевая сумма графов G₁ и G₂ показана на рис. 2.2,д, а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G₁ и G₂ . показана на рис. 2.2.е.

Легко убедиться в том, что три рассмотренные операции коммутативны т. е. , и многоместны, т. е. . и так далее.

Удаление вершины. Если х_i -вершина графа G = (X, A), то G–х_i -порожденный подграф графа G на множестве вершин X–х_i , т. е. G–х_i является графом, получившимся после удаления из графа G вершины х_iи всех ребер, инцидентных этой вершине. Удаление вершины х₃ показано на рис. 2.3,б (для исходного графа, изображенного на рис. 2.3,а). Матрица смежности исходного графа представлена на таблице 2.1а). Результирующая матрица смежности графа после выполнения операции удаления вершины х_i получается путем удаления соответствующего i – го столбца и i -ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1) – го столбца и (i+1) -ой строки ( таблица 2.1б). В дальнейшем элементы графа могут быть переобозначены.

Удаление ребра или удаление дуги. Если a_i – дуга графа G = (X, A), то G-a_i – подграф графа G, получающийся после удаления из G дуги a_i . Заметим, что концевые вершины дуги a_i не удаляются. Удаление изграфа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a₄ и a₇ показано на рис. 2.3,в. Результирующая матрица смежности графа после выполнения операции удаления дуги a_i получается путем удаления соответствующих элементов из исходной матрицы ( таблица 2.1в).

Бинарные операции

Определение 58.12. Объединением графов графов Gi и G2, обозначаемое как Gi u G2, представляет такой граф G3 = (Xi u Х2, Ai и Аг), что множество его вершин является объединением множеств вершин каждого графа Xi и Х2, а множество ребер — объединением множеств их ребер Ai и А2. Граф G3, полученный операцией объединения графов Gi и G2, показан на рис. 58.3 (я — граф Gi, б — G2, с — G3), а его матрица смежности показана далее. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов Gi и G2.

Матрицы смежности графов:

Определение 58.13 Пересечение графов Gi и G2, обозначаемое как Gi n G2, представляет собой граф G4 = (Xi n Х2, Ai n А2). Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в Gi и в G2 . Операция пересечения графов Gi n G2 показана на рис. 58.4, в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов Gi и G2 показана далее:

Определение 58.14. Кольцевая сумма двух графов Gi и G2, обозначаемая как Gi © G2, представляет собой граф G5, порожденный на множестве ребер Ai © А2. Другими словами, граф G5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в Gi, либо в G2, но не в обоих одновременно. Кольцевая сумма графов Gi и G2 показана на рис. 58.4, г.

Рис. 58.4. Операция пересечения и кольцевой суммы: а — граф Gu б—граф G2; в — граф G| о G2;