Функция Гранди

Функция Гранди — функция в теории графов.

Определение

Рассмотрим орграф $D=(V,X)$ . Функция $g(v)$ , ставящая в соответствие каждой вершине $v\in V$ целое число $g(v)\geqslant 0$ , называется функций Гранди для орграфа $D$ , если в каждой вершине $v\in V$ число $g(v)$ является минимальным из всех целых неотрицательных чисел, не принадлежащих множеству $\left\{g(w)\mid w\in D(v)\right\}$ и $g(v)=0$ при $D(v)=\varnothing$ .

Свойства

Если орграф $D=(V,X)$ допускает функцию Гранди, то найдется вершина $v\in V$ такая, что $g(v)=0$ ^[1].
Пусть $D=(V,X)$ - орграф без контуров. Тогда $D$ допускает и притом единственную функцию Гранди ^[2]. Для графов с контурами справедлив результат "Если граф допускает функцию Гранди $g(v)$ , то существует его подграф, не содержащий контуров, имеющий ту же функцию Гранди $g(v)$ ". (Erusalimsky I.M. Family of Grandy Functions for oriented graphs. Tr. J. Math 19, No 3, 269-273)
Если орграф $D=(V,X)$ допускает функцию Гранди $g(v)$ , то множество вершин $N=\left\{v\in V\mid g(v)=0\right\}$ является ядром этого орграфа^[3].

Примечания

↑ Нефедов, 1992, с. 246.
↑ Нефедов, 1992, с. 247.
↑ Нефедов, 1992, с. 248.

Литература

Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 262 с.

Похожие исследовательские статьи

Ко́мпле́ксные чи́сла — числа вида $\text{[math]}$ где $\text{[math]}$ — вещественные числа, $\text{[math]}$ — мнимая единица, то есть число, для которого выполняется равенство: $\text{[math]}$ Множество комплексных чисел обычно обозначается символом $\text{[math]}$ Вещественные числа можно рассматривать как частный случай комплексных, они имеют вид $\text{[math]}$ Главное свойство $\text{[math]}$ — в нём выполняется основная теорема алгебры, то есть любой многочлен $\text{[math]}$ -й степени имеет $\text{[math]}$ корней. Доказано, что система комплексных чисел логически непротиворечива.

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

Теорема (теория) Редфилда — Пойи — классический результат перечислительной комбинаторики.

Прямое произведение — множество, элементами которого являются все возможные упорядоченные пары элементов заданных двух непустых исходных множеств. Предполагается, что впервые «декартово» произведение двух множеств ввёл Георг Кантор.

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

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

Однородная функция степени $\text{[math]}$ — числовая функция $\text{[math]}$ такая, что для любого $\text{[math]}$ из области определения функции $\text{[math]}$ и любого $\text{[math]}$ выполняется равенство:

\text{[math]}

ρ-Метод Полларда для дискретного логарифмирования — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Предложен британским математиком Джоном Поллардом в 1978 году, основные идеи алгоритма очень похожи на идеи ро-алгоритма Полларда для факторизации чисел. Данный метод рассматривается для группы ненулевых вычетов по модулю $\text{[math]}$ , где $\text{[math]}$ — простое число, большее $\text{[math]}$ .

Кратный интеграл — определённый интеграл, взятый от $\text{[math]}$ переменных; например:

\text{[math]}

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

<span class="mw-page-title-main">Граф Пэли</span> плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадра

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

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

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

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

Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин $\text{[math]}$ графа. Поскольку $\text{[math]}$ цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых $\text{[math]}$ цветов достаточно, и «второго класса», для которых необходимо $\text{[math]}$ цветов.

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

Многочлен Татта — многочлен от двух переменных, играющий большую роль в теории графов; определён для любого неориентированного графа и содержит информацию, насколько граф связен. Стандартное обозначение — $\text{[math]}$ .

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

<span class="mw-page-title-main">T-раскраска</span>

T-раскраска графа $\text{[math]}$ , заданная множеством T неотрицательных целых, содержащим 0, — это функция $\text{[math]}$ , которая отображает каждую вершину графа G в положительное целое (цвет) так, что $\text{[math]}$ . Простыми словами, абсолютное значение разности между двумя цветами смежных вершин должно не принадлежать фиксированному множеству T. Концепцию предложил Уильям К. Хейл. Если T = {0}, это сводится к обычной раскраске вершин.

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

Спектр графа - это множество собственных значений матрицы смежности графа.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.