트리의 발생 행렬의 커널은 다음과 같습니다. $\emptyset$

Question

내가 읽으려고하는 논문에서 다음과 같은 내용을 발견했습니다.

허락하다 $G=(V,E)$ 방향성 그래프이고 $A \in \mathbb{R}^{\vert V \vert \times \vert E \vert}$다음과 같이 구성 요소별로 정의 된 노드 에지 발생 행렬$$A_{ke} = \left\{ \begin{array}{cl} 1 & \text{if node } k \text{ is the source node of edge }e\\ -1 & \text{if node } k \text{ is the sink node of edge }e\\ 0 & \text{otherwise} \end{array} \right. $$... 그래프가 방사형 (나무)이면 $\ker A = \emptyset$.

마지막 진술이 사실 인 이유를 시각화하는 데 어려움을 겪고 있습니다. 마찬가지로 트리의 노드 에지 발생 행렬이 전체 순위라는 것을 알고 있습니다. 누구든지 이것에 대한 증명 스케치를 보여줄 수 있습니까? 감사합니다!

편집 : 나는 의미$\ker A$ 빈 커널이 아닌 사소한 커널이 있습니다.

Answer 1

"방사형 그래프"또는 "트리"는 여기에 정의 된 의미에서 방향성 트리를 참조한다고 가정합니다 .

그렇게 말하면서 우리는 귀납적으로 진행합니다. 케이스$|V| = 2$사소합니다. 한다고 가정$|V| > 2$. 모든 나무에는 학위가있는 노드가 있습니다.$1$; 행을 순회하다$A$ 그래서이 노드 (우리는 "$n$")는 첫 번째 행에 해당하고,이 노드를 포함하는 에지가 첫 번째 열에 해당하도록 열을 순화합니다. 다음은 (순환 된) 행렬 $A$ 형식으로 작성할 수 있습니다. $$ A = \pmatrix{\pm1 & 0_{1\times (|E|-1)} \\ *& A'}, $$ 어디 $*$ 일부를 나타냅니다 $(|V|-1) \times 1$ 벡터 및 $A'$ 삭제하여 얻은 그래프의 발생 행렬입니다. $n$및 관련 가장자리. 때문에$A$ 블록 상부 삼각형입니다. $A$ 다음과 같은 경우에만 사소한 커널이 있습니다. $A'$ 사소한 커널이 있습니다.

결론은 다음과 같습니다.