что такое остов графа

Остовы графа

Содержание

Остов графа

Пусть G — произвольный (n, m)-граф с k компонентами связности. Если G — не дерево, то в нем (его компонентах связности) существуют циклы. Рассмотрим какой-либо цикл и удалим из него некоторое ребро. При этом количество компонент связности не увеличится. Если после этого еще останутся циклы, то рассмотрим следующий из них и снова удалим какое-либо его ребро. Продолжим этот процесс до тех пор, пока не исчезнут все циклы. Полученный в результате подграф, который, очевидно, является лесом и имеет столько же компонент связности, как и исходный граф G, называется остовом графа G.

Остовым (покрывающим) деревом графа G называется любое дерево T, являющееся суграфом графа G. Покрывающее дерево T в связном графе определяется неоднозначно.

Связный граф имеет единственное покрывающее дерево тогда и только тогда, когда он сам является деревом.

Остов графа G является минимальным связным суграфом графа G, то есть содержит минимальное количество ребер, связывающих вершины графа.

Суграф T графа G называется каркасом этого графа, если он является лесом, который на любом компоненте связности графа G образует дерево.

Теорема

Число ребер произвольного графа G с n вершинами и m ребрами, имеющего k компонент связности, которое необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m-n+k.

Доказательство теоремы

Определения

Число ν(G)=m-n+k называется цикломатическим числом (циклическим рангом) графа G. Число ν*(G)=n-k, то есть число ребер, входящих в любой остов графа G называется его коциклическим рангом. ν(G)+ν*(G)=m. Корневым деревом называется дерево T=(V,E) с выделенной вершиной ν, принадлежащая V, при этом вершина ν называется корнем дерева. Для каждой вершины корневого дерева её уровень — это длина цепи от корня до этой вершины.

Следствия

Следствие 1 Граф G является лесом тогда и только тогда, когда ν(G)=0.

Следствие 2 Граф G имеет единственный цикл тогда и только тогда, когда ν(G)=1.

Следствие 3 Граф G, в котором число ребер не меньше, чем число вершин, имеет цикл.

Теорема (Кирхгоф)

Число остовов в связном графе G порядка n≥2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G) графа G.

Теорема. Орграф сильно связан, если в нем существует остовной циклический маршрут.

Полезное

Смотреть что такое «Остовы графа» в других словарях:

Семейство полорогие — (Bovidae)** * * Семейство полорогих, или бычьих самая обширная и разнообразная группа парнокопытных, включает 45 50 современных родов и около 130 видов. Полорогие животные составляют естественную, ясно очерченную группу. Как ни… … Жизнь животных

Семейство настоящие лягушки — У семейства настоящих лягушек зубы имеются только на нижней челюсти; поперечные отростки крестцового позвонка имеют цилиндрическую форму, к концу слабо или совсем не расширяясь. Грудной пояс у отдельных родов мало различается, зато форма… … Жизнь животных

Источник

Остов графа

Остов – минимальное множество ребер, которые связывают все вершины связного графа.

Остов это дерево. Часть G‘ графа G называется остовом (каркасом, скелетом), если V’ = V и все они связаны без циклов. Остов обычно обозначают буквой T. Для орграфов остов – часть G, которая является остовом в неорграфе, полученном из G удалением ориентации дуг.

Остов получается из графа разрушением циклов. Число удаляемых при этом ребер: (G) = m – n + 1 – называется цикломатическим числом или цикломатическим рангом графа (или просто рангом графа).

Если граф состоит из нескольких компонент, то его остов лес, а число удаляемых при определении остова ребер будет равно:

(G) = m – n + ρ,

где ρ – количество компонент связности графа.

Количеств ребер в остове графа:

*(G) = n – ρ

называется коциклическим рангом.

(У связного графа *(G) = n – 1.)

Для дерева цикломатическое число равно 0.

Нахождение остова минимальной длины

3) Повторяем п. 2, пока находятся нужные ребра.

Фундаментальным циклом графа G(V,E) с остовным деревом T(V,E‘) называется простой цикл, получаемый в результате добавления к T одного из ребер G, не принадлежащего E‘. Количество фундаментальных циклов графа G = (V,E) при любом остовном дереве T равно цикломатическому числу (G).

Пусть G(V, E) связный неорграф с n вершинами и m ребрами, T – остов графа, имеющий n – 1 ребро, которые называются ветвями T (ведь остов – это дерево) и обозначаются b_j.

Не входящие в остов (G) = m – n + 1 ребер называются хордами и обозначаются h_i.

Если к дереву T добавить произвольную хорду h_i, то образуется точно один цикл C_i. Этот цикл состоит из хорды h_i и некоторых ветвей остова, образующих простую цепь и соединяющих вершины хорды h_i.

Цикл C_i называется фундаментальным циклом графа G относительно хорды h_i остова T (в общем случае остовов в графе может быть много). Таким образом, фундаментальный цикл содержит точно одну хорду остова графа.

Множество всех фундаментальных циклов <C₁, C₂, …, C_i, …, C_m–n+1> относительно хорд остова T называется фундаментальным множеством циклов графа G. Мощность этого множества равна цикломатическому числу (G) = m – n +1 или рангу графа G.

фундаментальное множество циклов графа можно задать с помощью матрицы, строки которой имеют вид

где h_i, b_j – хорды и ветви соответственно.

В каждом цикле имеется одна хорда h_i и некоторое множество ветвей остова T. Этой хорде h_i и ветвям, входящим в цикл C_i, присвоим значение 1, остальным ребрам графа присвоим значение 0. Повторяя процедуру для всех хорд, получим матрицу строк из 0 и 1.

Разрезом неорграфа G(V,E) по разбиению множества вершин V на два подмножества V₁ и V₂ называется множество ребер, соединяющих вершины из подмножества V₁ с вершинами подмножества V₂. В связном графе любой разрез не пуст.

Непустой разрез K неорграфа G называется простым или коциклом, если множество ребер K не содержит разрезов G ни по какому разбиению (любой разрез разбивает граф на две части – увеличивает число компонент связности).

В связном неорграфе остов T имеет, по крайней мере, одно общее ребро с любым разрезом графа.

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

Удаляя произвольную ветвь b_i из T, получаем лес с двумя компонентами, т. е. каждое ребро b_i есть разрез T по некоторому разбиению вершин V₁, V₂.

Множество ребер K_i = <b_i, h_i1, …, h_ij> образует разрез G относительно ветви b_i, который называют фундаментальным разрезом относительно b_i остова T. Таким образом, фундаментальный разрез содержит точно одну ветвь остова графа.

Множество <K₁, K₂, …, K_n–1> всех фундаментальных разрезов графа G называется фундаментальным множеством разрезов графа G относительно остова T.

Мощность этого множества равна *(G) = n–1. (В общем случае n– , где число компонент связности графа.)

По аналогии с фундаментальными циклами, каждому фундаментальному разрезу можно поставить в соответствие вектор

где

Из этих векторов можно составить матрицу фундаментальных разрезов.

Поскольку каждый фундаментальный разрез содержит точно одну ветвь T, то матрица K имеет вид:

где v* это *(G) = n – 1.

Таким образом , где H – матрица хорд графа, E – единичная матрица порядка *(G).

Матрицы фундаментальных циклов C и фундаментальных разрезов K взаимосвязаны.

Если , то ,

где – транспонированная матрица B.

Следовательно, для анализа графа достаточно найти одну матрицу (C или K), а другую можно определить транспонированием.

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

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

Планарность нужна, например, для реализации печатного монтажа, в процессе разработки которого схема устройства представляется в виде графа: элементы – вершины, связи между выводами элементов – ребра.

Если граф не планарен, то приходится удалять (переносить на другой слой, на другую плоскость) отдельные ребра. Минимальное число ребер, которое надо удалить для получения плоского изображения, называется числом планарности графа и обозначается (G). Для полных графов с

(K_n) = (n–3)(n–4)/2.

Из формулы следует, что при n = 4 (K₄) = 0. Для K₅ (K₅) = 1, следовательно, чтобы граф K₅ стал плоским, из него надо удалить одно ребро.

При перенесении на вторую плоскость, перенесенная часть может опять оказаться не плоской. Тогда отдельные ребра переносят на новую плоскость и т.д. Минимальное число плоскостей, при котором граф разбивается на плоские части, называется толщиной графа и обозначается t(G).

Толщина произвольного графа удовлетворяет неравенству

t(G) .

Здесь [x] – целая часть x.

Толщина полных графов удовлетворяет неравенству

t(K_n) .

Ответ на первый вопрос: – Граф планарен? – можно получить, если воспользоваться условиями планарности.

У связного плоского графа с n 3 число ребер m удовлетворяет условию

У связного плоского двудольного графа

У плоского графа кроме вершин и ребер можно выделить еще один геометрический образ – грань. Область плоскости, ограниченная ребрами связного плоского графа и не содержащая внутри себя ни ребер, ни вершин, называется его гранью. Внешняя неограниченная грань называется бесконечной гранью. У графа без циклов ровно одна грань – бесконечная. Не следует думать, что она какая–то исключительная. При укладке графа на сферу эта грань ничем не будет отличаться от других.

Число граней f в связном плоском графе определяется из соотношения:

где n – число вершин, m – число ребер.

Будем называть кускомграфа G относительно G₁:

1) ребро вместе с его концами,которые принадлежат V₁,

Алгоритм использует последовательный процесс присоединения к некоторому плоскому подграфу цепи , оба конца которой (и только они) – вершины . Эта цепь разобьет одну из граней на две.

В качестве начального плоского графа выбирают некоторый цикл графа G. Чтобы перейти от подграфа к , предварительно рассматривают все куски P_j графа G относительно .Грань f_k графа и кусок Р_j совместимы, если все его контактные точки принадлежат множеству вершин этой грани.

Для каждого куска определяем грани, которые с ним совместимы. Возможны три случая:

1) Некоторый кусок не совместим ни с какой гранью графа . Тогда граф не плоский.

2) Какой–либо кусок совместим с единственной гранью f_k графа . Тогда выберем в этом куске цепь такую, что оба ее конца (и только они) принадлежат . Дополняя ребрами и вершинами этой цепи, получаем , проводя внутри грани f_k.

3) Если каждый из кусков Р_j совместим, по крайней мере, с двумя гранями графа , то можно выбрать цепь в любом из кусков и действовать как в случае 2.

Источник

3.5. Дерево. Остов

отсюда следует, что

т. е. число ребер в дереве на единицу меньше числа вершин.

Ниже на рис. 3.7 приведены примеры деревьев.

Пример 3.7

В общем случае для графа можно построить несколько остовов. Для приведенного ниже графа построен один из возможных вариантов остова.

3.5.1. Алгоритм построения произвольного остова. Рассмотрим словесное описание алгоритма:

1. Для каждой компоненты i графа выполняем пункты 2 и 3.

2. Строим частичный подграф, содержащий все n_i вершин i-й компоненты и не содержащий ребер (0- граф).

3. Если в текущий частичный граф включены уже n_i-1 ребер, то остов для компоненты i построен, иначе выбираем очередное ребро компоненты и пытаемся его включить в текущий граф.

Так как цикл не образовался, то все рёбра с номерами 1, 2, 3, 4 включены в остов. Проверяем по (3.3): m=4, n=5 и 4=5-1.

3.5.2. Алгоритм построения минимального остова. Для взвешенного графа остов с наименьшей суммой весов для вошедших в него рёбер называется минимальным (кратчайшее связное дерево).

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

3.5.3. Алгоритм построения системы независимых циклов графа

1. Строится произвольный остов графа. В исходном графе отмечаются рёбра, не включенные в остов.

3. По формуле Эйлера (3.2) производится проверка числа построенных циклов.

Пример 3.12

Рис 3.12

3.6. Алгоритм кратчайшей раскраски графа

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

Теорема. Для плоских графов   4.

Пример 3.13. Рассмотрим граф G (рис. 3.13). Убедившись в том, что он – плоский (ребро (x₁, x₅) может быть проведено вне контура (x₁, x₂, x₃, x₅)), произведём его раскраску. Имеем: =3 (краски  0, 1, 2).

Источник

Поиск минимального остовного дерева графа

Вы будете перенаправлены на Автор24

Минимальное остовное дерево — это остовное дерево графа, которое имеет самый маленький допустимый вес (сумму весов всех его рёбер).

Введение

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

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

Задача о минимальном остовном дереве

Задача минимального остова ставится так: во взвешенном связном графе нужно определить остов, имеющий самый маленький вес. Другими словами, найти остов с минимальным общим весом всех рёбер. Для этих целей возможно использовать алгоритм Краскала, который позволяет выстроить минимальный остов графа. Построение остова выполняется последовательно, с каждым шагом прибавляется по одному ребру. Основой алгоритма являются два принципа:

Рисунок 1. Задача о минимальном остовном дереве. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

Рисунок 2. Минимальный остов. Автор24 — интернет-биржа студенческих работ

Рассмотрим пример нахождения минимального остовного дерева графа, изображённого на рисунке один. Формирование остова следует начать с ребра, имеющего наименьший вес. Таких рёбер два, ($V_1, V_3$) и ($V_2, V_5$), выбираем первый вариант. Рёбра присоединяются к остову в следующей очерёдности: ($V_1, V_3$), ($V_2, V_5$), ($V_1, V_2$), ($V_4, V_5$). И тогда суммарная весовая характеристика остова будет:

Следует отметить, что рёбра ($v_2, v_3$), ($v_1, v_5$) не вошли в состав остова, хотя и обладают меньшим весом чем ребро ($v_4, v_5$), поскольку их присутствие приводит к образованию циклов с рёбрами, уже находящимися в составе остова.

Рассмотрим ещё пример практического применения этой задачи. Предположим есть множество аэродромов, и необходимо рассчитать самый маленький (по суммарному расстоянию) комплект авиационных рейсов, позволяющий летать между всеми аэропортами. Для решения данной задачи, необходимо найти самый маленький остов полного графа дистанций среди аэропортов. Он и будет решением данной проблемы.

Очень много практических задач возможно свести к нахождению самого маленького расстояния между двумя вершинами (или некоторым количеством пар вершин) в заданном графе (или орграфе). Задача может быть поставлена в разных вариациях:

Расположение «центров», которые покрывают требуемую зону

Примерами задач такого типа могут служить:

Рассмотрим конкретный пример. Необходимо выполнить размещение радиопередающих станций на пространстве, которое представляет из себя квадрат, поделённый на шестнадцать районов, таким образом, чтобы станция, размещённая в любом районе, имела возможность вещания на данный район и на соседние районы, размещённые по горизонтали и вертикали. При этом, количество станций необходимо минимизировать.

Алгоритм решения может быть таким. Нужно построить граф, у которого в качестве вершин будут соответствующие районы. Пара вершин соединяется лишь в одном случае, когда районы, которые они символизируют, будут соседними. Когда такой граф построен, решение задачи сводится к определению минимального доминирующего множества вершин в этом графе.

Задача планирования производства

Практическими примерами задач этого типа является планирование производства в организациях различных промышленных сфер. Рассмотрим пример. Необходимо изготовить n товаров на определённом промышленном оборудовании. При этом для одного оборудования при переходе с производства старых товаров на производство новых товаров его нужно перенастраивать, а для других товаров этого делать не требуется. Цена переналадки оборудования одна и та же вне зависимости от типа товаров. Необходимо определить цикл последовательного выполнения операций, которые не требуют выполнять перенастройку оборудования, или доказать, что это невозможно. Для решения этой задачи, требуется выстроить орграф, с вершинами, соответствующими наименованиям товаров. Если существует дуга (n, v), то это значит, что товар v возможно делать после товара n и перенастройка оборудования не требуется. В этом случае задача состоит в определении одного или множества возможных гамильтоновых циклов в данном орграфе.

Задача раскраски графа

Под раскраской графа понимается придание каждой его вершине определённого цвета и при этом пара любых смежных вершин не имеет одинакового цвета. Минимальное из возможных количество цветов в раскраске определяется как хроматическое число графа. При выполнении раскраски все вершины подлежат разбиению на классы «единого цвета». Все вершины одного класса не могут быть смежными.

Рисунок 3. Раскраска графа. Автор24 — интернет-биржа студенческих работ

Требуется определить хроматическое число графа, изображённого на рисунке 2. Выполним раскраску вершин 1, 3, 5, 7 в красные цвета. Вершины 2, 6, 8 раскрасим жёлтым цветом, а вершину 4 выкрасим зелёным. Вычисления хроматического числа дали итог равный трём.

Источник