선형 수목성

수학의 한 분야인 그래프 이론에서, 비방향 그래프의 선형 수목성은 가장자리가 분할될 수 있는 선형 숲의 최소 수입니다.여기서 선형 포리스트는 최대 도 2를 갖는 순환 그래프, 즉 경로 그래프의 분리 결합이다.선형 수목성은 가장자리를 분할할 수 있는 최소 숲 수인 수목성의 변종이다.

The linear arboricity of any graph of maximum degree ${\displaystyle \Delta }$ is known to be at least ${\displaystyle \lceil \Delta /2\rceil }$ and is conjectured to be at most ${\displaystyle \lceil (\Delta +1)/2\rceil }$. This conjecture would determine the linear arboricity exactly for graphs그 경우처럼 두 표현 모두 동일하다.짝수 정도의 그래프의 경우 선형 수목성은 두 개의 가능한 값 중 하나여야 함을 의미하지만, 이 두 가지 선택 중에서 정확한 값을 결정하는 것은 NP-완전이다.

정도와의 관계

각 선형 포리스트는 최대 $[\displaystyle \Delta }$의 가장자리 중 두 개만 사용할 수 있으므로, $그래프{\displaystyle }$ G ${\$$displaystyle$$$G}의 선형 수목성은 항상$/$ 이상이다$.$아키야마, Exoo &amp의 선형 arboricity 추측, Harary(1981년)은 이 하한도 단단하다:그들의 추측에 따르면, 모든 그래프 대부분의 ⌈(Δ+1)/2⌉{\displaystyle \lceil(\Delta+1)/2\rceil}에서 .[1] 하지만, 이 증명되지 않은 그대로 남아 있으면 최고의 입증된 upper은 선형 arboricity 단번에. 선형 arboricity는 있다.seing더 큰${\displaystyle \mathrm{}\Delta \mathrm{}}$/ ${\displaystyle 2}$ + O${\displaystyle }$(${\displaystyle {\Delta \mathrm{}}^{}}$ 2 / 3${\displaystyle {}^{}}$- ${\displaystyle c^{}}$) ${\displaystyle \Delta /2+O$(\$Delta$ ^[2]$^{2/3-c}})$ Ferber, Fox 및 Jain으로 인해 c$$> 0 ${\displaysty c>0}.$

In order for the linear arboricity of a graph to equal ${\displaystyle \Delta /2}$, ${\displaystyle \Delta }$ must be even and each linear forest must have two edges incident to each vertex of degree ${\displaystyle \Delta }$. But at a vertex that is at the end of a path, the forest containing that path has only one incident edge. 따라서 해당 꼭지점의 정도가 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$과(와) 같을 수 없다$.$ 따라서 선형 수목성이${\displaystyle }\Delta {\displaystyle \mathrm{}}$ /$$2 {\$displaystyle \Delta /2}$인 그래프에는 최대값보다 ${\displaystyle 작은\mathrm{}}$ 정점이 있어야 한다.일반 그래프에서는 그러한 정점이 없으며 선형 수목성은 $\Delta {\displaystyle \mathrm{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \Delta /2}$과(와) 같을 수 없다$.$ 따라서, 일반 그래프의 경우, 선형 수목성 추측에 따르면, 선형 추측은 선형 수목성이 정확히${\displaystyle }$Δ${\displaystyle }$(${\displaystyle \mathrm{\Delta }}$ + ${\displaystyle 1}$)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rceil }$ ${\displaystyle \lceil (\Delta +1)/2\rceil }$임을 의미한다$.$

관련 문제

선형 수목성은 그래프의 가장자리를 분할할 수 있는 최소 포리스트 수인 수목성의 변화다.연구원들은 또한 선형 숲의 각 경로가 최대 k 엣지를 가질 수 있는 선형 수목성의 변종인 선형 k-arbority를 연구했다.^[3]

또 다른 관련 문제는 해밀턴 분해인데$,$ 해밀턴 주기에서는 짝수 $\Delta {\displaystyle \mathrm{}}$ {\$displaystyle \Delta }$의 정규 그래프를 정확히 $\Delta {\displaystyle \mathrm{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \Delta /2}$개의 해밀턴$$ 주기들로 분해하는 문제다.그래프에서 임의 정점을 제거하여 형성된 하위 그래프가 선형 ${\displaystyle 수목성\mathrm{}}$ $\Delta {\displaystyle \mathrm{}}$ / 2${\displaystyle \Delta$/2}을$($를$)$ 갖는 경우에만 주어진 그래프가 해밀턴 분해된다.

계산 복잡성

다항식 시간에 결정할 수 있는 수목성과 달리 선형 수목성은 NP-hard이다.선형 수목성 2의 그래프를 인식하는 것조차 NP-완전하다.^[4]그러나 입방형 그래프와 최대도 3의 다른 그래프의 경우 선형 수목성은 항상 2이며,^[1] 깊이 우선 검색에 기초한 알고리즘을 사용하여 선형 숲 2개로 분해되는 것을 선형 시간 내에 발견할 수 있다.^[5]

참조