В теории графов свойство графа или инвариант графа — это свойство графа , которое зависит только от абстрактной структуры, а не от представлений графа, таких как конкретные маркировки или рисунки графа. [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 Lovász, László (2012), "4.1 Параметры и свойства графа", Большие сети и пределы графа , Colloquium Publications, т. 60, Американское математическое общество, стр. 41–42, ISBN 978-1-4704-1583-9.
^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «3.10 Параметры графа», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Springer, стр. 54–56, doi :10.1007/978-3-642-27875-4, ISBN978-3-642-27874-7, МР 2920058.
