موضوع مقاله: نظریه کیرشهف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نظریه کیرشهف | مقدمه: در حوزهٔ ریاضیات و در موضوع نظریه گراف، نظریهٔ کیرشهف یا نظریهٔ ماتریس درخت کیرشهف که از روی اسم گوستاو کیرشهف نامگذاری شده‌است در مود تعداد درخت‌های پوشا در یک گراف است که نشان می‌دهد این عدد را می‌توان در زمان چند جمله ای به عنوان دترمینان ماتریس به دست آمده از گراف محاسبه کرد. | ## بخش 1: نظریه کیرشهف | این نظریه یک تعمیم از فرمول کیلی است که تعداد درخت‌های پوشا در یک گراف کامل به دست می‌آورد. نظریهٔ کیرشهف بر پایهٔ مفهموم ماتریس لاپلاس یک گراف است که برابر با اختلاف بین ماتریس درجه (یک ماتریس قطری با درجهٔ راس‌ها در قطرها) و ماتریس مجاورت آن است. برای یک گراف همبند مشخص G با n راس نامگذاری شده فرض کنید λ1, λ2, … , λn−1 مقادیر ویژه غیر صفر ماتریس لاپلاس آن باشد. پس تعداد درخت‌های پوشای G برابر است با: که یعنی تعداد درخت‌های پوشا برابر با هر هم عامل ماتریس لاپلاس G است. در ابتدا، ماتریس لاپلاس Q را برای گراف الماسی G می‌نویسیم (تصویر را در سمت چپ ببینید): سپس، ماتریس * Q را با حذف کردن یکی از سطرها و ستون‌های ماتریس Q تشکیل می‌دهیم. برای مثال، با حذف ردیف ۱ و ستون ۱ داریم: در نهایت، دترمینان * Q را برای ساخت (t(G به دست می‌آوریم که برای گراف الماسی برابر ۸ است. (توجه کنید که (t(G یک هم عامل (۱٬۱) از Q در این مثال است) اثبات کلی ابتدا در نظر داشته باشید که لاپلاس خاصیتی دارد که مجموع تعداد مقادیرش در هر ستون و در هر ردیف برابر با صفر است. | ## بخش 2: نظریه کیرشهف | ​پس می‌توانیم هر کهاد را با افزودن ستون‌ها و ردیف‌ها، جابه‌جا کردن آن‌ها یا ضرب یک ردیف یا ستون در ۱- یه یک کهاد دیگر تبدیل کنیم؛ بنابراین هم عامل‌ها مشابه هم هستند و می‌توان تأیید کرد که در واقع آن‌ها علامت یکسانی دارند. در ادامه اقدام به نشان دادن این می‌کنیم که دترمینان کهاد M11 تعداد درخت‌های پوشا را می‌شمارد. ماتریس وقوع یک ماتریس n در m است که به این صورت تعریف می‌شود: فرض کنید که (i,j) یال k -ام گراف باشد، و i <j. برای مثال قبل (با n = ۴ و m = ۵) داریم: در نظر داشته باشید که لاپلاس L می‌تواند به حاصل ضرب ماتریس وقوع و ترانهاده اش ساده شود، یعنی L = EET. علاوه بر این، فرض کنید F همان ماتریس E باشد که اولین ردیفش حذف شده باشد، پس داریم FFT = M11. حالا فرمول کوچی - بینت اجازه می‌دهد که بنویسیم: که محدودهٔ S بین زیرمجموعه‌های [m] با اندازهٔ n-1 است و FS نشان می‌دهد که ماتریس (n − ۱) در (n − ۱) که ستون‌هایش همان F هستند که در S مرتب شده‌اند. پس هر S با n − ۱ یال از گراف اصلی، و می‌توان نشان داد که آن یال‌ها موجب یک درخت پوشا می‌شوند اگر و تنها اگر دترمینان FS برابر با ۱+ یا ۱- باشد، و موجب یک درخت پوشا نمی‌شوند اگر و تنها اگر دترمینان برابر ۰ شود. | ## بخش 3: نظریه کیرشهف | موارد خاص و تعمیم‌ها فرمول کیلی فرمول کیلی از نظریهٔ کیرشهف به عنوان یک حالت خاص تبعیت می‌کند چون هر بردار با طول ۱ در هر مکان، ۱- در مکان دیگر و ۰ در جایی دیگر یک بردار ویژه از ماتریس لاپلاس گراف کامل با مقدار ویژهٔ متناظر با n است. این بردارها با هم دیگر یک فضا به اندازهٔ n − ۱ پوشش می‌دهند که پس هیچ مقدار ویژهٔ غیرصفر دیگری وجود ندارد. متناوباً، توجه داشته باشید که همان‌طور که فرمول کیلی تعداد درخت‌های نامگذاری شدهٔ مجزای یک گراف کامل Kn را به دست می‌آورد، ما باید هر هم عامل ماتریس لاپلاس Kn را محاسبه کنیم. لاپلاس ماتریس در این مورد برابر است با: هر هم عامل از ماتریس بالا برابر است با nn−2. نظریهٔ کیرشهف برای گراف‌های چندگانه نظریهٔ کیرشهف برای گراف‌های چندگانه نیز به خوبی صادق است؛ ماتریس Q به صورت زیر اصلاح شده‌است: مقدار qi,j برابر با m- است. که m تعداد یال‌های بین i و j است؛ هنگام شمردن درجهٔ یک راس، تمام دورها حذف می‌شوند. | ## جمع‌بندی | فرمول کیلی برای یک گراف چندگانهٔ کامل برابر با (mn-1(nn-1-(n-1)nn-2 است که از روش بالا ساخته شده‌است چون یک گراف ساده یه گراف چندگانه با m = ۱ است.