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

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

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

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

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

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

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

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

• Граф свойство Р является наследственным , если каждый индуцированный подграф графа со свойством Р также обладает свойством P . Например, быть идеальным графом или быть хордовым графом являются наследственными свойствами. ^[1]
• Свойство графа является монотонным , если каждый подграф графа со свойством Р также обладает свойством P . Например, быть двудольным графом или графом без треугольников монотонно. Каждое монотонное свойство наследственно, но не обязательно наоборот; например, подграфы хордовых графов не обязательно хордовые, поэтому хордовый граф не монотонен. ^[1]
• Свойство графа является незначительным замкнутым , если каждый график минор графа со свойством Р также обладает свойством P . Например, планарный граф является второстепенным замкнутым. Любое свойство min-closed монотонно, но не обязательно наоборот; например, миноры графов без треугольников не обязательно сами по себе не содержат треугольников. ^[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-выбираемым
• Число независимости , наибольший размер независимого набора вершин
• Кликовое число , наибольший порядок полного подграфа
• Древесность
• Род графа
• Номер страницы
• Индекс Хосоя
• Индекс Винера
• Граф инвариант Колена де Вердьера
• Токсичность

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

• Коэффициент кластеризации
• Центральность посредничества
• Дробное хроматическое число
• Алгебраическая связность
• Изопериметрический номер
• Индекс эстрады
• Сила

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

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

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

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

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