Свойство графа

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

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

Определения [ править ]

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

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

Свойства недвижимости [ править ]

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

Свойство графа P является наследственным если каждый индуцированный подграф графа со свойством P также обладает свойством P. , Например, быть идеальным графом или хордальным графом — это наследственные свойства. ^[1]
Свойство графа является монотонным если каждый подграф графа со свойством 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 вершинах имеют один и тот

Примеры [ править ]

Свойства [ править ]

Целочисленные инварианты [ править ]

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

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

Последовательности и полиномы [ править ]

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

См. также [ править ]

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

Ссылки [ править ]

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

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

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

[1]

[2]