Ядро матрицы инцидентности дерева есть $\emptyset$
В статье, которую я пытаюсь прочитать, я наткнулся на следующее:
Позволять $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$ имеет тривиальное ядро, а не пустое ядро.
Ответы
Я предполагаю, что под «радиальным графом» или «деревом» вы имеете в виду ориентированное дерево в определенном здесь смысле .
Сказав это, мы продолжим индуктивно. Случай с$|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'$ имеет тривиальное ядро.
Напрашивается вывод.