Аналитический способ задания графа это

Содержание

Способы задания графов.
Способы задания графов
Лекция 11. Графы
Способы задания графов
Маршруты, циклы, связности.
MT1100: Дискретная математика
Аналитический способ задания графов

Способы задания графов.

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

1) Графический способ.

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

На рисунке 12 изображен смешанный граф с вершинами v₁, v₂,¼, v₆, ребрами e₁, e₂, e₃, e₅ и дугой e₄. Смежные вершины v₁, v₂, инциденты ребру e₁. Вершины v₁, v₃, инциденты параллельным ребрам e₂ и e₃. Вершине v₄ инциденты петля e₅ и дуга e₄, причем v₄ является началом дуги e₄, а v₅ – концом этой дуги. Степень вершины v₁ равна 3, вершины v₂ – 1, вершины v₃ – 2, вершины v₄ – 3, вершины v₅ – 1, вершины v₆ – 0. Таким образом, вершины v₂ и v₅ – висячие, а вершина v₆ – изолированная. В случае дуги e₄ точнее было бы говорить о полустепенях исхода и захода вершин v₄ и v₅, а именно: полустепень исхода вершины v₄ равна 3, вершины v₅ – 0, полустепень захода вершины v₄ равна 2, вершины v₅ – 1.

2) Аналитический способ.

3) Матричный способ.

Имеется несколько вариантов задать граф матрицей. Наиболее употребимыми являются матрица инциденций и матрица смежности.

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

Таким образом, для графа на рисунке 12 матрица инциденций такова:

e₁	e₂	e₃	e₄	e₅
v₁
v₂
I=	v₃
v₄
v₅	-1
v₆

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

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

v₁	v₂	v₃	v₄	v₅	v₆
v₁
v₂
S=	v₃
v₄
v₅
v₆

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

Дата добавления: 2015-10-19 ; просмотров: 17507 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник

Способы задания графов

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

1) Графический способ.

На рисунке 12 изображен смешанный граф с вершинами v₁, v₂,, v₆, ребрами e₁, e₂, e₃, e₅ и дугой e₄. Смежные вершины v₁, v₂, инциденты ребру e₁. Вершины v₁, v₃, инциденты параллельным ребрам e₂ и e₃. Вершине v₄ инциденты петля e₅ и дуга e₄, причем v₄ является началом дуги e₄, а v₅ – концом этой дуги. Степень вершины v₁ равна 3, вершины v₂ – 1, вершины v₃ – 2, вершины v₄ – 3, вершины v₅ – 1, вершины v₆ – 0. Таким образом, вершины v₂ и v₅ – висячие, а вершина v₆ – изолированная. В случае дуги e₄ точнее было бы говорить о полустепенях исхода и захода вершин v₄ и v₅, а именно: полустепень исхода вершины v₄ равна 3, вершины v₅ – 0, полустепень захода вершины v₄ равна 2, вершины v₅ – 1.

2) Аналитический способ.

3) Матричный способ.

Таким образом, для графа на рисунке 12 матрица инциденций такова:

Источник

Лекция 11. Графы

Графом (G) будем называть тройку объектов (V, X, q)

V – множество n вершин.

X – конечное множество ребер.

Q — функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.

Q задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).

Vj – начало ребра

Q(xi) = (Vj, Vk) – ребро инцидентно в вершине Vj и в вершине Vk.

Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.

Если на ребре xi0

То ребро называется петлей.

Способы задания графов

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны.

В конце выписываются все изолированные вершины.

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

3. С помощью матрицы инцидентности

M = [V] – число вершин

N = [X>- число ребер

А) Неориентированные графы

Для петель нужны дополнительные предположения.

4. Матрица смежности (задается одинаково для всех графов)

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

Граф, в котором нет кратных ребер и петель, называется простым.

Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.

Дальше все о неориентированных графах.

K1 – полный граф с одной вершиной

K4 – полный граф с четырьмя вершинами

K5 – полный пятивершинник

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

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

Полный двудольный граф.

Маршруты, циклы, связности.

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

Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины.

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

Если в простой цепи первая и последняя вершины совпадают, то она называется циклом.

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

Эти части называются компонентами связности.

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

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

Связный граф, у которого все ребра ациклические, называется деревом.

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

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

Источник

MT1100: Дискретная математика

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

Матрицей смежности для графа %%G = (V, E)%% называется квадратная матрица %%A = (a_)%%, строкам и столбцам которой соответствуют вершины графа. Для неориентированного графа число %%a_%% равно числу ребер, инцидентных %%V_i%% и %%V_j%%. Для орграфа число %%a_%% равно числу ребер с началом в %%V_i%% и концом в %%V_j%%.

$$ A = \begin0 & 0 & 1 & 1 & 0 & 2 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 2 & 1 & 0 & 1 & 1 & 0 \end $$

Матрица смежности для примера из «Основных понятий»

Списком ребер графа называется таблица, состоящая из двух столбцов, в которой на пересечении %%i%%-й строки и первого (левого) столбца записывается ребро %%e_i%%, а на пересечении %%i%% -й строки и второго (правого) столбца записываются вершины, инцидентные ребру %%e_i%%.

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

1	%%B, C%%
2	%%A, C%%
3	%%B, F%%
4	%%A, F%%
5	%%A, F%%
6	%%A, D%%
7	%%D, F%%
8	%%D, E%%
9	%%E, F%%
10	%%B, E%%
11	%%E, E%%

Список ребер для примера из «Основных понятий»

Матрицей инцидентности для графа %%G = (V, E)%% называется матрица %%B = (b_)%%, столбцам которой соответствуют вершины графа, а строкам — ребра. Число орграфа %%b_%% равно: $$ b_ = \begin 1, \text < если >e_j \text < исходит из >V_i \\ -1, \text < если >e_j \text < заходит в >V_i \\ 0, \text < если >e_j \text < не инцидентно >V_i \end$$

Для неориентированного графа %%b_%% равно: $$ b_ = \begin 1, \text < если >e_j \text < инцидентно >V_i \\ 0, \text < если >e_j \text < не инцидентно >V_i \end$$

У матрицы инцидентности есть пара особенностей:

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

$$ B = \begin 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \end $$

Матрица инцидентности для примера из «Основных понятий» с учетом удаления петли у %%E%%

Источник

Аналитический способ задания графов

Практическая работа № 1

Тема: Графическое изображение графов.

Цель: изучить основы теоретико-множественного и графического представлений графов, простейших свойств графов, получить практический навык задания и визуализации графа на плоскости; закрепить навыки построения графов по образцу в графических средах (программы для графического представления графов).

Задачи:

1. Закрепить знания основных понятий теории графов.

2. Приобрести практические умения использования специального программного обеспечения для моделирования.

Материальное обеспечение:

Программы для графического представления графов: grin_rus, Grafoanalizator1.3.3 rus, windisc ru.

Теоретическая часть:

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

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

Всё более распространенными становятся представления количественных характеристик, взаимосвязей между объектами в виде разного рода одно-, двух- и более мерных гистограмм, круговых диаграмм, других аналогичных способов представления в виде тех или иных геометрических фигур, по наглядным характеристикам которых (высоте, ширине, площади, радиусу и пр.) можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.

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

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

Основные понятия теории графов

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

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

Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и тогда определение графа таково:

Граф – это конечное множество Х, состоящее из n элементов называемых вершинами графа, и подмножество V декартова произведения называемое множеством дуг.

Ориентированным графом G (орграфом) называется совокупность (Х, V).

Неориентированным графом называется совокупность множеств Х и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству Х.

Дугу между вершинами i и j, будем обозначать (i, j). Число дуг графа будем обозначать

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

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) — инцидентным соответствующим вершинам.

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

Граф, для которого из следует называется симметричным. Если из следует , то соответствующий граф называется антисимметричным.

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

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

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

Вершина называется нечётной, если нечётное число. Вершина называется чётной, если чётное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.

В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. Число нечётных вершин любого графа чётно. Во всяком графе с n вершинами, где всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Если в графе с n вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени

Маршруты, цепи, циклы

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

Если то маршрут замкнут, в противном случае открыт.

Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

Простой путь – путь, в котором ни одна дуга не встречается дважды.

Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

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

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

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

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

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

Ориентированные графы

Если элементы множества Е графа упорядоченные пары, то граф называется ориентированным или орграфом.

Ребро графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.

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

Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.

Степенью входа вершины орграфа называется число входящих в вершину рёбер.

В орграфах в зависимости от сочетаний степеней входа и выхода для данной вершины рассматривается три случая.

Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0.

Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.

Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.

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

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

Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.

Длиной пути называется число рёбер в этом пути.

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

Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.

Петлёй называется ребро, у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной.

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

Изоморфизм графов

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

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

Алгоритм распознания изоморфизма двух графов и

1. Подсчитаем число вершин каждого графа (число вершин должно совпадать, в противном случае графы неизоморфные).

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

3. Для каждого элемента х графа ищем такой элемент у графа что выполняется условие: число исходов х совпадает с числом исходов у, и число заходов х совпадает с числом заходов у. Найденные элементы х и у соединяем ребром, т. е. строим граф соответствия (если соответствия нет, то графы не изоморфны).

4. Выписываем подстановку, которая переводит граф в граф .

Плоские графы

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

В качестве характеристики плоского представления графа вводится понятие грани.

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

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

Рассмотрим графы и

а) Дополнением графа называется граф множеством вершин которого является множество а множеством его рёбер является множество

б) Объединением графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер является множество

в) Пересечением графов и называется граф множеством вершин которого является множество а множеством его рёбер является множество

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

Способы задания графов

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

Аналитический способ задания графов

Граф задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.

Пусть дано множество которое имеет мощность

Для того чтобы задать отображение Е на V , необходимо каждому элементу поставить в соответствие некоторое подмножество множества V, которому соответствует отображение Е. Это подмножество обозначают через Поэтому Совокупность двух объектов: множества V и отображение Е на V задаёт некоторый граф.

Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар

Дата добавления: 2019-02-22 ; просмотров: 1716 ; Мы поможем в написании вашей работы!

Источник