투그래프

Two-graph

수학에서 2-그래프는 유한 꼭지점 집합 X에서 선택한 (순서가 없는) 삼쌍의 집합으로, X에서 매 (순서가 없는) 4배는 2-그래프의 짝수 수의 삼쌍을 포함하고 있다.일반 2-그래프는 모든 꼭지점 쌍이 2-그래프의 3배수에 있는 속성을 가지고 있다.2-그래프는 등각선과의 연관성 때문에 연구되어 왔고, 일반 2-그래프의 경우, 강력하고 정규적인 그래프와 유한한 그룹도 많은 일반 2-그래프가 흥미로운 자동화 그룹을 가지고 있기 때문이다.

2-그래프는 그래프가 아니며 2-정규그래프와 같이 그래프 이론에서 2-그래프라고불리는 다른 개체와 혼동해서는안 된다.

예

정점 집합 {1,...,6}에서 순서가 지정되지 않은 다음과 같은 세 쌍의 집합은 두 개의 그래프로 되어 있다.

123 124 135 146 156 236 245 256 345 346

이 두 개의 그래프는 각각의 뚜렷한 꼭지점 쌍이 정확히 두 개의 세 쌍으로 함께 나타나기 때문에 일반적인 두 개의 그래프로 되어 있다.

단순 그래프 G = (V,E)를 사용하면 유도 서브그래프의 가장자리 수가 홀수인 정점 집합 V의 3배 세트가 세트 V에 2-그래프를 형성한다.모든 두 개의 그래프는 이런 식으로 표현될 수 있다.[1]이 예를 단순 그래프에서 2-그래프의 표준구축이라고 한다.

좀 더 복잡한 예로서 T를 가장자리 집합 E가 있는 트리가 되게 한다.T의 경로에 포함되지 않는 E의 모든 세 쌍의 집합은 세트 E에 2개의 그래프를 형성한다.[2]

전환 및 그래프

그래프에서 {X,Y} 전환

2-그래프는 그래프의 스위칭 클래스와 서명된 전체 그래프의 (서명된) 스위칭 클래스에 해당한다.

(단순) 그래프에서 정점 집합을 바꾸는 것은 정점 쌍의 각 정점 쌍의 보조성을 역방향으로 바꾸는 것을 의미한다. 따라서 가장자리 집합은 인접한 쌍이 아닌 쌍이 되고 인접하지 않은 쌍이 인접하도록 변경된다.끝점이 집합에 있거나 둘 다 집합에 없는 가장자리는 변경되지 않는다.그래프는 다른 그래프에서 다른 그래프를 전환하여 얻을 수 있다면 등가 전환이다.전환 중인 그래프의 동등성 클래스를 스위칭 클래스라고 한다.스위칭은 반 린트 앤 세이델(1966)에 의해 도입되었고 세이델에 의해 개발되었다. 그것은 부분적으로 사인 그래프의 스위칭과 구별하기 위해 그래프 스위칭 또는 세이델 스위칭이라고 불려왔다.

위에서 주어진 간단한 그래프에서 두 개의 그래프를 표준으로 구성했을 때, 두 개의 그래프는 만약 그들이 전환 중에 동일하다면, 그리고 동일한 전환 등급에 있는 경우에만 동일한 두 개의 그래프를 산출할 것이다.

Ⅱ를 세트X에 투그래프로 하자.X의 원소 X에 대해, 정점 집합 X에 대해, 정점 집합 Y와 z가 인접한 경우 및 정점 집합 X의 그래프 graph을x 정의하십시오.이 그래프에서 x는 절연 정점이 된다.이 구조는 되돌릴 수 있다; 간단한 그래프 G를 주어진다면, 새로운 요소 x를 G의 꼭지점 집합에 결합하고, 동일한 가장자리 집합을 유지하며, 위의 표준 구조를 적용한다.[3]

그래프 G에는 동일한 정점 집합에 서명된 전체 그래프 σ이 있으며, 이 그래프 σ은 G이면 음수, G이면 양수, 반대로 G는 모든 정점과 음수 에지로 구성된 σ의 하위 그래프다.G의 2-그래프는 σ에서 음의 삼각형(음의 가장자리 수가 홀수인 삼각형)을 지지하는 정점의 3쌍의 집합으로도 정의할 수 있다.서명된 두 개의 전체 그래프는 전환 중에 동일할 경우에만 동일한 2-그래프를 생성한다.

G와 σ의 스위칭은 관련이 있다: 양쪽 모두에서 동일한 정점을 전환하면 그래프 H와 그에 상응하는 서명된 전체 그래프가 나온다.

인접 행렬

2-그래프의 인접 행렬은 해당 서명된 전체 그래프의 인접 행렬이므로 대칭이고 대각선 상에 0이며 대각선 바깥에 ±1의 항목이 있다.G가 서명된 전체 그래프 σ에 해당하는 그래프인 경우, 이 행렬을 (0, -1, 1) 인접 행렬 또는 G의 인접 행렬이라고 한다.Seel 매트릭스는 주 대각선 상에 0개의 항목, 인접 정점의 경우 -1개 항목, 비인접 정점의 경우 +1개의 항목을 가진다.

그래프 G와 H가 동일한 스위칭 클래스에 있으면 행렬이 유사하기 때문에 G와 H의 두 Seidel 인접 행렬의 고유값 다중값이 일치한다.[4]

세트 V에 대한 2-그래프는 인접 행렬이 2개의 고유값 > > 0 > ρ12 say 단 두 개의 고유값만 가지고 있는 경우에만 일반적이다. 여기서 ρρ12 = 1 - V.[5]

등각선

주요기사: 등각선

모든 2-그래프는 각 쌍이 동일한 각도에서 만나는 어떤 차원 유클리드 공간의 선 집합과 동일하다.n 정점의 두 그래프에서 생성된 선 세트는 다음과 같이 구한다.-1987은 Seidel 인접 행렬의 최소 고유값인 2-그래프의 A가 되도록 하고, 다중성 n - d가 있다고 가정한다.그 다음 행렬 ρI + A는 d등급의 양의 반확정성이므로 유클리드 d-공간에 있는 n 벡터의 내생물의 Gram 행렬로 나타낼 수 있다.이 벡터들은 동일한 규범(이름, , ρ, 과 상호 내부 제품 ±1을 가지므로, 이들 벡터에 의해 확장된 n개의 라인 중 어떤 쌍도 cos 1 = 1/161인 동일한 각도 φ에서 만난다.반대로 유클리드 공간에 있는 비직교 등각선 세트는 2-그래프를 발생시킬 수 있다(구성은 등각선 참조).[6]

위와 같은 표기법으로 최대 카디널리티 n은 n n d(( - 1)/(ρ22 - d)를 만족하며, 2-그래프가 정규적인 경우에만 바운드가 달성된다.

메모들

  1. ^ Colburn & Dinitz 2007, 페이지 876, Remark 13.2
  2. ^ Cameron, P.J. (1994), "Two-graphs and trees", Discrete Mathematics, 127: 63–74 Colburn & Dinitz 2007, 페이지 876, 건설 13.12 목표 (
  3. ^ 카메론 & 반 린트 1991, 페이지 58-59
  4. ^ 카메론 & 반 린트 1991, 페이지 61
  5. ^ Colburn & Dinitz 2007, 페이지 878 #13.24
  6. ^ 판 린트&세이델 1966년

참조

  • 브루워(Brower), 에이에이(A.E), 코헨(Cohen), 노이마이어(Neumaer)(1989), 거리-정규 그래프(Distance-Regular Graphs) 등이 그것이다.베를린 스프링거-베를라크.섹션 1.5, 3.8, 7.6C.
  • Cameron, P.J.; van Lint, J.H. (1991), Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, ISBN 978-0-521-42385-4
  • Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, pp. 875–882, ISBN 1-58488-506-8
  • 크리스 고딜과 고든 로일(2001), 대수 그래프 이론.수학 대학원 교과서, 제207권, 뉴욕 스프링거-베를라크.제11장.
  • 세이델, J. J. (1976년), 2개의 그래프에 대한 조사.In: Colorquio Internazionale sulle Teori Combinatorie(진행, 로마, 1973), Vol.나, 페이지 481-511.17번 아티 데이 볼록니 린시로마 나치오날레 데이 린시 아카다비아.
  • 테일러, D. E. (1977), 일반 2-그래프.런던수학협회의 절차(3), 35권, 257-274.
  • van Lint, J. H.; Seidel, J. J. (1966), "Equilateral point sets in elliptic geometry", Indagationes Mathematicae, Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28: 335–348