모서리 및 꼭지점 공간

그래프 이론의 수학적 분야에서는, 비방향 그래프의 에지 공간과 정점 공간은 각각 에지 집합과 정점 집합의 측면에서 정의된 벡터 공간이다.이러한 벡터 공간은 그래프를 연구하는 데 선형대수의 기법을 사용할 수 있게 해준다.

정의

$G{\displaystyle }$ ${\displaystyle :=(V}$, E${\displaystyle }$) ${\displaystyle G:=(V,E)}$을(를) 유한한 비방향 그래프로 한다$$.The vertex space ${\displaystyle {\mathcal {V}}(G)}$ of G is the vector space over the finite field of two elements ${\displaystyle \mathbb {Z} /2\mathbb {Z} :=\lbrace 0,1\rbrace }$ of all functions ${\displaystyle V\rightarrow \mathbb {Z} /2\mathbb {Z} }$. Every element$V{\displaystyle \mathcal{}}$($){\displaystyle {\mathcal{V}(G)}$는 당연히 V의 서브셋에 해당하며, V의 정점에 1을 할당한다.$또한{\displaystyle \mathcal{}}$ V의 모든 부분 집합은 V${\displaystyle }$( ${\displaystyle G}$) ${\displaystyle {\mathcal {V}(G)}$에 특성$$ 함수로 고유하게 표시된다.에지 공간 $E{\displaystyle \mathcal{}}$( ${\displaystyle G}$) ${\displaystyle {\mathcal {E}(G)}$은(는) 에지 세트 E에서 자유롭게 생성된 $Z{\displaystyle \mathbb{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle Z\mathbb{}}$ ${\$-vector$$ 공간이다$$.정점 공간의 치수는 따라서 그래프의 정점 수인 반면, 가장자리 공간의 치수는 가장자리 수입니다.

이러한 정의는 좀 더 명백하게 만들어질 수 있다.예를 들어, 에지 공간을 다음과 같이 설명할 수 있다.

• 벡터 공간의 요소는 $E{\displaystyle }$ ${\$${\displaystyle \mathrm{displaystyle}}$ $E}$의 하위 집합이며$,$ 즉 세트 $E{\displaystyle \mathcal{}}$ (${\displaystyle }$G${\displaystyle }$) ${\displaystyle {\mathcal$ {$E}(G)}$은(는) E의 전원 집합이다.
• 벡터 덧셈은 대칭차이로 정의된다: ${\displaystyle P}$+ ${\displaystyle Q}$ ${\displaystyle :=}$ ${\displaystyle P\mathrm{;}}$ ${\displaystyle Q}$ P${\displaystyle }$, ${\displaystyle Q\mathcal{}}$ ${\displaystyle \in }$ E${\displaystyle }$( ${\displaystyle G}$) ${\displaystyle P+Q:$$=P\Triangle Q\qquad P,Q\in {\mathcal {E}(G)}$
• 스칼라 곱셈은 다음과 같이 정의된다.
  • ${\displaystyle 0\cdot P:=\emptyset \qquad P\in {\mathcal {E}(G)}$
  • ${\displaystyle 1\cdot P:=P\qquad P\in {\mathcal {E}(G)}$

E의 싱글톤 서브셋은 $E{\displaystyle \mathcal{}}$( $){\displaystyle {\mathcal{E}(G)}$ 의 기초를 형성한다$.$

$또한{\displaystyle \mathcal{}}$ V${\displaystyle }$($){\displaystyle {\mathcal{V}(G)}$을(를) E${\displaystyle }$(${\displaystyle G)}$ ${\displaystyle {\mathcal{E}}}}$에 대해 정의된 것과 유사한 벡터 추가와 스칼라 곱셈을 가진 V의 파워셋으로 생각할 수 있다$.$

특성.

그래프 $G{\displaystyle }$ ${\displaystyle G}$에 대한 발생 행렬 $H{\displaystyle }$ ${\displaystyle H}$이(가) 하나의 가능한 선형 변환을 정의함$$

${\displaystyle H:{\mathcal {E}(G)\to {\mathcal {V}(G)}$

$G{\displaystyle }$ ${\displaystyle G}$의 모서리 공간과 정점 공간 사이$.$ $G{\displaystyle }$ ${\displaystyle G$의 입사 행렬은 선형 변환으로서 각 모서리들을 두 개의 입사 정점에 매핑한다.$v{\displaystyle }$$$ ${\displaystyle u}$ ${\displaystylevu}$을(를) $v{\displaystyle }$ ${\displaystyle v}$과($와{\displaystyle }$) u$${\$displaystyle$u} 사이의 가장자리가 되도록$$ 하십시오.

${\displaystyle H(vu)=v+u}$

사이클 공간과 절단 공간은 에지 공간의 선형 하위 공간이다.

참조

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6 (전자 제3판은 작성자 사이트에서 무료로 이용 가능).

참고 항목

• 공간을 순환하다.
• 공간을 절약하다