ทฤษฎีบทของเคิร์ชฮอฟฟ์

Q: ตัวอย่าง

ขั้นแรก สร้างเมทริกซ์ลาปลาเซียน L สำหรับ กราฟรูปเพชร ตัวอย่าง G (ดูภาพด้านขวา):

Q: โครงร่างหลักฐาน

(การพิสูจน์ด้านล่างนี้อิงตาม สูตร Cauchy–Binet ข้อโต้แย้ง การอุปนัย เบื้องต้นสำหรับทฤษฎีบทของ Kirchhoff สามารถพบได้ในหน้า 654 ของ Moore (2011) [ 2 ] )

ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟทฤษฎีบทของ Kirchhoffหรือทฤษฎีบทเมทริกซ์ต้นไม้ของ Kirchhoffเป็นทฤษฎีบทเกี่ยวกับจำนวนต้นไม้แผ่คลุมในกราฟโดยระบุว่าจำนวนนี้สามารถคำนวณได้จากโคแฟกเตอร์ ใดๆ ของ เมทริกซ์ Laplacianของกราฟซึ่งแสดงให้เห็นโดยเฉพาะว่าจำนวนต้นไม้แผ่คลุมสามารถคำนวณได้จากข้อมูลกราฟในเวลาพหุนามทฤษฎีบทของ Kirchhoff เป็นการขยายความของสูตรของ Cayleyซึ่งให้จำนวนต้นไม้แผ่คลุมในกราฟสมบูรณ์ทฤษฎีบทนี้ตั้งชื่อตามนักคณิตศาสตร์ชาวเยอรมันGustav Kirchhoffผู้ตีพิมพ์ผลงานนี้ในปี 1847 มีการตีพิมพ์บทความของ Kirchhoff เป็นภาษาอังกฤษในปี 1958 ^{[ 1 ]}

คำจำกัดความและข้อความ

ให้Gเป็นกราฟแบบง่ายที่ไม่มีทิศทาง ต้นไม้แผ่คลุมของG คือกราฟย่อยของGที่เป็นต้นไม้ที่มีเซตของจุดยอดเดียวกันกับGเมท ริกซ์ ลาปลาเซียนLของG คือผลต่างระหว่าง เมทริกซ์ดีกรีของกราฟ( เมทริกซ์แนวทแยงของดีกรีจุดยอด)และเมทริกซ์ประชิด ( เมทริกซ์ (0,1)ที่มีค่า 1 ในตำแหน่งที่จุดยอดอยู่ติดกัน และค่า 0 ในตำแหน่งอื่น) ตัวประกอบร่วมของLได้มาจากการลบแถว (เช่น แถวที่i ) และคอลัมน์ (เช่น คอลัมน์ที่ j ) ของLหาดีเทอร์มิแนนต์ของเมทริกซ์ที่เล็กลงนั้น แล้วคูณด้วย (-1) ⁱ⁺ j

ทฤษฎีบทของ Kirchhoff กล่าวว่า จำนวนต้นไม้แผ่คลุมของกราฟนั้นเท่ากับค่าโคแฟกเตอร์ใดๆ ของเมทริกซ์ลาปลาเซียนของกราฟนั้น (โดยเฉพาะอย่างยิ่ง ค่าโคแฟกเตอร์ทั้งหมดเหล่านี้มีค่าเท่ากัน)

ตัวอย่าง

ขั้นแรก สร้างเมทริกซ์ลาปลาเซียนL สำหรับ กราฟรูปเพชร ตัวอย่างG (ดูภาพด้านขวา):

L=\left[{\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right].

ถัดไป สร้างเมทริกซ์Q ^*โดยการลบแถวและคอลัมน์ใดๆ ออกจากQตัวอย่างเช่น การลบแถวที่ 1 และคอลัมน์ที่ 1 จะได้

L^{\ast }=\left[{\begin{array}{rrr}3&-1&-1\\-1&3&-1\\-1&-1&2\end{array}}\right].

สุดท้าย หาค่าดีเทอร์มิแนนต์ของL ^*ซึ่งได้ผลลัพธ์เป็น 8 จำนวนต้นไม้แผ่คลุมของGที่แสดงอยู่ทางด้านขวา ก็มีค่าเท่ากับ 8 เช่นกัน

โครงร่างหลักฐาน

(การพิสูจน์ด้านล่างนี้อิงตามสูตร Cauchy–Binet ข้อโต้แย้ง การอุปนัยเบื้องต้นสำหรับทฤษฎีบทของ Kirchhoff สามารถพบได้ในหน้า 654 ของ Moore (2011) ^{[ 2 ]} )

ขั้นแรก สังเกตว่าเมทริกซ์ลาปลาเซียนมีคุณสมบัติที่ว่า ผลรวมของสมาชิกในทุกแถวและทุกคอลัมน์มีค่าเป็น 0 ดังนั้นเราจึงสามารถแปลงไมเนอร์ใดๆ ไปเป็นไมเนอร์อื่นได้โดยการบวกแถวและคอลัมน์ สลับตำแหน่ง และคูณแถวหรือคอลัมน์ด้วย -1 ดังนั้นค่าโคแฟกเตอร์จึงเหมือนกัน ยกเว้นเครื่องหมาย และสามารถตรวจสอบได้ว่าในความเป็นจริงแล้ว ค่าโคแฟกเตอร์มีเครื่องหมายเดียวกัน

เราจะแสดงให้เห็นว่าดีเทอร์มิแนนต์ของไมเนอร์M คือจำนวนต้นไม้แผ่คลุม (spanning trees) ให้nเป็นจำนวนจุดยอดของกราฟ และmเป็นจำนวนขอบของกราฟ เมทริกซ์เหตุการณ์Eเป็น เมทริกซ์ขนาด n x mซึ่งสามารถกำหนดได้ดังนี้ สมมติว่า ( i , j ) เป็น ขอบที่ kของกราฟ และi < jดังนั้นE = 1, E = −1 และค่าอื่นๆ ในคอลัมน์kเป็น 0 (ดูเมทริกซ์เหตุการณ์แบบมีทิศทางเพื่อทำความเข้าใจเมทริกซ์เหตุการณ์E ที่ปรับเปลี่ยนนี้ ) สำหรับตัวอย่างก่อนหน้านี้ (โดยที่n = 4 และm = 5):

E=\left[{\begin{array}{rrrrr}1&1&0&0&0\\-1&0&1&1&0\\0&-1&-1&0&1\\0&0&0&-1&-1\end{array}}\right].

โปรดจำไว้ว่าเมทริกซ์ลาปลาเซียนLสามารถแยกตัวประกอบเป็นผลคูณของเมทริกซ์เหตุการณ์และเมทริกซ์ทรานสโพส ของมัน ได้ นั่นคือL = EE ^Tยิ่งไปกว่านั้น ให้Fเป็นเมทริกซ์E ที่ ลบแถวแรกออกไป ดังนั้นFF ^T = M

สูตรโคชี-บิเนต์ช่วยให้เราสามารถเขียนได้ดังนี้

\det \left(M_{11}\right)=\sum _{S}\det \left(F_{S}\right)\det \left(F_{S}^{\mathrm {T} }\right)=\sum _{S}\det \left(F_{S}\right)^{2}

โดยที่Sครอบคลุมเซตย่อยของ [ m ] ที่มีขนาดn − 1 และF แทนเมทริกซ์ขนาด ( n − 1) x ( n − 1) ที่มีคอลัมน์เป็นคอลัมน์ของFที่มีดัชนีอยู่ในS จากนั้น Sแต่ละตัวจะระบุ ขอบ n − 1 ขอบของกราฟดั้งเดิม และสามารถแสดงได้ว่า ถ้าขอบเหล่านั้นก่อให้เกิดต้นไม้แผ่ขยาย (spanning tree) แล้ว ดีเทอร์มิแนนต์ของF จะเป็น +1 หรือ −1 และถ้าขอบเหล่านั้นไม่ก่อให้เกิดต้นไม้แผ่ขยายแล้ว ดีเทอร์มิแนนต์จะเป็น 0 ซึ่งเป็นการเสร็จสิ้นการพิสูจน์

กรณีเฉพาะและข้อสรุปทั่วไป

สูตรของเคย์ลีย์

สูตรของเคย์ลีย์ได้มาจากทฤษฎีบทของเคิร์ชฮอฟฟ์ในกรณีพิเศษ เนื่องจากเวกเตอร์ทุกตัวที่มีค่า 1 ในตำแหน่งหนึ่ง ค่า -1 ในอีกตำแหน่งหนึ่ง และค่า 0 ในตำแหน่งอื่น ๆ ล้วนเป็นเวกเตอร์ลักษณะเฉพาะของเมทริกซ์ลาปลาเซียนของกราฟสมบูรณ์ โดยมีค่าลักษณะเฉพาะที่สอดคล้องกันคือnเวกเตอร์เหล่านี้รวมกันครอบคลุมปริภูมิที่มีมิติn − 1 ดังนั้นจึงไม่มีค่าลักษณะเฉพาะอื่น ๆ ที่ไม่เท่ากับศูนย์

อีกทางเลือกหนึ่ง โปรดทราบว่า เนื่องจากสูตรของ Cayley ให้จำนวนต้นไม้ที่มีป้ายกำกับที่แตกต่างกันของกราฟสมบูรณ์K เราจึงจำเป็นต้องคำนวณโคแฟกเตอร์ใดๆ ของเมทริกซ์ Laplacian ของK เมทริกซ์ Laplacian ในกรณีนี้คือ

{\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{bmatrix}}.

โคแฟกเตอร์ใดๆ ของเมทริกซ์ข้างต้นคือn ⁿ⁻²ซึ่งเป็นสูตรของเคย์ลีย์

การกำหนดสูตรโดยใช้ค่าลักษณะเฉพาะของเมทริกซ์ลาปลาเซียน

ทฤษฎีบทนี้สามารถกำหนดได้โดยใช้ค่าลักษณะเฉพาะของเมทริกซ์ลาปลาเซียน ค่าลักษณะเฉพาะเหล่านี้จะไม่เป็นลบเสมอ และหนึ่งในนั้นต้องเป็นศูนย์ สำหรับกราฟGที่มีnจุดยอด ให้ 0 = λ ≤λ ≤ λ ≤ ... ≤ λ เป็นค่าลักษณะเฉพาะของเมทริกซ์ลาปลาเซียนของกราฟนั้น แล้วจำนวน ต้นไม้แผ่คลุม t ( G ) ของGคือ

t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.

ทฤษฎีบทของ Kirchhoff สำหรับมัลติกราฟ

ทฤษฎีบทของ Kirchhoff ใช้ได้กับมัลติกราฟเช่นกัน โดยเมทริกซ์Lจะถูกปรับเปลี่ยนดังนี้:

ค่าq เท่ากับ− mโดยที่mคือจำนวนขอบระหว่างiและj
เมื่อนับดีกรีของจุดยอดจะไม่นับรวมวงวน ทั้งหมด

สูตรของ Cayley สำหรับมัลติกราฟสมบูรณ์คือm ^{n −1} ( n ^{n −1} −( n −1) n ^{n −2} )โดยใช้วิธีการเดียวกันกับที่แสดงไว้ข้างต้น เนื่องจากกราฟแบบง่ายเป็นมัลติกราฟที่มีm = 1

การระบุต้นไม้แผ่ขยายอย่างชัดเจน

ทฤษฎีบทของ Kirchhoff สามารถเสริมความแข็งแกร่งได้โดยการเปลี่ยนแปลงนิยามของเมทริกซ์ Laplacian แทนที่จะนับเพียงขอบที่ออกจากแต่ละจุดยอดหรือเชื่อมต่อจุดยอดสองจุด ให้กำหนดตัวแปรที่ไม่แน่นอน ให้กับแต่ละขอบ และให้ค่าในตำแหน่ง ( i , j ) ของเมทริกซ์ Laplacian ที่แก้ไขแล้วเป็นผลรวมของตัวแปรที่ไม่แน่นอนที่สอดคล้องกับขอบระหว่าง จุดยอดที่ iและjเมื่อiไม่เท่ากับj และเป็นผลรวมเชิงลบของตัวแปรที่ไม่แน่นอนทั้งหมดที่สอดคล้องกับ ขอบที่ออกจาก จุดยอดที่ iเมื่อiเท่ากับj

ดีเทอร์มิแนนต์ของเมทริกซ์ลาปลาเซียนที่ปรับเปลี่ยนแล้ว โดยการลบแถวและคอลัมน์ใดๆ (คล้ายกับการหาจำนวนต้นไม้แผ่คลุมจากเมทริกซ์ลาปลาเซียนดั้งเดิม) ข้างต้น จะเป็นพหุนามเอกพันธุ์ (พหุนามเคิร์ชฮอฟฟ์) ในตัวแปรที่สอดคล้องกับขอบของกราฟ หลังจากรวบรวมพจน์และทำการตัดทอนที่เป็นไปได้ทั้งหมดแล้วเอกนาม แต่ละตัว ในนิพจน์ที่ได้จะแสดงถึงต้นไม้แผ่คลุมที่ประกอบด้วยขอบที่สอดคล้องกับตัวแปรที่ปรากฏในเอกนามนั้น ด้วยวิธีนี้ เราสามารถแจงนับต้นไม้แผ่คลุมทั้งหมดของกราฟได้อย่างชัดเจนโดยการคำนวณดีเทอร์มิแนนต์เท่านั้น

สำหรับการพิสูจน์ทฤษฎีบทเวอร์ชันนี้ โปรดดูที่ Bollobás (1998) ^{[ 3 ]}

แมทรอยด์

ต้นไม้แผ่คลุมของกราฟก่อให้เกิดฐานของแมทรอยด์กราฟิกดังนั้นทฤษฎีบทของ Kirchhoff จึงให้สูตรสำหรับจำนวนฐานในแมทรอยด์กราฟิก วิธีเดียวกันนี้ยังสามารถใช้เพื่อกำหนดจำนวนฐานในแมทรอยด์ปกติ ซึ่งเป็นการขยายความของแมทรอย ด์กราฟิก( Maurer 1976 )

ทฤษฎีบทของ Kirchhoff สำหรับมัลติกราฟแบบมีทิศทาง

ทฤษฎีบทของ Kirchhoff สามารถปรับเปลี่ยนเพื่อให้ได้จำนวนต้นไม้แผ่ขยายแบบมีทิศทางในมัลติกราฟแบบมีทิศทางได้ โดยเมทริกซ์Qถูกสร้างขึ้นดังนี้:

ค่าq สำหรับiและj ที่แตกต่างกัน จะมีค่าเท่ากับ − mโดยที่mคือจำนวนขอบจากiไปยังj
ค่าq เท่ากับดีกรีขาเข้าของiลบด้วยจำนวนลูปที่i

จำนวนของต้นไม้แผ่ขยายแบบมีทิศทางที่รากอยู่ที่จุดยอดiคือดีเทอร์มิแนนต์ของเมทริกซ์ที่ได้จากการลบแถวและคอลัมน์ที่i ของเมทริกซ์ Q

การนับป่าk- องค์ประกอบที่ครอบคลุม

ทฤษฎีบทของ Kirchhoff สามารถขยายให้ครอบคลุมป่าแผ่ขยาย $k$ องค์ประกอบ ในกราฟที่ไม่มีน้ำหนักได้^[⁴^]ป่า แผ่ขยาย $k$ องค์ประกอบคือกราฟย่อยที่มี $k$ องค์ประกอบที่เชื่อมต่อกันซึ่งมีจุดยอดทั้งหมดและไม่มีวงจร กล่าวคือ มีเส้นทางอย่างมากที่สุดหนึ่งเส้นทางระหว่างจุดยอดแต่ละคู่ กำหนดให้ป่าF ดังกล่าว ที่มีองค์ประกอบที่เชื่อมต่อกัน ${\textstyle F_{1},\dots ,F_{k}}$ กำหนดน้ำหนักของมัน ${\textstyle w(F)=|V(F_{1})|\cdot \dots \cdot |V(F_{k})|}$ ให้เป็นผลคูณของจำนวนจุดยอดในแต่ละส่วนประกอบ จากนั้น

\sum _{F}w(F)=q_{k},

โดยผลรวมนั้นครอบคลุมป่าแผ่ขยาย $k องค์ประกอบทั้งหมด และ$ ${\textstyle q_{k}}$ คือสัมประสิทธิ์ของ ${\textstyle x^{k}}$ ของพหุนาม

(x+\lambda _{1})\dots (x+\lambda _{n-1})x.

ตัวประกอบสุดท้ายในพหุนามเกิดจากค่าไอเกนเป็นศูนย์ ${\textstyle \lambda _{n}=0}$ กล่าวให้ชัดเจนยิ่งขึ้นคือ จำนวน ${\textstyle q_{k}}$ สามารถคำนวณได้ดังนี้

q_{k}=\sum _{\{i_{1},\dots ,i_{n-k}\}\subset \{1\dots n-1\}}\lambda _{i_{1}}\dots \lambda _{i_{n-k}}.

โดยผลรวมนั้นครอบคลุมเซตย่อยทั้งหมดที่มีสมาชิก ( n − k ) ตัวของ ${\textstyle \{1,\dots ,n\}}$ . ตัวอย่างเช่น

{\begin{aligned}q_{n-1}&=\lambda _{1}+\dots +\lambda _{n-1}=\operatorname {tr} Q=2|E|\\q_{n-2}&=\lambda _{1}\lambda _{2}+\lambda _{1}\lambda _{3}+\dots +\lambda _{n-2}\lambda _{n-1}\\q_{2}&=\lambda _{1}\dots \lambda _{n-2}+\lambda _{1}\dots \lambda _{n-3}\lambda _{n-1}+\dots +\lambda _{2}\dots \lambda _{n-1}\\q_{1}&=\lambda _{1}\dots \lambda _{n-1}\end{aligned}}

เนื่องจากป่าแผ่ขยายที่มี ส่วนประกอบ n −1 สอดคล้องกับขอบเดียว กรณี k = n − 1 จึงระบุว่าผลรวมของค่าลักษณะเฉพาะของQเป็นสองเท่าของจำนวนขอบ กรณี k = 1 สอดคล้องกับทฤษฎีบทของ Kirchhoff ดั้งเดิม เนื่องจากน้ำหนักของต้นไม้แผ่ขยายทุกต้นคือn

การพิสูจน์สามารถทำได้ในลักษณะเดียวกับการพิสูจน์ทฤษฎีบทของ Kirchhoff ตัวผกผันได้ $(n-k)\times (n-k)$ เมทริกซ์ย่อยของเมทริกซ์เหตุการณ์สอดคล้องแบบหนึ่งต่อหนึ่งกับ ป่าแผ่ขยาย kองค์ประกอบ โดยมีการเลือกจุดยอดสำหรับแต่ละองค์ประกอบ

สัมประสิทธิ์ ${\textstyle q_{k}}$ ขึ้นอยู่กับการ ลงนามในสัมประสิทธิ์ของพหุนามลักษณะเฉพาะของQ

ดูเพิ่มเติม

[ 1 ]

[ 2 ]

[ 3 ]

[