В теории графов свойство графа или инвариант графа — это свойство графа , которое зависит только от абстрактной структуры, а не от представлений графа, таких как конкретные обозначения или рисунки графа. [1]
Определения
Хотя рисование и представление графов являются допустимыми темами в теории графов, чтобы сосредоточиться только на абстрактной структуре графов, свойство графа определяется как свойство, сохраняющееся при всех возможных изоморфизмах графа. Другими словами, это свойство самого графа, а не конкретного рисунка или представления графа. Неофициально термин «инвариант графа» используется для свойств, выраженных количественно, тогда как «свойство» обычно относится к описательным характеристикам графов. Например, утверждение «граф не имеет вершин степени 1» является «свойством», а «количество вершин степени 1 в графе» является «инвариантом».
Более формально, свойство графа — это класс графов, обладающий свойством, согласно которому любые два изоморфных графа либо оба принадлежат этому классу, либо оба ему не принадлежат. [1] Аналогичным образом, свойство графа может быть формализовано с использованием индикаторной функции класса, функции преобразования графиков в логические значения, которая является истинной для графов в классе и ложной в противном случае; опять же, любые два изоморфных графа должны иметь одно и то же значение функции друг друга. Инвариант графа или параметр графа может быть аналогичным образом формализован как функция от графов к более широкому классу значений, таким как целые числа, действительные числа , последовательности чисел или полиномы , которые снова имеют одно и то же значение для любых двух изоморфных графов. [2]
Свойство графа является монотонным , если каждый подграф графа со свойством P также обладает свойством P. Например, быть двудольным графом или графом без треугольников является монотонным. Каждое монотонное свойство является наследственным, но не обязательно наоборот; например, подграфы хордальных графов не обязательно являются хордальными, поэтому быть хордальным графом не монотонно. [1]
Свойство графа является минорно-замкнутым, если каждый минор графа со свойством P также имеет свойство P . Например, планарный граф является минорно-замкнутым. Каждое минорно-замкнутое свойство монотонно, но не обязательно наоборот; например, миноры графов без треугольников не обязательно сами являются свободными от треугольников. [1]
Эти определения могут быть расширены от свойств до числовых инвариантов графов: инвариант графа является наследственным, монотонным или минорно-замкнутым, если функция, формализующая инвариант, образует монотонную функцию от соответствующего частичного порядка на графах до действительных чисел.
Кроме того, инварианты графов были изучены относительно их поведения по отношению к непересекающимся объединениям графов:
Инвариант графа является аддитивным , если для всех двух графов G и H значение инварианта непересекающегося объединения G и H является суммой значений на G и на H . Например, количество вершин аддитивно. [1]
Инвариант графа является мультипликативным , если для всех двух графов G и H значение инварианта дизъюнктного объединения G и H является произведением значений на G и на H . Например, индекс Хосоя (количество совпадений) является мультипликативным. [1]
Инвариант графа является максимальным , если для всех двух графов G и H значение инварианта в дизъюнктном объединении G и H является максимальным из значений на G и на H . Например, хроматическое число максимально. [1]
Кроме того, свойства графа можно классифицировать по типу описываемого ими графа: является ли граф неориентированным или ориентированным , применимо ли свойство к мультиграфам и т. д. [1]
Значения инвариантов
Целевой набор функции, определяющей инвариант графа, может быть одним из:
Истинное значение, истинное или ложное, для индикаторной функции свойства графика.
Целое число, например количество вершин или хроматическое число графа.
Легко вычислимые инварианты графа способствуют быстрому распознаванию изоморфизма графа или, скорее, неизоморфизма, поскольку для любого инварианта два графа с разными значениями не могут (по определению) быть изоморфными. Однако два графа с одинаковыми инвариантами могут быть изоморфными, а могут и не быть.
Инвариант графа I ( G ) называется полным , если из идентичности инвариантов I ( G ) и I ( H ) следует изоморфизм графов G и H. Нахождение эффективно вычислимого такого инварианта (проблема канонизации графа ) означало бы простое решение сложной проблемы изоморфизма графа . Однако даже инварианты с полиномиальными значениями, такие как хроматический полином, обычно не являются полными. Например, граф когтей и граф путей на 4 вершинах имеют один и тот же хроматический полином .
^ abcdefghi Ловас, Ласло (2012), «4.1 Параметры графа и свойства графа», Большие сети и пределы графа , Публикации коллоквиума, том. 60, Американское математическое общество, стр. 41–42, ISBN.978-1-4704-1583-9.
