심플렉스 그래프

Simplex graph
그래프 G 및 해당 심플렉스 그래프 κ(G)κ(G)의 블루 컬러 노드는 G(빈 세트)의 제로 베텍스 클릭에 해당하고, 자홍색 노드는 3베렉스 클릭에 해당한다.

수학의 한 분야인 그래프 이론에서, 비방향 그래프 G의 심플렉스 그래프 κ(G)은 그 자체로 G에서 각 클라이크(상호 인접 정점 집합)에 대해 하나의 노드를 가진다.κ(G)의 두 노드는 하나의 꼭지점의 유무에 따라 해당하는 두 개의 부류가 다를 때마다 에지로 연결된다.

빈 집합은 하나의 꼭지점과 인접한 두 꼭지점의 모든 집합이 그렇듯이 클라이크 그래프를 형성하는 데 사용되는 G의 집합 중 하나로 포함된다.따라서 심플렉스 그래프는 그 안에 G 자체의 하위분할을 포함하고 있다.전체 그래프의 심플렉스 그래프는 하이퍼큐브 그래프, 길이 4 이상 사이클 그래프의 심플렉스 그래프는 기어 그래프다.경로 그래프의 보완 그래프의 심플렉스 그래프는 피보나치 큐브다.

G의 전체 서브그래프는 중위수 대수 구조를 부여할 수 있다: 3개 부류 A, B, C의 중위수는 3개 부류 중 다수에 속하는 정점에 의해 형성된다.[1]이 중위수 집합에 속하는 정점 2개는 모두 A, B 또는 C 중 적어도 하나에 속해야 하며, 따라서 가장자리로 연결되어야 하므로 세 개의 군집의 중위수는 그 자체가 하나의 집단이다.심플렉스 그래프는 이 중위수 대수 구조에 해당하는 중위수 그래프다.G가 초당적 그래프의 보완 그래프일 때 G의 집단은 분배 격자로 더 강한 구조를 부여할 수 있으며,[2] 이 경우 심플렉스 그래프는 격자의 그래프다.중위수 그래프의 경우 일반적으로 그렇듯이, 모든 심플렉스 그래프는 그 자체로 양분적이다.

심플렉스 그래프는 G의 클라이크 콤플렉스 X(G)에 있는 심플렉스마다 하나의 꼭지점이 있으며, 이에 대응하는 두 개의 심플렉스 중 하나가 다른 하나의 면일 때 두 개의 꼭지점이 에지로 연결되어 있다.따라서 객체(simplex graph, X(G)의 simplex와 객체 간의 관계(simplex graph, X(G)의 simplex 간의 포함 관계)는 X(G)와 ((G)의 일대일 대응 관계에 있다.

-일대다 그래프 Bandelt 및에 의해;반 드 Vel(1989년)[3]는 만일 내부 그래프triangle-free은 단신 그래프가 없은 얼음 가지고 있으며, 내부 그래프의 색 수 n는 심플렉스 그래프 같은 크기로. ntr의 데카르트 곱에 내장될 수 있는 최소 숫자와 동일하다는 것을 보여 주는 것을 관찰했다 소개되었다.ees.색수가 높은 삼각형이 없는 그래프가 존재한 결과, 2차원 위상학적 중위 알헤브라가 존재하며, 이는 미세하게 많은 실제 나무의 산물에 내장될 수 없다는 것을 보여주었다.Imrich, Klavzar & Mulder(1999) 또한 그래프가 삼각형이 없는지 또는 중위수 그래프인지를 테스트하는 것이 똑같이 빠르게 수행될 수 있다는 증거의 일부로 심플렉스 그래프를 사용한다.

메모들

  1. ^ Barthelmy, Leclerc & Monjardet(1986) 200페이지.
  2. ^ 프롭(1997년).
  3. ^ Imrich, Klavzar & Mulder(1999)는 Bandelt와 Van de Vel에 의해서도 심플렉스 그래프의 도입을 후기 논문으로 인정하지만, 이것은 착오로 보인다.

참조

  • Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J.E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemp. Math., vol. 453, Providence, RI: AMS, pp. 49–86.
  • Bandelt, H.-J.; van de Vel, M. (1989), "Embedding topological median algebras in products of dendrons", Proceedings of the London Mathematical Society, s3-58 (3): 439–453, doi:10.1112/plms/s3-58.3.439, archived from the original on 2013-04-15.
  • Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188.
  • Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", SIAM Journal on Discrete Mathematics, 12 (1): 111–118, CiteSeerX 10.1.1.28.5906, doi:10.1137/S0895480197323494, MR 1666073.
  • Propp, James (1997), "Generating random elements of finite distributive lattices", Electronic Journal of Combinatorics, 4 (2): R15, arXiv:math.CO/9801066.