เคอร์เนลของเมทริกซ์อุบัติการณ์ของต้นไม้คือ $\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'$ มีเคอร์เนลเล็กน้อย
ข้อสรุปดังนี้