Kernel matriks insiden pohon adalah $\emptyset$
Saya menemukan yang berikut dalam makalah yang saya coba baca:
Membiarkan $G=(V,E)$ menjadi grafik terarah dan biarkan $A \in \mathbb{R}^{\vert V \vert \times \vert E \vert}$menjadi matriks kejadian tepi simpul yang didefinisikan berdasarkan komponen sebagai$$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. $$... Jika grafiknya radial (pohon), maka $\ker A = \emptyset$.
Saya mengalami kesulitan mencoba memvisualisasikan mengapa pernyataan terakhir itu benar - saya tahu dengan ekuivalen dikatakan bahwa matriks kejadian tepi-simpul dari sebuah pohon adalah peringkat penuh. Adakah yang bisa menunjukkan sketsa bukti untuk ini? Terima kasih banyak!
EDIT : Maksud saya$\ker A$ memiliki kernel yang sepele, bukan kernel kosong.
Jawaban
Saya berasumsi bahwa dengan "grafik radial" atau "pohon", Anda mengacu pada pohon terarah dalam pengertian yang didefinisikan di sini .
Dengan itu, kami melanjutkan secara induktif. Kasus dengan$|V| = 2$itu sepele. Seandainya$|V| > 2$. Perhatikan bahwa setiap pohon memiliki simpul dengan derajat$1$; permutasi baris$A$ sehingga simpul ini (yang kami beri label sebagai "$n$") sesuai dengan baris pertama, dan mengubah kolom sehingga tepi yang berisi node ini sesuai dengan kolom pertama. Selanjutnya matriks (yang diubah) $A$ bisa ditulis dalam bentuk $$ A = \pmatrix{\pm1 & 0_{1\times (|E|-1)} \\ *& A'}, $$ dimana $*$ menunjukkan beberapa $(|V|-1) \times 1$ vektor dan $A'$ adalah matriks insiden dari grafik yang diperoleh dengan menghapus $n$dan tepi terkaitnya. Karena$A$ adalah blok segitiga atas, kita melihatnya $A$ memiliki kernel yang sepele jika dan hanya jika $A'$ memiliki kernel yang sepele.
Kesimpulannya mengikuti.