В теории графов подграфом Сакса данного графа называется подграф , в котором все компоненты связности являются либо отдельными ребрами, либо циклами . Эти подграфы названы в честь Хорста Сакса , который использовал их в расширении характеристического многочлена матрицы смежности графов. [1] Аналогичное расширение с использованием подграфов Сакса возможно и для перманентных полиномов графов. [2] Подграфы Сакса и вычисляемые с их помощью многочлены нашли применение в химической теории графов , [3]например, как часть теста на существование несвязывающих орбиталей в углеводородных структурах. [4]
Остовный подграф Сакса , также называемый {1,2}-фактором, представляет собой подграф Сакса, в котором каждая вершина данного графа инцидентна ребру подграфа. [5] Объединение двух совершенных паросочетаний всегда является двудольным, охватывающим подграф Сакса, но в целом подграфы Сакса не ограничиваются двудольностью. Некоторые авторы используют термин «подграф Сакса» для обозначения только охватывающих подграфов Сакса. [6]