Свойство графа - Graph property

Пример графа со свойствами быть планарный и быть связанный, а при заказе 6 размер 7, диаметр 3, обхват 3, связность вершин 1, и последовательность степеней <3, 3, 3, 2, 2, 1>

В теория графов, а свойство графа или инвариант графа является собственностью графики это зависит только от абстрактной структуры, а не от представлений графов, таких как конкретные маркировка или рисунки графа.^[1]

Определения

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

Более формально свойство графа - это класс графов со свойством, что любые два изоморфный графы либо оба принадлежат классу, либо оба не принадлежат ему.^[1] Аналогично, свойство графа может быть формализовано с помощью индикаторная функция класса, функция от графиков до логических значений, которая истинна для графиков в классе и ложна в противном случае; опять же, любые два изоморфных графика должны иметь то же значение функции, что и друг друга. Инвариант графика или параметр графика можно аналогичным образом формализовать как функцию от графиков до более широкого класса значений, таких как целые числа, действительные числа, последовательности чисел или многочлены, который снова имеет одинаковое значение для любых двух изоморфных графов.^[2]

Свойства недвижимости

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

Свойство графа п является наследственный если каждый индуцированный подграф графа со свойством п также имеет собственность п. Например, будучи идеальный график или быть хордовый граф являются наследственными свойствами.^[1]
Свойство графа монотонный если каждый подграф графа со свойством п также имеет собственность п. Например, будучи двудольный граф или быть граф без треугольников монотонный. Каждое монотонное свойство наследственно, но не обязательно наоборот; например, подграфы хордовых графов не обязательно хордовые, поэтому хордовый граф не является монотонным.^[1]
Свойство графа минор-закрыто если каждый граф минор графа со свойством п также имеет собственность п. Например, будучи планарный граф минор-закрыто. Каждое свойство с закрытым миноре монотонно, но не обязательно наоборот; например, миноры графов без треугольников не обязательно сами по себе не содержат треугольников.^[1]

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

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

Инвариант графа добавка если для всех двух графиков г и ЧАС, значение инварианта на несвязном объединении г и ЧАС это сумма значений на г и дальше ЧАС. Например, количество вершин аддитивно.^[1]
Инвариант графа мультипликативный если для всех двух графиков г и ЧАС, значение инварианта на несвязном объединении г и ЧАС это продукт значений на г и дальше ЧАС. Например, Индекс Хосоя (количество совпадений) мультипликативно.^[1]
Инвариант графа максинг если для всех двух графиков г и ЧАС, значение инварианта на несвязном объединении г и ЧАС это максимальное из значений на г и дальше ЧАС. Например, хроматическое число макс.^[1]

Кроме того, свойства графа можно классифицировать в соответствии с типом графа, который они описывают: является ли граф ненаправленный или направленный, относится ли свойство к мультиграфы, так далее.^[1]

Значения инвариантов

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

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

Инварианты графов и изоморфизм графов

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

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

Примеры

Свойства

Целочисленные инварианты

порядок, количество вершин
Размер, количество ребер
Количество связанные компоненты
Ранг цепи, линейная комбинация количества ребер, вершин и компонентов
диаметр, самый длинный из самых коротких дорожка длины между парами вершин
обхват, длина кратчайшего цикла
Связность вершин, наименьшее количество вершин, удаление которых разъединяет граф
Пограничное соединение, наименьшее количество ребер, удаление которых разъединяет граф
Хроматическое число, наименьшее количество цветов для вершин в правильной раскраске
Хроматический индекс, наименьшее количество цветов для краев в правильной окраске краев
Возможность выбора (или список хроматических чисел) наименьшее число k такое, что G является k-choosable
Число независимости, наибольший размер независимого множества вершин
Номер клики, наибольший порядок полного подграфа
Древесность
Род графа
Номер страницы
Индекс Хосоя
Индекс Винера
Граф инвариант Колена де Вердьера
Токсичность

Инварианты действительных чисел

Последовательности и многочлены

Последовательность степеней
Спектр графика
Характеристический полином из матрица смежности
Хроматический полином, номер ${ displaystyle k}$ -цветность рассматривается как функция ${ displaystyle k}$
Полином Тутте, двумерная функция, которая кодирует большую часть связности графа

Смотрите также

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

использованная литература

^ ^а ^б ^c ^d ^е ^ж ^г ^час ^я Ловас, Ласло (2012), «4.1 Параметры графа и свойства графа», Большие сети и пределы графа, Публикации коллоквиума, 60, Американское математическое общество, стр. 41–42..
^ Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «3.10 Параметры графика», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Springer, стр. 54–56, Дои:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Г-Н 2920058.

[l-1] а ^б ^c ^d ^е ^ж ^г ^час ^я Ловас, Ласло (2012), «4.1 Параметры графа и свойства графа», Большие сети и пределы графа, Публикации коллоквиума, 60, Американское математическое общество, стр. 41–42..

[2] Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «3.10 Параметры графика», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Springer, стр. 54–56, Дои:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Г-Н 2920058.

[1]

[2]