কির্শহফের উপপাদ্য। স্প্যানিং ট্রির সংখ্যা খুঁজে পাওয়া#
সমস্যা: আপনাকে একটি সংযুক্ত অনিয়ন্ত্রিত গ্রাফ (সম্ভাব্য একাধিক এজ সহ) দেওয়া হয় যা একটি সংলগ্নতা ম্যাট্রিক্স ব্যবহার করে প্রতিনিধিত্ব করা হয়। এই গ্রাফের বিভিন্ন স্প্যানিং ট্রির সংখ্যা খুঁজে বের করুন।
১৮৪৭ সালে কির্শহফ দ্বারা নিম্নলিখিত সূত্রটি প্রমাণ করা হয়েছিল।
কির্শহফের ম্যাট্রিক্স ট্রি উপপাদ্য#
$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$ সরানো ম্যাট্রিক্স।
কির্শহফের উপপাদ্য এই সূত্রকে জ্যামিতিক অর্থ দেয়।