কির্শহফের থিওরেম। স্প্যানিং ট্রির সংখ্যা খুঁজে পাওয়া#
সমস্যা: তোমাকে একটি কানেক্টেড আনডিরেক্টেড গ্রাফ (সম্ভাব্য একাধিক এজ সহ) দেওয়া হয় যা একটি অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করে রিপ্রেজেন্ট করা হয়। এই গ্রাফের বিভিন্ন স্প্যানিং ট্রির সংখ্যা খুঁজে বের করো।
১৮৪৭ সালে কির্শহফ নিচের সূত্রটি প্রুফ করেছিলেন।
কির্শহফের ম্যাট্রিক্স ট্রি থিওরেম#
ধরো $A$ হলো গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স: $A_{u,v}$ হল $u$ এবং $v$ এর মধ্যে এজের সংখ্যা। ধরো $D$ হলো গ্রাফের ডিগ্রি ম্যাট্রিক্স: একটি ডায়াগোনাল ম্যাট্রিক্স যেখানে $D_{u,u}$ হল ভার্টেক্স $u$ এর ডিগ্রি (একাধিক এজ এবং লুপ সহ - এজ যা ভার্টেক্স $u$ কে নিজের সাথে সংযুক্ত করে)।
গ্রাফের ল্যাপ্লাসিয়ান ম্যাট্রিক্স $L = D - A$ হিসেবে ডিফাইন করা হয়। কির্শহফের থিওরেম অনুযায়ী, এই ম্যাট্রিক্সের সমস্ত সহগুণক একে অপরের সমান, এবং তারা গ্রাফের স্প্যানিং ট্রির সংখ্যার সমান। একটি ম্যাট্রিক্সের $(i,j)$ কোফ্যাক্টর হল $(-1)^{i + j}$ এর গুণফল, $i$-তম সারি এবং $j$-তম কলাম সরিয়ে পাওয়া ম্যাট্রিক্সের ডিটারমিন্যান্টের সাথে। তাই তুমি, উদাহরণস্বরূপ, ম্যাট্রিক্স $L$ এর শেষ সারি এবং শেষ কলাম মুছতে পারো, এবং তাহলে ম্যাট্রিক্সের ডিটারমিন্যান্টের পরম মান তোমাকে স্প্যানিং ট্রির সংখ্যা দেবে।
ম্যাট্রিক্সের ডিটারমিন্যান্ট গাউসিয়ান এলিমিনেশন ব্যবহার করে $O(N^3)$ এ বের করা যায়।
এই থিওরেমের প্রুফ অত্যন্ত কঠিন এবং এখানে উপস্থাপন করা হয়নি; প্রুফের একটি রূপরেখা এবং একাধিক এজ ছাড়া গ্রাফ এবং ডিরেক্টেড গ্রাফের জন্য থিওরেমের ভেরিয়েশনের জন্য উইকিপিডিয়া দেখো।
কির্শহফের সার্কিট আইনের সাথে সম্পর্ক#
কির্শহফের ম্যাট্রিক্স ট্রি থিওরেম এবং বৈদ্যুতিক সার্কিটের জন্য কির্শহফের আইন সুন্দর উপায়ে সম্পর্কিত। এটি দেখানো সম্ভব (ওম এর আইন এবং কির্শহফের প্রথম আইন ব্যবহার করে) যে সার্কিটের দুটি পয়েন্ট $i$ এবং $j$ এর মধ্যে প্রতিরোধ $R_{ij}$ হল
$$R_{ij} = \frac{ \left| L^{(i,j)} \right| }{ | L^j | }.$$এখানে ম্যাট্রিক্স $L$ পাওয়া যায় কন্ডাক্ট্যান্স ম্যাট্রিক্স $A$ থেকে ($A_{i,j}$ হল পয়েন্ট $i$ এবং $j$ এর মধ্যে রেজিস্ট্যান্সের বিপরীত) কির্শহফের ম্যাট্রিক্স ট্রি থিওরেমে দেখানো পদ্ধতি ব্যবহার করে। $T^j$ হল সারি এবং কলাম $j$ সরানো ম্যাট্রিক্স, $T^{(i,j)}$ হল দুটি সারি এবং দুটি কলাম $i$ এবং $j$ সরানো ম্যাট্রিক্স।
কির্শহফের থিওরেম এই সূত্রকে জ্যামিতিক অর্থ দেয়।