Сплиттанс

В теории графов , разделе математики, расщепление неориентированного графа измеряет его расстояние от разделенного графа . Разбитый граф — это граф, вершины которого можно разделить на независимое множество (без ребер внутри этого подмножества) и клику (имеющую все возможные ребра внутри этого подмножества). Сплиттанс — это наименьшее количество добавлений и удалений ребер, которые преобразуют данный граф в расщепленный граф. ^{[ 1 ]}

Расчет из последовательности градусов

Расщепление графа можно вычислить только на основе последовательности степеней графа, без изучения подробной структуры графа. Пусть $G$ — любой граф с $n$ вершинами, степени которого в порядке убывания равны $d 1 \geq d 2 \geq d 3 \geq \dots \geq d n$ . Пусть $m$ будет наибольшим индексом, для которого $d i \geq i - 1$ . Тогда расщепление $G$ равно

\sigma (G)={\tbinom {m}{2}}-{\frac {1}{2}}\sum _{i=1}^{m}d_{i}+{\frac {1}{2}}\sum _{i=m+1}^{n}d_{i}.

Данный граф уже является расщепленным графом, если $σ (G) = 0$ . В противном случае его можно превратить в разделенный граф, вычислив $m$ , добавив все недостающие ребра между парами $m$ вершин максимальной степени и удалив все ребра между парами оставшихся вершин. Как следствие, расщепление и последовательность добавлений и удалений ребер, которые его реализуют, могут быть вычислены за линейное время . ^{[ 1 ]}

Приложения

Расщепление графа использовалось в параметризованной сложности как параметр для описания эффективности алгоритмов. Например, при этом параметре раскраска графов регулируется с фиксированным параметром: можно оптимально раскрасить графики ограниченного расщепления за линейное время . ^{[ 2 ]}

Ссылки

^ Jump up to: ^а ^б Хаммер, Питер Л .; Симеоне, Бруно (1981), «Расщепление графа», Combinatorica , 1 (3): 275–284, doi : 10.1007/BF02579333 , MR 0637832 , S2CID 30335319
^ Цай, Лейжен (2003), «Параметризованная сложность раскраски вершин», Discrete Applied Mathematics , 127 (3): 415–429, CiteSeerX 10.1.1.104.3789 , doi : 10.1016/S0166-218X(02)00242-1 , MR 1976024

[hamsim-1] Jump up to: ^а ^б Хаммер, Питер Л .; Симеоне, Бруно (1981), «Расщепление графа», Combinatorica , 1 (3): 275–284, doi : 10.1007/BF02579333 , MR 0637832 , S2CID 30335319

[cai-2] Цай, Лейжен (2003), «Параметризованная сложность раскраски вершин», Discrete Applied Mathematics , 127 (3): 415–429, CiteSeerX 10.1.1.104.3789 , doi : 10.1016/S0166-218X(02)00242-1 , MR 1976024

[ 1 ]

[ 2 ]