발생행렬

수학에서, 입사 행렬은 보통 입사 관계라고 불리는 두 종류의 물체 사이의 관계를 보여주는 논리 행렬이다.첫 번째 클래스가 X이고 두 번째 클래스가 Y인 경우 행렬에는 X의 각 원소에 대해 행이 하나씩 있고 Y의 각 원소에 대해 열이 하나씩 있습니다.x 행과 y 열의 엔트리는 x와 y가 관련되어 있는 경우 1이고(이 컨텍스트에서는 사고라고 부릅니다), 관련되지 않은 경우 0입니다.다양성이 있습니다.아래를 참조해 주세요.

그래프 이론

발생 행렬은 그래프 이론에서 일반적인 그래프 표현이다.이는 정점과 버텍스 쌍의 관계를 부호화하는 인접 행렬과는 다릅니다.

무방향 및 방향 그래프

그래프 이론에서, 무방향 그래프는 두 가지 종류의 발생 행렬을 가지고 있다: 무방향과 방향이다.

무방향 그래프의 무방향 발생 행렬(또는 단순히 발생 행렬)은 n×m {\$displaystyle$ n$\times$ m$}$ 행렬이다. 여기서 n과 m은 각각 정점과 가장자리의 수이며, 정점 $(\$ 및 $e-display$ j$(\$displaystyle v_i}$=1$)인 경우 Bij =1이다.$e_{j}}$는 사고이고, 그렇지 않으면 0입니다.

예를 들어 오른쪽에 표시된 무방향 그래프의 입사행렬은 4행(정점 4개, e2, e3, $4개$ 에지에 대응)과 4열(e1, $e_{1}, e_{$3}, $e_{4$}):

이1 이2 이3 이4 1 1 1 1 0 2 1 0 0 0 3 0 1 0 1 4 0 0 1 1

=

$(\displaystyle {bmatrix}1&1&0&0&0\\0&1&1\end{bmatrix})}$

발생 행렬을 보면 각 열의 합계가 2라는 것을 알 수 있습니다.각 모서리에는 양 끝에 연결된 정점이 있기 때문입니다.

방향 그래프의 발생 행렬은 n×m {\$displaystyle$ n$\times$ m$}$ 행렬 B이다. 여기서 n과 m은 각각 정점과 모서리의 수이며, 여기서 끝 e j{\$displaystyle e_{j}$가 정점 v {\$displaystyle v_i$ 1인 경우 Bij $=$ -$1$이다.$($ 작성자가 반대 기호 규칙을 사용) 및 0($displaystyle$ v_${i$})입니다.

무방향 그래프의 지향성 발생 행렬은 그래프의 모든 방향의 발생 행렬이다.즉, 엣지 e의 열에는 e의 한 정점에 대응하는 행에 1개, e의 다른 정점에 대응하는 행에 -1개가 있고, 다른 모든 행에는 0이 있습니다.열의 엔트리를 부정하는 것은 가장자리의 방향을 반전시키는 것에 해당하기 때문에 방향성 발생 행렬은 열의 부정까지 고유하다.

그래프 G의 비방향성 발생 행렬은 다음과 같은 정리에 의해 선 그래프 L(G)의 인접 행렬과 관련된다.

${{displaystyle A(L(G)=B(G)^{\textsf {T}}B(G)-2I_{m}}.}$

여기서 A(L(G)는 G의 선 그래프의 인접 행렬, B(G)는 입사 행렬, I는_m 차원 m의 항등 행렬이다.

이산 라플라시안(또는 키르히호프 행렬)은 다음 공식에 의해 지향성 발생 행렬 B(G)로부터 구한다.

${{displaystyle B(G)B(G)^{\textsf {T}}.}$

그래프의 적분 주기 공간은 정수 또는 실수 또는 복소수 위의 행렬로 볼 때 지향성 발생 행렬의 null 공간과 같다.이진 사이클 공간은 2요소장 위의 행렬로 볼 때 지향성 또는 비방향성 발생 행렬의 null 공간이다.

부호 있는 그래프와 쌍방향 그래프

부호 그래프의 발생 행렬은 지향성 발생 행렬의 일반화이다.주어진 부호 그래프를 지향하는 것은 양방향 그래프의 발생 행렬이다.양수 에지의 열은 일반(부호 없음) 그래프의 모서리와 마찬가지로 한 끝점에 해당하는 행에 1이 있고 다른 끝점에 해당하는 행에 -1이 있습니다.음의 모서리 열은 두 행에 모두 1 또는 -1이 있습니다.선 그래프와 키르히호프 행렬 속성은 부호 있는 그래프로 일반화됩니다.

멀티그래프

입사 행렬의 정의는 루프와 다중 가장자리가 있는 그래프에 적용된다.루프를 지원하는 지향성 발생 행렬의 열은 그래프에 부호가 있고 루프가 음이 아닌 한 모두 0입니다. 그러면 입사 정점의 행에 있는 ±2를 제외하고 모두 0이 됩니다.

가중 그래프

가중 그래프는 1 대신 가장자리의 무게를 사용하여 나타낼 수 있습니다.예를 들어, 오른쪽에 있는 그래프의 발생 행렬은 다음과 같습니다.

이1 이2 이3 이4 1 2 1 5 0 2 2 0 0 0 3 0 1 0 6 4 0 0 5 6

=

$(\displaystyle {bmatrix} 2&1&5&0\2&0&0\0&6\end {bmatrix})}$

하이퍼그래프

일반 그래프의 모서리에는 두 개의 꼭지점(각 끝에 하나씩)만 있을 수 있으므로 그래프의 입사 행렬 열에는 0이 아닌 두 개의 항목만 있을 수 있습니다.반면 하이퍼그래프는 하나의 모서리에 여러 개의 정점을 할당할 수 있습니다. 따라서 음이 아닌 정수의 일반 행렬은 하이퍼그래프를 나타냅니다.

발생 구조

발생 구조 C의 발생 행렬은 p × q 행렬 B(또는 그 전치)이며, 여기서 p와 q는 각각 점과 선의 수이며, 점_i p와 선_j L이 인시던트이면 B = 1이고 그렇지 않으면 0이다_i,j.이 경우, 입사 행렬은 또한 구조의 Levi 그래프의 생체역시 행렬이다.모든 Levi 그래프에 대해 하이퍼그래프가 존재하며, 그 반대도 마찬가지이므로, 발생 구조의 발생 행렬은 하이퍼그래프를 설명한다.

유한 기하학

중요한 예는 유한 기하학이다.예를 들어 유한 평면에서 X는 점의 집합이고 Y는 선의 집합입니다.고차원의 유한 기하학에서 X는 점 집합이 될 수 있고 Y는 전체 공간(하이퍼플레인)의 치수보다 작은 차원의 하위 공간 집합이 될 수 있다. 또는 보다 일반적으로 X는 한 차원 d의 모든 하위 공간 집합이 될 수 있고 Y는 다른 차원 e의 모든 하위 공간 집합이 될 수 있으며, 발생률은 사람이 포함된다고 정의된다.t.

폴리토피스

마찬가지로 폴리토프에서 크기가 1씩 다른 셀 간의 관계를 입사행렬로 나타낼 수 있다.^[1]

블록 설계

또 다른 예는 블럭 설계입니다.여기서 X는 "점"의 유한 집합이고 Y는 "블록"이라고 불리는 X의 하위 집합의 클래스이며, 설계 유형에 따라 규칙이 적용됩니다.입사 행렬은 블록 설계 이론에서 중요한 도구입니다.예를 들어, 균형 불완전 2-설계(BIBD)의 기본 정리인 Fisher의 부등식을 사용하여 ^[2]블록 수가 최소한 점의 수라는 것을 증명할 수 있습니다.블록을 집합의 시스템으로 간주할 때, 발생 행렬의 영구적인 수는 개별 대표(SDR)의 시스템 수입니다.

「 」를 참조해 주세요.

• 패리-설리반 불변량

레퍼런스

추가 정보

• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Springer-Verlag, ISBN 3-540-26183-4
• Jonathan L Gross, Jay Yellen, Graph Theory 및 그 응용 프로그램, 제2판, 2006 (p 97, 무방향 그래프에 대한 발생 매트릭스, p 98, 다이그래프에 대한 발생 매트릭스)

외부 링크

• Weisstein, Eric W. "Incidence matrix". MathWorld.