블록 그래프

Block graph
블록 다이어그램 또는 막대 차트와 혼동하지 마십시오.
블록 그래프

그래프 이론에서, 조합 수학의 한 분야인 블록 그래프 또는 집단[1] 트리는 모든 쌍커넥티드 구성요소(블록)가 집단인 무방향 그래프의 한 종류이다.

블록 그래프는 (Kodi [2]Husimi의 이름을 따서) 후시미 나무라고 잘못 부르기도 하지만, 그 이름은 선인장 그래프,[3] 즉 모든 불요불급한 쌍접합 성분이 순환인 그래프를 더 적절하게 지칭한다.

블록 그래프는 임의의 무방향 [4]그래프 블록의 교차 그래프로 특징지을 수 있다.

특성화

블록 그래프는 정확히 4개의 꼭지점 u, v, x 및 y에 대해 3개의 거리 d(u, v) + d(x,y), d(u,x) + d(v,y) + d(u,y) + d(v,x) 중 가장 큰 2개가 [2][5]항상 동일한 그래프입니다.

또한 다이아몬드 그래프 또는 유도 하위 그래프로서 4개 이상의 정점의 사이클이 없는 그래프로서 금지된 그래프 특성화가 있습니다. 즉, 다이아몬드 프리 화음 [5]그래프입니다.그것들은 또한 서로 거리 2에 있는 모든 두 개의 노드가 고유한 최단 [2]경로로 연결되는 프톨레마이오스 그래프(차수-차수 그래프)와 두 개의 최대 클리어가 최대 하나의 정점을 [2]공통으로 갖는 화음 그래프이다.

그래프 G는 G의 정점의 연결된 두 부분 집합의 교차가 비어 있거나 연결되어 있는 경우에만 블록 그래프입니다.따라서 연결된 블록 그래프에서 꼭지점의 연결된 부분 집합은 블록 [6]그래프가 아닌 그래프에는 적용되지 않는 특성인 볼록 형상을 형성합니다.이 특성 때문에 연결된 블록 그래프에서 모든 정점 집합에는 볼록 형상에서의 닫힘인 고유한 최소 연결된 수퍼셋이 있습니다.연결된 블록 그래프는 각 [1]정점의 쌍을 연결하는 고유한 유도 경로가 있는 그래프입니다.

관련 그래프 클래스

블록 그래프는 화음, 거리 상속 및 측지학입니다.거리 종속 그래프는 동일한 두 정점 사이의 모든 유도 경로가 동일한 길이를 가지며, 블록 그래프의 특성이 두 정점마다 최대 하나의 유도 경로를 갖는 그래프이다.화음 그래프와 거리 종속 그래프는 모두 완벽한 그래프의 하위 클래스이기 때문에 블록 그래프가 완벽합니다.

모든 트리, 군집 그래프 또는 풍차 그래프는 블럭 그래프입니다.

모든 블록 그래프는 최대 [7]2개의 상자 크기를 가집니다.

블록 그래프는 의사 중위수 그래프의 예입니다.정점 3개마다 3개의 정점 사이의 최단 경로에 속하는 고유한 정점이 존재하거나 모서리가 이들 3개의 [7]최단 경로에 있는 고유한 삼각형이 있습니다.

트리의 선 그래프는 모든 절단 정점이 최대 2개의 블록에 입사하는 블록 그래프 또는 이에 상응하는 발톱이 없는 블록 그래프입니다.트리의 선 그래프는 트리의 가장 큰 유도 하위 그래프가 가능한 [8]한 작은 특정 수의 모서리와 정점을 가진 그래프를 찾는 데 사용되었다.

블록마다 크기가 최대 3개인 블록 그래프는 삼각형 모양의 선인장 그래프인 특수한 선인장 그래프입니다.모든 그래프에서 가장 큰 삼각형 선인장은 매트로이드 패리티 문제에 대한 알고리즘을 사용하여 다항식 시간에 찾을 수 있습니다.삼각형 선인장 그래프는 평면 그래프이므로, 가장 큰 삼각형 선인장은 평면화의 중요한 하위 문제인 가장 큰 평면 부분 그래프에 대한 근사치로 사용될 수 있다.근사 알고리즘으로서 이 방법은 최대 평면 서브그래프 [9]문제로 가장 잘 알려진 근사비 4/9를 가진다.

무방향 그래프의 블록 그래프

G가 임의의 무방향 그래프일 경우, B(G)로 표기되는 G의 블록 그래프는 G의 블록의 교차 그래프이다. B(G)는 G의 쌍접합 성분마다 정점을 가지며, 대응하는 두 개의 블록이 관절 정점에서 만나면 B(G)의 두 정점이 인접한다.K가 하나의 꼭지점을 가진 그래프를 나타낸다면1, B1(K)는 빈 그래프라고 정의된다.B(G)는 반드시 블록 그래프이다.이것은 G의 각 꼭지점에 대해 하나의 쌍접합 구성요소를 가지며, 이렇게 형성된 각 쌍접합 구성요소는 파벌이어야 한다.반대로, 모든 블록 그래프는 일부 그래프 [4]G에 대한 그래프 B(G)이다. 만약 G가 나무라면, B(G)는 G의 선 그래프와 일치한다.

그래프 B(B(G)는 G의 각 관절 정점에 대해 하나의 정점을 가지며,[4] G의 동일한 블록에 속하는 경우 두 정점은 B(B(G)에 인접합니다.

레퍼런스

  1. ^ a b 를 클릭합니다Vušković, Kristina (2010), "Even-hole-free graphs: A survey" (PDF), Applicable Analysis and Discrete Mathematics, 4 (2): 219–240, doi:10.2298/AADM100812027V.
  2. ^ a b c d 를 클릭합니다Howorka, Edward (1979), "On metric properties of certain clique graphs", Journal of Combinatorial Theory, Series B, 27 (1): 67–74, doi:10.1016/0095-8956(79)90069-8.
  3. ^ 예를 들어 Robert E. Jamison이 1983년에 블록 그래프를 Husimi tree라고 언급한 다른 논문의 리뷰인 MR0659742를 참조한다. Jamison은 이 실수를 Mehdi Behzad와 Gary Chartrand의 책에 있는 오류에 기인한다.
  4. ^ a b c 를 클릭합니다Harary, Frank (1963), "A characterization of block-graphs", Canadian Mathematical Bulletin, 6 (1): 1–6, doi:10.4153/cmb-1963-001-x, hdl:10338.dmlcz/101399.
  5. ^ a b 를 클릭합니다Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2.
  6. ^ 를 클릭합니다Edelman, Paul H.; Jamison, Robert E. (1985), "The theory of convex geometries", Geometriae Dedicata, 19 (3): 247–270, doi:10.1007/BF00149365, S2CID 123491343.
  7. ^ a b 블록 그래프, 그래프 클래스 포함에 대한 정보 시스템.
  8. ^ 를 클릭합니다Erdős, Paul; Saks, Michael; Sós, Vera T. (1986), "Maximum induced trees in graphs" (PDF), Journal of Combinatorial Theory, Series B, 41 (1): 61–79, doi:10.1016/0095-8956(86)90028-6.
  9. ^ Călinescu, Gruia; Fernandes, Cristina G.; Finkler, Ulrich; Karloff, Howard (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms, 2, 27 (2): 269–302, doi:10.1006/jagm.1997.0920, S2CID 8329680