Как называются элементы графа

Элементы теории графов.

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

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

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

Если в графе все элементы множества изображаются дугами, то граф называется ориентированным или орграфом, если ребрами, то неориентированным. Два ребра называются смежными, если они имеют общий конец.

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

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

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

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

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

Способов задания графов – — великое множество. Самый простой способ – — задание множеств и . Граф также может быть задан просто рисунком. В силу изоморфизма один и тот же граф может быть изображен разными рисунками.


Рис. 1.13.Основной и Определение дополнительныйого графыа

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

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

Маршрут называется циклическим, если . Циклическая цепь называется циклом, а циклическая простая цепь – — простым циклом. Число ребер в маршруте — называется длинойа маршрута. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа. Длина всякого цикла не менее трех в графе без петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.

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


Рис. 1.14.Граф

В подавляющем большинстве случаев граф задается матрицей. Для расчетов на ЭВМ это единственный способ. Наиболее часто граф задают с помощью матриц смежности и инциденций.

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

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

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

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

.

Строки матрицы инциденций называют векторами инциденций графа . Матрица инциденций

также однозначно определяет структуру графа.

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

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

(1.13.6)

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

. (1.13.7)

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

. (1.13.8)

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

Рис. 1.15.Центр графа

Вершина центральная, если . Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин. На рис. 1.15 , , . Таким образом, . Периферийные вершины и , диаметральные цепи и , центральная вершина .

[1] Клод Элвуд Шеннон (1916—2001 гг.) — американский математик.

* Клод Элвуд Шеннон (1916 – 2001) – американский математик.

[2] Ральф Хартли (1881—1970 гг.) — американский инженер и изобретатель.

* Ральф Хартли (1881 – 1970) – американский инженер и изобретатель.

[3] Джино Фано (1871—1952 гг.) — итальянский математик.

* Джино Фано (1871 – 1952) – итальянский математик.

[4] Огастес Морган (де Морган) (1806—1875 гг.) — шотландский математик и логик.

* Огастес Морган (де Морган)(1806 – 1875) – шотландский математик и логик.

[5] Леонард Эйлер (1707—1783 гг.) — швейцарский математик.

* Леонард Эйлер (1707 — — 1783) — — швейцарский математик.

[6] Джон Венн (1834—1923 гг.) — английский математик и логик.

** Джон Венн (1834 — — 1923) — — английский математик и логик.

[K2]Почему в разные стороны / или \?

[S3]Как мне разъяснили наши ‘русистки’ слово пиксель склоняется след. образом:

Знак / в теории множеств используется для записи после него дополнительных условий, а знак \ для обозначения разности множеств.

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

Понятие графа

Дата добавления: 2020-07-23 ; просмотров: 812 ; Нарушение авторских прав

Графом G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е – множество ребер).

Число вершин графа (порядок графа) G обозначим p, а число
ребер – q.

Пусть v1, v2 – вершины, е = (v1, v2) – соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность – отношение между разнородными элементами.

Пример.

Данная диаграмма изображает граф, имеющий четыре вершины и пять ребер. В этом графе вершины v1 и v2 смежны, а вершины v1 и v3 не смежны. Смежные ребра: e1 и e5. Несмежные ребра: e1 и e3. Ребро е1 инцидентно вершинам v1 и v2, вершина v1 инцидентна ребрам е1 и е4.

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

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

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

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

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

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

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

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

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

Граф G’(V’, E’) называется подграфом графа G(V, E) (обозначается G’ I G), если V’ I V, а E’ – множество всех ребер G, оба конца которых принадлежат V’.

Читайте так же:  Как называется изготовление открыток

Двудольный граф (или биграф, или четный граф) – это граф G(V, E), такой что множество V разбито на два непересекающихся множества V1 и V2, причем всякое ребро из Е соединяет вершину из V1 с вершиной из V2. Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если ?V1? = m и ?V2? = n, то полный двудольный граф обозначается Km,n.

Пример. Диаграмма графа K3,3.

Граф, состоящий из простого цикла с k вершинами, обозначается Ck.

Пример. С3 – треугольник.

Количество ребер, инцидентных вершине v, называется (локальной) степенью (или валентностью) вершины v и обозначается d(v):

Если степени всех вершин равны k, то граф называется регулярным (однородным) степени k.

Пример. Диаграмма регулярного графа степени 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а входящих – полустепенью захода. Обозначаются эти числа, соответственно, d – (v) и d + (v).

Если в орграфе полустепень захода некоторой вершины равна нулю (т.е. d + (v) = 0), то такая вершина называется источником, если же нулю равна полустепень исхода (т.е. d – (v) = 0), то вершина называется стоком.

Графы G1 и G2 равны, то есть G1 = G2, если их множества вершин и ребер совпадают: V1 = V2 и E1 = E2. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Пример.

Три внешне различные диаграммы являются диаграммами одного и того же графа.

Дополнением графа G(V1, E1) называется граф `G(V2, E2), где V2 = V1 & E2 = = <e I V1 ? V1 ? e I E1>.

Основные виды графов

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

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

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

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

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

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

Если граф содержит петли, то это обстоятельство специально оговаривают, добавляя к основной харатеристике графа слова «с петлями», например, «орграф с петлями». Если граф не содержит петель, то добавляют слова «без петель».

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

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

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

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

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

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

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

Пример 1. Построить полный двудольный граф.

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

Эйлеров граф

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

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

Пример 2. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом? Объяснить ответ. Привести примеры.

Ответ. Если n — нечётное число, то каждая вершина инцидентна n-1 рёбрам. В таком случае данный граф является эйлеровым графом. Примеры таких графов на рисунке ниже.

Регулярный граф

Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k. Таким образом, на рисунке к примеру 2 изображены примеры регулярных графов, называемых по степени его вершин 4-регулярными и 2-регулярными графами или регулярными графами 4-й степени и 2-й степени.

Число вершин регулярного графа k-й степени не может быть меньше k+1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример 3. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

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

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

Гамильтонов граф

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

Пример 4. Задан двудольный граф, в котором n — число вершин из множества A, а m — число вершин из множества B. В каком случае граф будет эйлеровым графом, а в каком случае — гамильтоновым графом?

Ответ. Если n и n — чётные, то граф будет эйлеровым. Если n = n , то граф будет гамильтоновым.

Взвешенный граф

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

Графы-деревья

Деревом называется связный граф без циклов (рисунок ниже). Любые две вершины дерева соединены лишь одним маршрутом.

Число q рёбер графа находится из соотношения

где n — число вершин дерева.

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

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

Как называются элементы графа

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

Граф, или неориентированный граф — это упорядоченная пара , для которой выполнены следующие условия:

  • — это непустое множествовершин, или узлов,
  • — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
  • (а значит и, , иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

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

    Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

    Два ребра называются смежными, если они имеют общую концевую вершину.

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

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

    Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды).

    Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

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

    Ориентированный граф (сокращённо орграф) — это упорядоченная пара , для которой выполнены следующие условия:

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

    Смешанный граф

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

    Ориентированный и неориентированный графы являются частными случаями смешанного.

    Изоморфные графы

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

    Прочие связанные определения

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

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

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

    Читайте так же:  Как называется отходы от зерна

    Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

  • Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
  • Всякий простой неэлементарный путь содержит элементарный цикл.
  • Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
  • Петля — элементарный цикл.
  • Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

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

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

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

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

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

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

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

    • гиперграф — если ребро может соединять более двух вершин.
    • ультраграф — если между элементами и существуют бинарные отношения инцидентности.
    • Способы представления графа в информатике

      Матрица смежности

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

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

    • Двумерный массив;
    • Матрица с пропусками;
    • Неявное задание (при помощи функции).
    • Матрица инцидентности

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

      1 в случае, если связь «выходит» из вершины , ?1, если связь «входит» в вершину, 0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

      Данный способ является самым ёмким (размер пропорционален ) для хранения, но облегчает нахождение циклов в графе.

      Список рёбер

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

      Языки описания и программы построения графов

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

      Отметим специализированные коммерческие программы для построения графов:

      Из бесплатных можно отметить:

      Для визуализации графов можно использовать:

      • Graphviz
      • LION Graph Visualizer.
      • Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом.
      • Gephi — графическая оболочка для представления и изучения графов.
      • См. также

        • Словарь терминов теории графов
        • Визуализация графов
        • Система графов
        • Прямое произведение графов
        • Теоремы теории графов
        • Boost Graph — Библиотека для работы с графами на языке C++
        • Литература

        • Оре О. Теория графов. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
        • Ошемков А.А. Лекции по наглядной геометрии и топологии http://dfgm.math.msu.su/files/0ngit/oshemkov/00ngit.pdf
        • Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu
        • Харари Ф. Теория графов. М.: Мир, 1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu
        • Кормен Т. М.и др.Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М .: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
        • Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М .: Физико-математическая литература, 1997. — ISBN 5-02-015033-9
        • Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
        • Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. — 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdfhttp://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
        • Wikimedia Foundation . 2010 .

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

          Граф — Граф: От древневерхненемецкого gravo, gravio «предводитель, вождь»: Граф (титул) дворянский титул; «Граф» короткометражная немая кинокомедия Чарли Чаплина (The Count, 1916). От греч. ????? «царапаю, черчу, пишу»: Граф… … Википедия

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

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

          Граф Келли (теория групп) — Граф Кэли граф, который строится по группе с выделенной системой образующих. Назван в честь английского математика Артура Кэли (A. Cayley). Определение Пусть дана дискретная группа G и система образующих S. Предположим S = S ? 1, то есть, для… … Википедия

          Граф Петерсена — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

          ГРАФ СЛУЧАЙНЫЙ — вероятностная модель, предназначенная для изучения частотных характеристик различных параметров графов. Под Г. с. обычно понимается нек рый класс графов на к ром задано распределение вероятностей. Произвольный конкретный граф Gиз наз. реализацией … Математическая энциклопедия

          Граф — Антон (Graf, Anton) 1736, Винтертур 1813, Дрезден. Немецкий живописец. Учился в 1753 1756 у И. У. Шелленберга в Винтертуре, затем у И. Я. Хайда в Аугсбурге. Работал как портретист в Регенсбурге, Винтертуре, Аугсбурге, Мюнхене, Цюрихе. С 1766… … Европейское искусство: Живопись. Скульптура. Графика: Энциклопедия

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

          Гамильтонов граф — Граф додекаэдра с выделенным циклом Гамильтона … Википедия

          Планарный граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия

          2 1 Основные понятия и определения графа и его элементов

          Лекция 1.

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

          2.1. Основные понятия и определения графа и его элементов

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

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

          Е сли ребро графа G соединяет две его вершины V и W, (т.е. ), то говорят, что это ребро им инцидентно . Две вершины графа называются смежными , если существует инцидентное им ребро: на рис. 2.1, а смежными являются вершины А и В, А и С. Если граф G имеет ребро , у которого начало и конец совпадают, то это ребро называется петлёй . На рис. 2.1, б петля — . Два ребра называются смежными , если они имеют общую вершину.

          Рёбра, которые начинаются в одной и той же вершине, заканчиваются также в одной и той же вершине, называются кратными, или параллельными. Количество одинаковых пар вида называется кратностью ребра . Число рёбер, инцидентных вершине А, называется степенью этой вершины и обозначается (от англ. degree – степень).

          Вершина графа, имеющая степень, равную нулю, называется изолированной . Граф, состоящий из изолированных вершин, называется нуль-графом . Вершина графа, имеющая степень, равную 1, называется висячей .

          Теорема 2.1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа:

          где — число вершин; — число рёбер графа.

          Вершина называется чётной (нечётной) , если её степень – чётное (нечётное) число.

          Теорема 2.2. Число нечётных вершин любого графа – чётно.

          Следствие. Невозможно начертить граф с нечётным числом нечётных вершин.

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

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

          Если все пары во множестве X являются упорядоченными, т.е. кортежами длины 2, то граф называется ориентированным , орграфом , или направленным . Началом ребра называется вершина, указанная в кортеже первой, концом – вторая вершина этой пары (графически она указана стрелкой). Рёбра ориентированного графа имеют определённые фиксированные начало и конец и называются дугами .

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

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

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

          Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой маршрут. Обозначается как (от лат. distantio – расстояние) .

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

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

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

          Цепь, путь и цикл в графе называются простыми , если они проходят через любую из вершин не более одного раза. Неориентированный граф называется связным , если между любыми двумя его вершинами есть маршрут . Так, графы G 1 и G 3 (рис. 2.1, а , в ) являются связными, а граф G 2 (рис. 2.1, б ) – несвязным .

          Две вершины называются связными, если существует маршрут между ними. Связность между вершинами является отношением эквивалентности.

          Все подграфы V i (классы эквивалентности) графа G называют связными компонентами , или компонентами связности .

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

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

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

          Теорема 2.4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.

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

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

          Т еорема 2.5 (Эйлера). Связный плоский граф с n вершинами и m рёбрами разбивает плоскость на r областей (включая внешнюю), причём .

          Задача 16 «О трёх колодцах». Проложить дорожки от трёх домов к каждому из трёх колодцев так, чтобы никакие две дорожки не пересекались.

          Решение: Предположим, что эти 9 тропинок можно проложить. Обозначим домики точками А, В, С, колодцы — точками К1, К2, К3. Каждую точку-дом соединим с каждой точкой-колодцем. Получились ребра (графа) в количестве девяти штук, которые попарно не пересекаются. Такие ребра образуют на рассматриваемой плоскости задачи многоугольник, поделенный на меньшие многоугольники. Для такого разбиения должно выполняться известное соотношение Эйлера п — т + r = 2, причем n = 6 и m = 9. Получается, r = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, так как, по условию задачи Эйлера, ни одна из дорожек не должна напрямую соединять два колодца или два дома. Так как любое ребро лежит ровно в 2-х гранях, то количество ребер графа должно быть не меньше 5*4/2 = 10 . Это противоречит условию исходной задачи, по которому их число равно девять ! Полученное противоречие доказывает, что ответ в задаче о 3х колодцах Эйлера отрицателен .

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

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

          Теорема 2.6. Граф G является эйлеровым тогда и только тогда, когда G – связный граф, имеющий все чётные вершины.

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

          З адача 17 «О кёнигсбергских мостах» (Эйлера). Необходимо обойти все 7 мостов так, чтобы на каждом побывать только один раз и вернуться к началу пути (рис. 2.3).

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

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

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

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

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

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

          2.3. Деревья. Лес. Бинарные деревья

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

          Для каждой пары вершин дерева – узлов – существует единственный маршрут, поэтому вершины удобно классифицировать по степени удалённости от корневой вершины. Расстояние до корневой вершины называется ярусом s вершины, .

          Теорема 2.7. Граф является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

          граф связен и не содержит циклов;

          граф не содержит циклов и имеет п – 1 ребро ;

          граф связен и имеет п – 1 ребро ;

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

          граф связный, но утрачивает это свойство после удаления любого ребра;

          в графе всякая пара вершин соединена цепью, и только одной.

          Висячие вершины, за исключением корневой, называются листьями.

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

          Кодеревом остова Т графа G называется дополнение Т до G, т.е. такой его подграф, который содержит все его вершины и только те его рёбра, которые не входят в Т .

          При описании деревьев принято использовать термины: отец, сын, предок, потомок.

          К аждая вершина дерева называется узлом, причём каждый узел является корнем дерева, состоящего из поддеревьев. Узел k -го яруса называется отцом узла ( k + 1)–го яруса, если они смежны. Узел ( k + 1)–го яруса называется сыном узла k -го яруса. Два узла, имеющие одного отца, называются братьями (рис. 2.5).

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

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

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

          Цикломатическое число графа. Цикломатическим числом неориентированного графа G называется число , где — число его рёбер; — число связных компонент графа; — число вершин.

          2.4. Способы задания графа. Изоморфные графы

          Геометрическое представление плоского графа называется его реализацией.

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

          Граф можно задавать таблицей, состоящей из п строк (вершины) и т столбцов (рёбра).

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

          Матрицей инцидентности называется таблица В, состоящая из п строк (вершины) и т столбцов (рёбра), в которой:

          для неориентированного графа:

          , если вершина инцидентна ребру ;

          , если вершина не инцидентна ребру ;

          для ориентированного графа:

          , если вершина является началом дуги ;

          , если вершина не инцидентна дуге ;

          , если вершина является концом дуги .

          Матрицей смежности графа без кратных рёбер называется квадратная матрица А порядка п , в которой:

          , если ; , если .

          При восстановлении графа по его матрице инцидентности можно получить граф лишь с точностью до изоморфизма.

          З адача 18. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

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

          Задача 19. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

          Решение. Диаграмму графа, имеющего шесть вершин, можно представить следующим образом (рис. 2.7).