결합 구조

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 균등 결합 구조와 정칙 결합 구조
- 2.2. 선형 공간과 준선형 공간
3. 연산
4. 예
5. 역사
참조

1. 개요

결합 구조는 점과 선으로 구성되며, 점과 선 사이의 관계(결합)를 통해 정의되는 수학적 구조이다. 부분 결합 구조, 균등 및 정칙 결합 구조, 선형 공간 및 준선형 공간 등의 개념이 존재하며, 연산과 쌍대 구조를 가질 수 있다. 결합 행렬과 레비 그래프를 통해 시각화 및 분석이 가능하며, 그래프, 다각형, 블록 디자인, 사영 평면, 리만 다양체, 일반화 다각형 등 다양한 수학적 대상과 연결된다. 레비 그래프는 프리드리히 빌헬름 다니엘 레비의 이름을 따서 명명되었으며, 기하학, 그래프 이론, 설계 이론 등 다양한 분야에서 연구된다.

2. 정의

'''결합 구조''' $(X,L,\vartriangleleft)$ 는 다음과 같은 데이터로 주어진다.

집합 $X$ . 그 원소를 '''점'''(點, point^eng)이라고 한다.
집합 $L$ . 그 원소를 '''직선'''(直線, line^eng)이라고 한다.
부분 집합 관계 $\vartriangleleft\subseteq X\times L$ . 만약 $(x,l)\in \vartriangleleft$ 라면 이를 $x\vartriangleleft l$ 또는 $l\vartriangleright x$ 로 표기하고, $x$ 가 $l$ 과 '''결합한다'''(結合-, incident^eng)고 한다. 이 이항 관계는 $x\,\mathsf I\,l$ 또는 $x\in l$ 등으로 표기되기도 한다.

결합 구조

(X,L,\vartriangleleft)

에서, 부분 집합

X'\subseteq X

와

L'\subseteq L

이 주어졌을 때,

(X',L',\vartriangleleft\restriction X'\times L')

를

(X,L,\vartriangleleft)

의 '''부분 결합 구조'''(部分結合構造, incidence substructure^eng)라고 한다.

'''결합 구조'''는

(P, L, I)

삼중항으로 정의되기도 하는데, 여기서

P

는 '점'이라 불리는 원소들의 집합이고,

L

은 '선'이라 불리는 원소들의 구별되는 집합이며,

I \subseteq P \times L

는 결합 관계이다.

I

의 원소

(p, l)

은 '''플래그'''라고 한다. 만약

(p, l)

이

I

에 속한다면, 점

p

가 선

l

"위에 놓여 있다"거나, 선

l

이 점

p

를 "통과한다"고 말할 수 있다. 이 관계의 대칭적 특성을 반영하여 더 대칭적인 용어로는 "

p

는

l

과 결합한다" 또는 "

l

은

p

와 결합한다"고 하며,

p I l

표기를

(p, l) \in I

와 동의어로 사용한다.^[2]

일부 일반적인 상황에서

L

은

P

의 부분 집합의 집합일 수 있으며, 이 경우 결합

I

는 포함 관계(

p I l

는

p

가

l

의 원소인 경우에만 해당)가 된다. 이러한 유형의 결합 구조를 '''집합론적'''(set-theoretic^eng)이라고 한다.^[3] 그러나 항상 그런 것은 아닌데, 예를 들어

P

가 벡터의 집합이고

L

이 정사각 행렬의 집합인 경우, 결합 관계

I

를 다음과 같이 정의할 수 있다.

I = \{(v, M) : \vec v \text{는 행렬 } M \text{의 고유 벡터이다} \}.

이 예시는 점과 선이라는 기하학적 용어가 사용되더라도, 대상 객체가 반드시 이러한 기하학적 객체일 필요는 없다는 것을 보여준다.

2. 1. 균등 결합 구조와 정칙 결합 구조

결합 구조

(X,L,\vartriangleleft)

가 다음 조건을 만족시키면 '''균등 결합 구조'''(均等結合構造, uniform incidence structure^영어)라고 한다.

임의의 두 점 $x,y\in X$ 에 대하여, $|\{l\in L\colon x\vartriangleleft l\}| = |\{l\in L\colon y\vartriangleleft l\}|$ 이다. 이는 모든 점에 대해, 그 점을 지나는 직선의 개수가 같다는 의미이다.

결합 구조

(X,L,\vartriangleleft)

가 다음 조건을 만족시키면 '''정칙 결합 구조'''(正則結合構造, regular incidence structure^영어)라고 한다.

임의의 두 직선 $l,m\in L$ 에 대하여, $|\{x\in X\colon x\vartriangleleft l\}| = |\{x\in X\colon x\vartriangleleft m\}|$ 이다. 이는 모든 직선에 대해, 그 직선 위의 점의 개수가 같다는 의미이다.

이 두 개념은 서로 쌍대 관계에 있다. 즉, 균등 결합 구조의 쌍대 결합 구조는 정칙 결합 구조이며, 반대로 정칙 결합 구조의 쌍대 결합 구조는 균등 결합 구조이다.

2. 2. 선형 공간과 준선형 공간

결합 구조

(X,L,\vartriangleleft)

가 다음 두 조건을 만족하면 '''준선형 공간'''(準線形空間, partial linear space^영어)이라고 한다.

(A) 임의의 서로 다른 두 점 $x,y\in X$ 에 대하여, $x\vartriangleleft l\vartriangleright y$ 인 직선 $l\in L$ 이 적어도 하나 이상 존재한다. 즉, 어떤 서로 다른 두 점을 잡아도 그 두 점을 지나는 직선이 최소한 하나는 있다.
(B) 임의의 직선 $l\in L$ 에 대하여, $x\vartriangleleft l\vartriangleright y$ 인 서로 다른 두 점 $x,y\in X$ 이 항상 존재한다. 즉, 모든 직선은 최소한 두 개의 점을 포함한다.

준선형 공간 중에서 특히 다음 조건을 만족하는 경우를 '''선형 공간'''(線形空間, linear space^영어)이라고 부른다.

(A′) 임의의 서로 다른 두 점 $x,y\in X$ 에 대하여, $x\vartriangleleft l\vartriangleright y$ 인 직선 $l\in L$ 이 유일하게 존재한다. 즉, 어떤 서로 다른 두 점을 잡아도 그 두 점을 지나는 직선이 정확히 하나만 있다.

사건 구조의 관점에서 보면, 부분 선형 공간은 다음 두 공리를 만족하는 사건 구조이다.

# 서로 다른 두 점은 최대 하나의 공통 선에 속한다.

# 모든 선은 최소 두 개의 점을 포함한다.

만약 첫 번째 공리를 더 강한 조건으로 바꾸어,

#

서로 다른 두 점은 정확히 하나의 공통 선에 속한다.

를 만족하면, 이 사건 구조는 선형 공간이라고 불린다.^[4]^[5]

3. 연산

결합 구조를 다루는 데에는 여러 유용한 연산들이 있다. 대표적인 연산으로는 쌍대 연산이 있는데, 이는 주어진 결합 구조에서 점과 선의 역할을 서로 바꾸어 새로운 결합 구조, 즉 쌍대 결합 구조를 만드는 과정이다.^[2] 어떤 결합 구조가 자신의 쌍대 구조와 동형일 경우, 이를 자기 쌍대 결합 구조라고 부른다. 파노 평면은 자기 쌍대 구조의 대표적인 예시이다.

또한, 유한 결합 구조의 경우, 점과 선 사이의 결합 관계를 결합 행렬이라는 0과 1로 이루어진 행렬로 표현할 수 있다. 이 행렬은 결합 구조의 대수적인 분석에 활용된다.

결합 구조를 시각적으로 이해하고 그래프 이론적 성질을 분석하기 위해 레비 그래프를 사용하기도 한다. 레비 그래프는 결합 구조의 점과 선을 각각 다른 색의 꼭짓점으로 표현하고, 점과 선이 결합 관계에 있을 때 두 꼭짓점을 변으로 연결하는 이분 그래프이다.

이러한 연산들은 결합 구조의 내부적인 대칭성이나 다른 구조와의 관계를 파악하는 데 중요한 도구로 사용된다.

3. 1. 쌍대 결합 구조

결합 구조

C = (P, L, I)

(여기서 P는 점의 집합, L은 선의 집합, I는 결합 관계)가 주어졌을 때, "점"과 "선"의 역할을 서로 바꾸면 쌍대 구조

C^* = (L, P, I^*)

를 얻을 수 있다. 여기서

I^*

는

I

의 역관계이다. 정의에 따라

C^{**} = C

가 성립하는데, 이는 두 번 쌍대 연산을 하면 원래의 구조로 돌아온다는 의미이다. 또한, 이는 사영 쌍대성의 추상적인 형태이기도 하다.^[2]

만약 어떤 결합 구조

C

가 그 쌍대 구조

C^*

와 동형이라면, 그 구조

C

를 자기 쌍대 구조라고 부른다. 예를 들어, 파노 평면은 자기 쌍대적인 결합 구조이다.

3. 2. 결합 행렬

결합 구조

(X,L,\vartriangleleft)

가 주어지고,

X

(점의 집합)와

L

(선의 집합)이 모두 유한 집합이라고 가정하자.

X

와

L

위에 각각 임의의 전순서를 부여하여 다음과 같이 나타낼 수 있다.

:

X=\{x_1,x_2,\dotsc,x_m\}

:

L=\{l_1,l_2,\dotsc,l_n\}

이때, 다음과 같은

m \times n

행렬

M

을 정의할 수 있으며, 이를 결합 구조

(X,L,\vartriangleleft)

의 '''결합 행렬'''(incidence matrix^영어)이라고 한다.

:

M_{ij}=\begin{cases} 1 & x_i\vartriangleleft l_j \\ 0 & x_i\not\vartriangleleft l_j \end{cases}

즉, 유한 결합 구조의 결합 행렬은 점

p_i

로 인덱싱된 행과 선

l_j

로 인덱싱된 열을 가지는 (0,1) 행렬이며, 여기서

ij

번째 항목은 점

p_i

가 선

l_j

위에 있을 경우(

p_i \vartriangleleft l_j

) 1이고 그렇지 않으면 0이다. 결합 행렬은 점과 선의 임의의 순서에 따라 달라지기 때문에 고유하게 결정되지 않는다.^[6]

한 비균일 결합 구조의 예시는 다음과 같다.

\begin{align}P &= \{ A, B, C, D, E, P \} \\[2pt]L &= \left\{ \begin{array}{ll}l = \{C, P, E \}, & m = \{ P \}, \\n = \{ P, D \}, & o = \{ P, A \}, \\p = \{ A, B \}, & q = \{ P, B \} \end{array} \right\}\end{align}

이 구조의 결합 행렬은 다음과 같다.

\begin{pmatrix}0 & 0 & 0 & 1 & 1 & 0 \\0 & 0 & 0 & 0 & 1 & 1 \\1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 \\1 & 0 & 0 & 0 & 0 & 0 \\1 & 1 & 1 & 1 & 0 & 1\end{pmatrix}

이는 아래의 결합표와 같다.

$I$	$l$	$m$	$n$	$o$	$p$	$q$
$A$	0	0	0	1	1	0
$B$	0	0	0	0	1	1
$C$	1	0	0	0	0	0
$D$	0	0	1	0	0	0
$E$	1	0	0	0	0	0
$P$	1	1	1	1	0	1

결합 구조 $C$ 가 결합 행렬 $M$ 을 가지면, 이중 구조 $C^*$ 는 전치 행렬 $M^T$ 를 결합 행렬로 가진다.

결합 구조는 점과 선의 순서를 적절히 배열했을 때, 해당 순서로 구성된 결합 행렬이 대칭 행렬인 경우 자기 이중 구조이다.

파노 평면의 한 예시에서 점이 $A, B, C, D, G, F, E$ 순서이고 선이 $l, p, n, s, r, m, q$ 순서일 때, 파노 평면은 다음의 결합 행렬을 가진다.

$\begin{pmatrix}1 & 1 & 1 & 0 & 0 & 0 & 0\\1 & 0 & 0 & 1 & 1 & 0 & 0 \\1 & 0 & 0 & 0 & 0 & 1 & 1 \\0 & 1 & 0 & 1 & 0 & 1 & 0 \\0 & 1 & 0 & 0 & 1 & 0 & 1 \\0 & 0 & 1 & 1 & 0 & 0 & 1 \\0 & 0 & 1 & 0 & 1 & 1 & 0\end{pmatrix} .$

이것이 대칭 행렬이므로, 파노 평면은 자기 이중 결합 구조이다.

3. 3. 레비 그래프

결합 구조

(X,L,\vartriangleleft)

가 주어졌을 때, 다음과 같은, 검은색 및 흰색의 그래프 색칠을 갖는 이분 그래프를 정의할 수 있다.

검은 꼭짓점은 점( $X$ 의 각 원소)에 대응한다.
흰 꼭짓점은 직선( $L$ 의 각 원소)에 대응한다.
검은 꼭짓점 $x\in X$ 및 흰 꼭짓점 $l\in L$ 사이에 변이 있을 필요 충분 조건은 $x\vartriangleleft l$ 인지 여부이다.

이를 결합 구조

(X,L,\vartriangleleft)

의 '''레비 그래프'''(Levi graph^영어)라고 한다.

각 사건 구조

C

는 구조의 이분 그래프 또는 사건 그래프라고 하는 Levi 그래프에 해당한다. 모든 이분 그래프는 2색으로 칠할 수 있으므로, Levi 그래프는 검은색과 흰색 정점 채색을 가질 수 있으며, 여기서 검은색 정점은 점에 해당하고 흰색 정점은

C

의 선에 해당한다. 이 그래프의 가장자리는 사건 구조의 플래그(사건 점/선 쌍)에 해당한다. 원래 Levi 그래프는 2차 일반화 사변형의 사건 그래프였으나,^[10] 이 용어는 H.S.M. Coxeter에 의해 확장되어^[11] 모든 사건 구조의 사건 그래프를 지칭하게 되었다.^[12]

파노 평면의 레비 그래프는 히우드 그래프이다. 히우드 그래프는 연결 그래프이며 정점 추이 그래프이므로, 흑백 정점을 서로 바꾸는 자기 동형 사상 (히우드 그래프 그림에서 수직축에 대한 반사에 의해 정의된 것과 같은)이 존재한다. 이는 파노 평면이 자기 쌍대임을 의미한다.

왼쪽에 있는 뫼비우스-칸토어 구성의 레비 그래프의 특정 표현은 도식의 중심을 기준으로

\pi/4

만큼의 회전(시계 방향 또는 시계 반대 방향)이 파란색과 빨간색 정점을 서로 바꾸고 모서리를 모서리에 매핑한다는 것을 보여준다. 즉, 이 그래프에는 색상을 서로 바꾸는 자기 동형 사상이 존재한다. 결과적으로 뫼비우스-칸토어 구성으로 알려진 이 입자 구조는 자기 쌍대이다.

4. 예

결합 구조는 각 선이 동일한 수의 점과 결합될 때 '''균일'''하다고 한다. 위에 제시된 예시 중 두 번째 그림(비균일 구조)을 제외한 나머지 구조는 모두 선 하나당 세 개의 점을 가지므로 균일한 구조이다.

4. 1. 자명한 결합 구조

임의의 집합 X에 대하여, 직선의 집합 L을 공집합 ∅으로 정의하면, 유일한 결합 구조 (X, ∅, ∅)를 정의할 수 있다. 이 결합 구조에는 직선이 하나도 존재하지 않는다는 특징이 있다.

마찬가지로, 임의의 집합 L에 대하여, 점의 집합 X를 공집합 ∅으로 정의하면, 유일한 결합 구조 (∅, L, ∅)를 정의할 수 있다. 이 결합 구조에는 점이 하나도 존재하지 않는다.

4. 2. 그래프

임의의 그래프

\Gamma

가 주어졌을 때, 다음과 같이 결합 구조

(\operatorname V(\Gamma),\operatorname E(\Gamma),\vartriangleleft)

를 정의할 수 있다.

점: $\Gamma$ 의 꼭짓점 ( $\operatorname V(\Gamma)$ )
직선: $\Gamma$ 의 변 ( $\operatorname E(\Gamma)$ )
결합 관계 ( $\vartriangleleft$ ): 변이 꼭짓점을 끝점으로 갖는지 여부

모든 그래프는 (이는 단순 그래프일 필요는 없으며, 루프나 다중 간선을 포함할 수 있다) 선(변) 하나당 두 개의 점(꼭짓점)을 가지는 균일한 결합 구조이다. 즉, 그래프의 꼭짓점들이 점 집합을 이루고, 그래프의 변들이 선 집합을 이루며, 결합 관계는 특정 꼭짓점이 특정 변의 끝점인지 여부로 정의된다.

4. 3. 다각형

2 이상의 정수

n\ge2

가 주어졌다고 가정하자. 점들의 집합

X=\{x_1,x_2,\dotsc,x_n\}

와 선들의 집합

L=\{l_1,l_2,\dotsc,l_n\}

위에 다음과 같은 결합 관계

\vartriangleleft

를 정의한다.

:

x_i\vartriangleleft l_j\iff j-i\equiv 0, 1\pmod n

이 결합 구조

(X,L,\vartriangleleft)

를 '''

n

각형'''(

n

角形,

n

-gon|^영어)이라고 한다.

특히,

n\ge3

일 경우, 이 결합 구조는 길이

n

의 순환 그래프에 대응하는 결합 구조이다.

4. 4. 블록 설계

임의의 블록 설계

(X,\mathcal B)

가 주어졌을 때, 이를 다음과 같이 결합 구조로 나타낼 수 있다.

점은 $X$ 의 원소로 삼는다.
직선은 블록, 즉 $\mathcal B$ 의 원소로 삼는다.
결합 관계는 점이 블록의 원소인지 여부( $\in$ )로 삼는다.

이렇게 정의된 결합 구조는

(X,\mathcal B,\in)

이다.

각 하이퍼그래프 또는 집합계는 결합 구조로 간주될 수 있다. 이 경우, 전체 집합이 "점"의 역할을 하고 해당 집합족이 "선"의 역할을 하며, 결합 관계는 집합 원소 관계

\in

가 된다. 반대로, 모든 결합 구조는 선을 그 선에 속하는 점들의 집합과 동일시함으로써 하이퍼그래프로 볼 수 있다.

일반적인 블록 설계는 집합

X

와

X

의 부분 집합들로 이루어진 집합족

F

로 구성된다(부분 집합의 중복은 허용된다). 결합 구조로서

X

는 점의 집합이고,

F

는 선의 집합이며, 이 맥락에서는 보통 "블록"이라고 불린다(중복된 블록은 서로 다른 이름을 가져야 하므로,

F

는 실제로는 멀티셋이 아닌 집합이다).

$F$ 의 모든 부분 집합(블록)이 동일한 크기를 가지면, 블록 설계는 균일(uniform)하다고 한다.
$X$ 의 각 원소가 동일한 수의 부분 집합(블록)에 나타나면, 블록 설계는 정규(regular)하다고 한다.

균일 설계의 쌍대 구조는 정규 설계이며, 그 반대도 성립한다.

4. 5. 사영 평면

'''사영 평면'''은 특별한 균등 정칙 결합 구조이다.

다음과 같은 점(P)과 선(L)으로 구성된 결합 구조를 생각해 보자. 이 구조는 파노 평면이라고 불린다.

\begin{align}P &= \{1,2,3,4,5,6,7\}, \\[2pt]L &= \left\{ \begin{array}{ll}\{1,2,3\}, & \{1,4,5\}, \\\{1,6,7\}, & \{2,4,6\}, \\\{2,5,7\}, & \{3,4,7\}, \\\{3,5,6\} \end{array} \right\}.\end{align}

블록 디자인으로 보면, 파노 평면은 균일하고 정규적인 특징을 가진다.

파노 평면에서 각 선은 세 개의 점으로 이루어져 있는데, 이 점들의 라벨(숫자)은 님 덧셈을 사용하여 더했을 때 0이 되는 특별한 관계를 가진다. 다른 관점에서 보면, 각 점의 번호를 이진수로 표현했을 때, 이는 유한체 GF(2) 상의 길이가 3인 0이 아닌 벡터로 볼 수 있다. 이때 세 벡터가 하나의 부분 공간을 생성하면, 즉 세 벡터의 합이 0 벡터가 되면, 이 세 점이 하나의 선을 이룬다.

4. 6. 리만 다양체

임의의 리만 다양체 (X,g)가 주어졌을 때, 다음과 같이 결합 구조를 정의할 수 있다.

점은 X의 원소로 삼는다.
직선은 (X,g)의 (확장 불가능) 측지선으로 삼는다.
결합 관계는 점이 측지선 위에 있는지 여부로 정의한다.

4. 7. 일반화 다각형

'''일반화 다각형'''은 사영 평면의 일반화이며, 특별한 종류의 준선형 공간이다.

5. 역사

“레비 그래프”라는 용어는 독일의 수학자 Friedrich Wilhelm Daniel Levi|프리드리히 빌헬름 다니엘 레비^de(1888~1966)의 이름을 딴 것이다.

각 사건 구조 C는 구조의 이분 그래프 또는 사건 그래프라고 하는 Levi 그래프에 해당한다. 모든 이분 그래프는 2색으로 칠할 수 있으므로, Levi 그래프는 검은색과 흰색 정점 채색을 가질 수 있으며, 여기서 검은색 정점은 점에 해당하고 흰색 정점은 C의 선에 해당한다. 이 그래프의 가장자리는 사건 구조의 플래그(사건 점/선 쌍)에 해당한다.

원래 Levi 그래프는 2차 일반화 사변형의 사건 그래프였다.^[10] 그러나 이 용어는 콕서터(H.S.M. Coxeter)에 의해 확장되어^[11] 모든 사건 구조의 사건 그래프를 지칭하게 되었다.^[12]

참조

_[1] 서적
_[2] 서적
_[3] 서적
_[4] 문서
_[5] 서적
_[6] 서적
_[7] 서적
_[8] 논문 Über die Construction der Configurationen ''n''₃
_[9] 간행물 Configurations and their realizations
_[10] 간행물 Finite Geometrical Systems University of Calcutta
_[11] 간행물 Self-dual configurations and regular graphs
_[12] 서적

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com