Логотип
Юнионпедия
Связь
Доступно в Google Play
Новый! Скачать Юнионпедия на вашем Android™ устройстве!
Свободно
Более быстрый доступ, чем браузер!
 

Глоссарий теории графов

Индекс Глоссарий теории графов

Здесь собраны определения терминов из теории графов.

66 отношения: Кратные рёбра, Клика (теория графов), Клетка (теория графов), Коцикл, Колесо (теория графов), Компонента связности графа, Компонента сильной связности в орграфе, Контурный ранг, Путь (теория графов), Паросочетание, Планарный граф, Полный граф, Петля (теория графов), Пересечение графов, Перечисление графов, Остовное дерево, Ориентированный граф, Объединение графов, Обхват (теория графов), Автоморфизм, Алгоритм Дейкстры, Направленный ациклический граф, Необходимое и достаточное условия, Разрез графа, Разбиение графа, Развёртка графа, Рамочный граф, Регулярный граф, Степень вершины (теория графов), Связный граф, Турнир (теория графов), Точка (геометрия), Тождественный граф, Укрытие (теория графов), Функция (математика), Хроматическое число, Шарнир (теория графов), Эйлеров цикл, Мультиграф, Матрица смежности, Матрица достижимости, Матрица инцидентности, Минимальное остовное дерево, Многодольный граф, Мост (теория графов), Мера множества, Издательская группа URSS, Изоморфизм графов, Интервальный граф, Инвариант (математика), ..., Инвариант графа, Блок-дизайн, Вершина (теория графов), Граф (математика), Граф-звезда, Гамильтонов граф, Гиперграф, Глоссарий теории графов, Двудольный граф, Двоичная система счисления, Двойственный граф, Диаметр, Дополнение графа, Дерево (теория графов), Ежевика (теория графов), Ламанов граф. Развернуть индекс (16 больше) »

Кратные рёбра

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

Новый!!: Глоссарий теории графов и Кратные рёбра · Узнать больше »

Клика (теория графов)

Граф с 23 кликами, содержащими 1 вершину (вершины графа), 42 кликами, состоящими из 2 вершин (рёбра графа), 19 кликами, состоящими из 3 вершин (закрашенные треугольники) и двумя кликами, состоящими из 4 вершин (тёмно-синие области).Шесть рёбер не входят ни в один треугольник и 11 светло-голубых треугольников образуют максимальные клики.Две тёмно-синие 4-клики являются как наибольшими, так и максимальными, и кликовое число графа равно 4. В теории графов кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром.

Новый!!: Глоссарий теории графов и Клика (теория графов) · Узнать больше »

Клетка (теория графов)

Граф Петерсена Граф Хивуда Граф МакГи Граф Татта — Коксетера Граф Гофмана-Синглтона n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин.

Новый!!: Глоссарий теории графов и Клетка (теория графов) · Узнать больше »

Коцикл

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

Новый!!: Глоссарий теории графов и Коцикл · Узнать больше »

Колесо (теория графов)

В теории графов колесом Wn называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.

Новый!!: Глоссарий теории графов и Колесо (теория графов) · Узнать больше »

Компонента связности графа

Несвязный граф с тремя компонентами связности Компонента связности графа G (или просто компонента графа G) — максимальный (по включению) связный подграф графа G.

Новый!!: Глоссарий теории графов и Компонента связности графа · Узнать больше »

Компонента сильной связности в орграфе

Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связны.

Новый!!: Глоссарий теории графов и Компонента сильной связности в орграфе · Узнать больше »

Контурный ранг

1.

Новый!!: Глоссарий теории графов и Контурный ранг · Узнать больше »

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

Граф-путь с 6 вершинами Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Новый!!: Глоссарий теории графов и Путь (теория графов) · Узнать больше »

Паросочетание

В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

Новый!!: Глоссарий теории графов и Паросочетание · Узнать больше »

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

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

Новый!!: Глоссарий теории графов и Планарный граф · Узнать больше »

Полный граф

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

Новый!!: Глоссарий теории графов и Полный граф · Узнать больше »

Петля (теория графов)

Граф, содержащий петлю при вершине 1 Пе́тля́ в графе — ребро, инцидентное одной и той же вершине.

Новый!!: Глоссарий теории графов и Петля (теория графов) · Узнать больше »

Пересечение графов

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

Новый!!: Глоссарий теории графов и Пересечение графов · Узнать больше »

Перечисление графов

Полный список всех деревьев с 2,3 и 4 помеченными вершинами: 2^2-2.

Новый!!: Глоссарий теории графов и Перечисление графов · Узнать больше »

Остовное дерево

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

Новый!!: Глоссарий теории графов и Остовное дерево · Узнать больше »

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

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

Новый!!: Глоссарий теории графов и Ориентированный граф · Узнать больше »

Объединение графов

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

Новый!!: Глоссарий теории графов и Объединение графов · Узнать больше »

Обхват (теория графов)

Обхват в теории графов — длина наименьшего цикла, содержащегося в данном графе.

Новый!!: Глоссарий теории графов и Обхват (теория графов) · Узнать больше »

Автоморфизм

Автоморфизм алгебраической системы — изоморфизм, отображающий алгебраическую систему на себя.

Новый!!: Глоссарий теории графов и Автоморфизм · Узнать больше »

Алгоритм Дейкстры

Блок-схема алгоритма Дейкстры. Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году.

Новый!!: Глоссарий теории графов и Алгоритм Дейкстры · Узнать больше »

Направленный ациклический граф

250px Направленный ациклический граф (ориентированный ациклический граф, DAG от directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел.

Новый!!: Глоссарий теории графов и Направленный ациклический граф · Узнать больше »

Необходимое и достаточное условия

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

Новый!!: Глоссарий теории графов и Необходимое и достаточное условия · Узнать больше »

Разрез графа

Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что.

Новый!!: Глоссарий теории графов и Разрез графа · Узнать больше »

Разбиение графа

параллельных вершин Разбиение графа на подграфы (Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа G.

Новый!!: Глоссарий теории графов и Разбиение графа · Узнать больше »

Развёртка графа

Развёртка графа — функция, заданная над вершинами ориентированного графа и удовлетворяющая ряду условий.

Новый!!: Глоссарий теории графов и Развёртка графа · Узнать больше »

Рамочный граф

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

Новый!!: Глоссарий теории графов и Рамочный граф · Узнать больше »

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

Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей.

Новый!!: Глоссарий теории графов и Регулярный граф · Узнать больше »

Степень вершины (теория графов)

Рис. 1. Граф, на вершинах которого отмечены степени. Степень или валентность вершины графа — количество рёбер графа G, инцидентных вершине x. При подсчёте степени ребро-петля учитывается дважды.

Новый!!: Глоссарий теории графов и Степень вершины (теория графов) · Узнать больше »

Связный граф

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

Новый!!: Глоссарий теории графов и Связный граф · Узнать больше »

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

Турнир с 4 вершинами вершин n рёбер: \binomn2 Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру.

Новый!!: Глоссарий теории графов и Турнир (теория графов) · Узнать больше »

Точка (геометрия)

Набор точек на плоскости То́чка — абстрактный объект в пространстве, не имеющий никаких измеримых характеристик (нульмерный объект).

Новый!!: Глоссарий теории графов и Точка (геометрия) · Узнать больше »

Тождественный граф

Тожде́ственный граф (асимметри́чный граф) — граф, группа автоморфизмов которого состоит из одного единственного тождественного автоморфизма.

Новый!!: Глоссарий теории графов и Тождественный граф · Узнать больше »

Укрытие (теория графов)

В теории графов укрытие — это определённый тип функции на множествах вершин неориентированного графа.

Новый!!: Глоссарий теории графов и Укрытие (теория графов) · Узнать больше »

Функция (математика)

График функции \beginalign&\scriptstyle \\ &\textstyle f(x).

Новый!!: Глоссарий теории графов и Функция (математика) · Узнать больше »

Хроматическое число

графа Петерсена. Для раскраски этого графа достаточно 3 разных цвета, его хроматическое число равно 3. Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета.

Новый!!: Глоссарий теории графов и Хроматическое число · Узнать больше »

Шарнир (теория графов)

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

Новый!!: Глоссарий теории графов и Шарнир (теория графов) · Узнать больше »

Эйлеров цикл

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

Новый!!: Глоссарий теории графов и Эйлеров цикл · Узнать больше »

Мультиграф

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

Новый!!: Глоссарий теории графов и Мультиграф · Узнать больше »

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

Матрица смежности — один из способов представления графа в виде матрицы.

Новый!!: Глоссарий теории графов и Матрица смежности · Узнать больше »

Матрица достижимости

Матрица достижимости простого ориентированного графа G.

Новый!!: Глоссарий теории графов и Матрица достижимости · Узнать больше »

Матрица инцидентности

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

Новый!!: Глоссарий теории графов и Матрица инцидентности · Узнать больше »

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

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

Новый!!: Глоссарий теории графов и Минимальное остовное дерево · Узнать больше »

Многодольный граф

k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (доль).

Новый!!: Глоссарий теории графов и Многодольный граф · Узнать больше »

Мост (теория графов)

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

Новый!!: Глоссарий теории графов и Мост (теория графов) · Узнать больше »

Мера множества

Ме́ра мно́жества — неотрицательная величина, интуитивно интерпретируемая как размер (объём) множества.

Новый!!: Глоссарий теории графов и Мера множества · Узнать больше »

Издательская группа URSS

Издательская группа URSS (исп. Editorial URSS) — российская издательская группа учебной и научной литературы, в том числе монографий, журналов, сборников трудов РАН, НИИ и учебных заведений.

Новый!!: Глоссарий теории графов и Издательская группа URSS · Узнать больше »

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

В теории графов изоморфизмом графов G.

Новый!!: Глоссарий теории графов и Изоморфизм графов · Узнать больше »

Интервальный граф

Семь интервалов на прямой и соответствующий интервальный граф с семью вершинами. Интервальный граф — граф пересечений мультимножества интервалов на прямой.

Новый!!: Глоссарий теории графов и Интервальный граф · Узнать больше »

Инвариант (математика)

Инвариа́нт — это свойство некоторого класса (множества) математических объектов, остающееся неизменным при преобразованиях определённого типа.

Новый!!: Глоссарий теории графов и Инвариант (математика) · Узнать больше »

Инвариант графа

Инвариа́нт гра́фа в теории графов — некоторое обычно числовое значение или упорядоченный набор значений (хэш-функция), характеризующее структуру графа G.

Новый!!: Глоссарий теории графов и Инвариант графа · Узнать больше »

Блок-дизайн

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

Новый!!: Глоссарий теории графов и Блок-дизайн · Узнать больше »

Вершина (теория графов)

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

Новый!!: Глоссарий теории графов и Вершина (теория графов) · Узнать больше »

Граф (математика)

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

Новый!!: Глоссарий теории графов и Граф (математика) · Узнать больше »

Граф-звезда

Граф-звезда ''S7'' В теории графов граф-звезда Sk — это полный двудольный граф K1,k.

Новый!!: Глоссарий теории графов и Граф-звезда · Узнать больше »

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

Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа. Гамильто́нов граф — математический объект теории графов.

Новый!!: Глоссарий теории графов и Гамильтонов граф · Узнать больше »

Гиперграф

Пример гиперграфа: V.

Новый!!: Глоссарий теории графов и Гиперграф · Узнать больше »

Глоссарий теории графов

Здесь собраны определения терминов из теории графов.

Новый!!: Глоссарий теории графов и Глоссарий теории графов · Узнать больше »

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

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

Новый!!: Глоссарий теории графов и Двудольный граф · Узнать больше »

Двоичная система счисления

Двоичная система счисления — позиционная система счисления с основанием 2.

Новый!!: Глоссарий теории графов и Двоичная система счисления · Узнать больше »

Двойственный граф

Граф G' двойственен к G Двойственный граф G' к планарному графу G — это граф, в котором вершины соответствуют граням графа G; две вершины соединены ребром если и только если соответствующие им грани графа G имеют общее ребро.

Новый!!: Глоссарий теории графов и Двойственный граф · Узнать больше »

Диаметр

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

Новый!!: Глоссарий теории графов и Диаметр · Узнать больше »

Дополнение графа

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

Новый!!: Глоссарий теории графов и Дополнение графа · Узнать больше »

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

Дерево — это связный ациклический граф.

Новый!!: Глоссарий теории графов и Дерево (теория графов) · Узнать больше »

Ежевика (теория графов)

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

Новый!!: Глоссарий теории графов и Ежевика (теория графов) · Узнать больше »

Ламанов граф

Веретено Мозера, планарный Ламанов граф Полный двудольный граф ''K''3,3, непланарный Ламанов граф Лама́нов граф — граф из семейства разреженных графов, описывающий минимальные отрезков и шарниров на плоскости.

Новый!!: Глоссарий теории графов и Ламанов граф · Узнать больше »

Перенаправления здесь:

Ациклический граф, Нулевой граф, Ребро (граф), Ребро (теория графов), Словарь терминов теории графов, Степень (теория графов), Узел (граф), Узел (теория графов), Цепь (теория графов), Цепь в графе, Цикл в орграфе, Эксцентриситет вершины, Кликовое число, Конечный граф, Подграф, Полустепень захода, Полустепень исхода, Помеченный граф, Псевдограф, Простой граф, Окрестность (теория клеточных автоматов), Инцидентность, Бесконечный граф, Вес (теория графов), Вершина графа, Взвешенный граф, Дуга (теория графов).

ИсходящиеВходящий
Привет! Мы на Facebook сейчас! »