Дуга (теория графов) | это... Что такое Дуга (теория графов)? (original) (raw)

Дуга (теория графов)

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

# А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я

А

Автоморфизм — Изоморфизм графа с самим собой.

Б

Биграф — см. двудольный граф.
Блок-дизайн с параметрами (v, k, λ) — покрытие с кратностью λ полного графа на v вершинах полными графами на k вершинах.

В

Валентность вершины — см. Степень вершины
Вершина, Узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G)
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Висячая вершина — вершина, степень которой равна 1 (то есть d(v) = 1)
Вполне несвязный граф (пустой граф, нуль-граф) — регулярный граф степени 0, то есть граф без рёбер.
Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра

Г

Гамильтонов граф — граф, в котором есть гамильтонов цикл.
Гамильтонов путь — простой путь в графе, содержащий все вершины графа ровно по одному разу.
Гамильтонов цикл — простой цикл в графе, содержащий все вершины графа ровно по одному разу.
Геометрическая реализация — фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе.
Геометрический граф — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
Гиперграф — совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин).
Гомеоморфные графы — графы, получаемые из одного графа с помощью последовательности подразбиений рёбер.
Грань — область, ограниченная рёбрами в плоском графе, и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань.
Граф — базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяют ровно две вершины).
Граф рода g — граф, который можно изобразить без пересечений на поверхности рода g и нельзя изобразить без пересечений ни на одной поверхности рода g-1.

Д

Двойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа A соединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро.
Двудольный граф (или биграф, или чётный граф) — это граф G(V,E), такой что множество вершин V разбито на два непересекающихся подмножества _V_1 и _V_2, причём всякое ребро E инцидентно вершине из _V_1 и вершине из _V_2 (то есть соединяет вершину из _V_1 с вершиной из _V_2). То есть, правильная раскраска графа двумя цветами. Множества _V_1 и _V_2 называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из _V_1 и _V_2 являются смежными. Если $\left|V_1\right| = a$ , $\left|V_2\right| = b$ , то полный двудольный граф обозначается K a,b.
Дерево — связный граф, не содержащий циклов.
Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.
Длина маршрута — количество рёбер в маршруте (с повторениями). Если маршрут M = _v_0,_e_1,_v_1,_e_2,_v_2,...,e k,v k, то длина M равна k (обозначается $\left|M\right|=k$ ).
Длина пути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v1, v2, …, vn длина равна n-1.
Дуга — это ориентированное ребро.
Дополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.

И

Изолированная вершина — вершина, степень которой равна 0 (то есть нет ребер инцидентных ей).
Изоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
Интервальный граф — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины инцидентны одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
Инцидентность — понятие, используемое только в отношении ребра и вершины: если _v_1,_v_2 — вершины, а e = (_v_1,_v_2) — соединяющее их ребро, тогда вершина _v_1 и ребро e инцидентны, вершина _v_2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

К

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

Л

Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья.

М

Маршрут в графе — это чередующаяся последовательность вершин и рёбер _v_0,_e_1,_v_1,_e_2,_v_2,...,e k,v k, в которой любые два соседних элемента инцидентны. Если _v_0 = v k, то маршрут замкнут, иначе открыт.
Матрица достижимости орграфа — это матрица, содержащая информацию о существовании путей между вершинами в орграфе.
Матрица инцидентности графа — это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
Матрица смежности графа — это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обоим вершинам). Петля считается сразу двумя соединениями для вершины, то есть к значению элемента матрицы в таком случае следует прибавлять 2.
Минимальный каркас (или Каркас минимального веса, Минимальное остовное дерево) графа — ациклическое множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нем минимальна.
Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается Γ + (v)
Мультиграф — граф, в котором существует пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

Н

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

О

Обхват — длина наименьшего цикла в графе.
Окружение — длина наибольшего простого цикла в графе.
Орграф, ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведет от вершины v к вершине w, при этом вершина w смежная с вершиной v.
Остовом (неориентированного) связного графа G=(V,E) называется его частичный граф S=(V,T), являющийся деревом.
Остовный подграф — подграф, содержащий все вершины.

П

Петля — ребро, начало и конец которого находятся в одной и той же вершине.
Планарный граф — граф, который может быть изображён (уложен) на плоскости без пересечения рёбер. Изоморфен плоскому графу, то есть, является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от плоского графа изображением на плоскости . Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.
Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству. (ср. Суграф.)
Полным графом называется граф, в котором для каждой пары вершин _v_1,_v_2, существует ребро, инцидентное _v_1 и инцидентное _v_2 (каждая вершина соединена ребром с любой другой вершиной)
Полным двудольным называется двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
Полустепень захода в орграфе для вершины v — число дуг, входящих в вершину. Обозначается d + (v).
Полустепень исхода в орграфе для вершины v — число дуг, исходящих из вершины. Обозначается d − (v).
Правильная раскраска графа — раскраска, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
Простая цепь — маршрут, в котором все вершины различны.
Простой граф — граф, в котором нет кратных рёбер и петель.
Простой путь — путь, все рёбра которого попарно различны. Другими словами, простой путь не проходит дважды через одно ребро.
- Простой цикл — цикл, не проходящий дважды через одну вершину.
Псевдограф — граф, содержащий петли.
Пустой граф (вполне несвязный граф, нуль-граф) — регулярный граф степени 0, то есть граф, не содержащий рёбер.
Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер) в которой каждый элемент инцидентен предыдущему и последующему. Может рассматриваться как частный случай маршрута.
Путь в орграфе — это последовательность вершин v1, v2, …, vn, для которой существуют дуги v1 → v2, v2 → v3, …, vn-1 → vn. Говорят, что этот путь начинается в вершине v1, проходит через вершины v2, v3, …, vn-1, и заканчивается в вершине vn.

Р

Развёртка графа — функция, заданная на вершинах ориентированного графа.
Размеченный граф — граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.
Разрез — множество ребер, удаление которого делает граф несвязным.
Раскраска графа — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.
Ребро графа — базовое понятие. Ребро соединяет две вершины графа.
Регулярный граф — граф, степени всех вершин которого равны. Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
- Регулярный граф степени 0 (вполне несвязный граф, пустой граф, нуль-граф) — граф без рёбер.

С

Самодвойственный граф — граф, изоморфный своему двойственному графу.
Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
Связный граф — граф, в котором все вершины связаны.
Сечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
Сеть — в принципе, то же, что и граф, хотя сетями обычно называют графы, вершины которых определённым образом помечены.
Сильная связность. Две вершины в ориентированном графе сильно связаны, если существует путь из первой во вторую и из второй в первую.
- Сильно связный орграф — орграф, в котором все вершины сильно связаны.
Смежность — понятие, используемое в отношении только двух рёбер либо только двух вершин: Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. (ср. Инцидентность.)
Смешанный граф — граф, содержащий как ориентированные, так и неориентированные рёбра.
Спектр графа — множество всех собственных значений матрицы смежности с учетом кратных рёбер.
Степень вершины v — количество рёбер, инцидентных вершине v. Обозначается d(v). Минимальная степень вершины графа G обозначается δ(G). а максимальная — Δ(G).
Стягивание ребра графа — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф _G_1 стягиваем к _G_2, если второй можно получить из первого последовательностью стягиваний рёбер.
Суграф (частичный граф) исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер. (ср. Подграф.)

Т

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

У

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

Ф

n-Фактор графа — регулярный остовный подграф степени n.
n-Факторизация графа — разбиение графа на независимые n-факторы.

Х

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

Ц

Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи _v_0,_e_1,...,e k,v k вершины _v_0 и v k называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v обозначается $\left\langle u,v\right\rangle$ . Для орграфов цепь называется орцепью.
В некоторых источниках простая цепь — цепь, рёбра которой различны, что является более слабым условием.
Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
- Цикл (простой цикл) в орграфе — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.
- Цикл Гамильтона — то же, что и Гамильтонов цикл.
Цикломатическое число графа — число компонент связности графа плюс число рёбер минус число вершин.

Ч

Частичный граф — то же, что и суграф.
Чётный граф — то же, что и двудольный граф.

Э

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

Ссылки

Литература

Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6

Wikimedia Foundation.2010.

Полезное

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

Граф (теория графов) — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Путь (теория графов) — У этого термина существуют и другие значения, см. Путь. Путь (Цепь) в графе последовательность вершин при , таких, что две любые последовательные вершины соединены хотя бы одной дугой из . Число рёбер в пути называется его длиной. Каждая из пар… … Википедия
Дуга — Дуга: В математике Дуга (геометрия) участок кривой между двумя её точками. Дуга окружности кривая линия, лежащая на окружности и ограниченная двумя точками. Дуга (теория графов) Другое Дуга (география) Дуга (анатомия) Дуга (физика) Дуга… … Википедия
ГРАФОВ ТЕОРИЯ — в химии, область конечной математики, изучающая дискретные структуры, наз. графами; применяется для решения различных теоретич. и прикладных задач. Некоторые основные понятия. Граф совокупность точек (вершин) и совокупность пар этих точек (не… … Химическая энциклопедия
Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
ГРАФ — множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,… … Математическая энциклопедия
Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия