캐터필러 트리

Caterpillar tree
이 기사는 그래프 이론에 관한 것이다.관목은 '플루메리아 알바'를 참고하세요.
애벌레

그래프 이론에서, 캐터필러 또는 캐터필러 트리는 모든 정점이 중앙 경로의 거리 1 내에 있는 나무입니다.

애벌레는 Harary와 Schwenk에 의해 일련의 논문에서 처음 연구되었다.그 이름은 Arthur [1][2]Hobbs에 의해 제안되었다.Harary & Schwenk(1973)가 색채적으로 썼듯이, "애벌레는 끝부분의 고치가 [1]제거되면 길로 변하는 나무입니다."

동등한 특성화

다음 모든 특성은 캐터필러 트리에 대해 설명합니다.

  • 잎과 입사 모서리를 제거하면 경로 [2][3]그래프가 생성되는 트리입니다.
  • 2도 이상의 모든 정점을 포함하는 경로가 존재하는 나무입니다.
  • 이 나무들은 적어도 세 개의 정도의 모든 정점이 최대 두 개의 잎이 아닌 이웃을 가진 나무들입니다.
  • 이들은 스타1,3 그래프 K의 모든 모서리를 길이 [3]2의 경로로 대체하여 형성된 그래프를 하위 그래프로 포함하지 않는 나무입니다.
  • 각 [3][4]선에 끝점이 하나씩 있는 교차하지 않는 선 세그먼트로 표시되는 모서리를 사용하여 두 개의 평행선에 정점을 사용하여 그릴 수 있는 연결된 그래프입니다.
  • 그것들은 네모난 것이 해밀턴 그래프인 나무들이다.즉, 캐터필러에는 모든 정점의 순환 시퀀스가 존재하며, 그 시퀀스의 인접한 각 정점의 쌍은 서로 1개 또는 2개의 거리에 있으며, 캐터필러가 아닌 나무에는 그러한 시퀀스가 없습니다.이 타입의 사이클은 캐터필러를 2개의 평행선상에 그려 한 라인상의 정점 시퀀스와 다른 [3]라인상의 정점 시퀀스를 연결함으로써 얻을 수 있다.
  • 선 그래프가 해밀턴 경로를 포함하는 트리입니다. 이러한 경로는 트리의 두 선 그림에서 모서리 순서를 지정함으로써 얻을 수 있습니다.보다 일반적으로 해밀턴 경로를 포함하도록 임의 트리의 선 그래프에 추가해야 하는 에지 수(해밀턴 완료 크기)는 트리의 가장자리를 [5]분해할 수 있는 최소 에지 분리 애벌레 수와 같습니다.
  • 경로 폭 [6]1의 연결된 그래프입니다.
  • 연결된 삼각형이 없는 구간 [7]그래프입니다.
  • 이들 그래프는 인접행렬이 오른쪽 상단 모서리에서 시작하여 아래쪽 또는 [8]왼쪽으로 내려가는 길이 n-1의 경로를 형성하도록 기술할 수 있는 n-vertex 그래프입니다.

일반화

k-트리는 각각 k + 1 정점을 포함하는 정확히 n - k 최대 클리크를 가진 화음 그래프이다. k-트리 자체로는 (k + 1)-클리크가 아닌 k-트리에서는 각 최대 클리크가 그래프를 둘 이상의 구성요소로 분리하거나 단일 리프 정점, 즉 단일 최대 클리크에만 속하는 정점을 포함한다.k-path는 최대 2개의 리프를 가진 k-트리이며, k-caterpillar는 k-path와 k-leaves로 분할할 수 있는k-트리입니다.각각 k-path의 구분 k-clique에 인접해 있습니다.이 용어에서 1-캐터필러는 캐터필러 트리와 동일하며 k캐터필러는 경로 폭 k의 [6]에지 최대 그래프입니다.

바닷가재 그래프는 모든 정점이 중앙 [9]경로의 거리 2 내에 있는 나무입니다.

열거

캐터필러는 정확한 공식이 주어질 수 있는 드문 그래프 열거 문제 중 하나를 제공한다: n 3 3일 때, 라벨이 부착되지 않은 정점이 n개인 캐터필러의 수는 다음과 같다.

n = 1, 2, 3, ...의 경우, n-쌍둥이 애벌레의 수는 다음과 같습니다.

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ...(OEIS의 시퀀스 A005418).

계산의 복잡성

그래프에서 스패닝 캐터필러 검출은 NP 완료입니다.이와 관련된 최적화 문제로는 최소 스패닝 캐터필러 문제(MSCP)가 있습니다.여기서 그래프는 엣지에 이중 비용을 가지며 입력 그래프에 걸쳐 전체 비용이 가장 작은 캐터필러 트리를 찾는 것이 목표입니다.여기서 캐터필러 비용은 엣지 비용의 합계로 정의되며, 각 엣지는 리프 엣지 또는 내부 엣지로서의 역할에 따라 두 가지 비용 중 하나를 사용합니다.P = NP가 아닌 한 MSCP에는 f(n) 근사 알고리즘이 없습니다.여기서 f(n)는 그래프의 [10]꼭지점 수인 n의 다항식 시간 계산 가능 함수입니다.

경계 트리 폭 그래프에서 MSCP에 대한 최적의 솔루션을 찾는 매개 변수화된 알고리즘이 있습니다.따라서 스패닝 캐터필러 문제와 MSCP 모두 그래프가 외부 평면,[10] 직렬 병렬 또는 할린 그래프인 경우 선형 시간 알고리즘을 사용합니다.

적용들

캐터필러 나무는 벤제노이드 탄화수소 분자의 구조를 나타내기 위해 화학 그래프 이론에서 사용되어 왔다.이 표현에서 1은 분자구조에서 각 가장자리가 6탄소 고리에 대응하는 캐터필러를 형성하고, 대응하는 고리가 구조 내에서 단대단 접속된 일련의 고리에 속할 때마다 정점에 2개의 가장자리가 입사한다.El-Basil은 "현재 "화학 그래프 이론"이라고 불리는 것에 중요한 역할을 한 거의 모든 그래프가 애벌레 나무와 관련이 있을 수 있다는 것은 놀라운 일이다."라고 쓰고 있다.이런 맥락에서 애벌레 나무는 이 지역의 [2][11][12]이반 구트만의 작품에서 따온 벤제노이드 나무와 구트만 나무로도 알려져 있다.

레퍼런스

  1. ^ a b c 를 클릭합니다Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl:2027.42/33977.
  2. ^ a b c 를 클릭합니다El-Basil, Sherif (1987), "Applications of caterpillar trees in chemistry and physics", Journal of Mathematical Chemistry, 1 (2): 153–174, doi:10.1007/BF01205666.
  3. ^ a b c d 를 클릭합니다Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika, 18: 138–140, doi:10.1112/S0025579300008494, hdl:2027.42/153141.
  4. ^ 를 클릭합니다Harary, Frank; Schwenk, Allen J. (1972), "A new crossing number for bipartite graphs", Utilitas Math., 1: 203–209.
  5. ^ 를 클릭합니다Raychaudhuri, Arundhati (1995), "The total interval number of a tree and the Hamiltonian completion number of its line graph", Information Processing Letters, 56 (6): 299–306, doi:10.1016/0020-0190(95)00163-8.
  6. ^ a b 를 클릭합니다Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models" (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176.
  7. ^ 를 클릭합니다Eckhoff, Jürgen (1993), "Extremal interval graphs", Journal of Graph Theory, 17 (1): 117–127, doi:10.1002/jgt.3190170112.
  8. ^ E. Guseyov, 인접 행렬의 패턴 및 애벌레가 우아하다는 또 다른 증거 [1]
  9. ^ Weisstein, Eric W. "Lobster graph". MathWorld.
  10. ^ a b Khosravani, Masoud (2011). Searching for optimal caterpillars in general and bounded treewidth graphs (Ph.D.). University of Auckland.
  11. ^ 를 클릭합니다Gutman, Ivan (1977), "Topological properties of benzenoid systems", Theoretica Chimica Acta, 45 (4): 309–315, doi:10.1007/BF00554539.
  12. ^ 를 클릭합니다El-Basil, Sherif (1990), "Caterpillar (Gutman) trees in chemical graph theory", in Gutman, I.; Cyvin, S. J. (eds.), Advances in the Theory of Benzenoid Hydrocarbons, Topics in Current Chemistry, vol. 153, pp. 273–289, doi:10.1007/3-540-51505-4_28.

외부 링크