نظریه کیرشهف

در حوزه ریاضیات و در موضوع نظریه گراف، نظریه کیرشهف یا نظریه ماتریس درخت کیرشهف که از روی اسم گوستاو کیرشهف نامگذاری شده‌است در مود تعداد درخت‌های پوشا در یک گراف است که نشان می‌دهد این عدد را می‌توان در زمان چند جمله‌ای به عنوان دترمینان ماتریس به دست آمده از گراف محاسبه کرد. این نظریه یک تعمیم از فرمول کیلی است که تعداد درخت‌های پوشا در یک گراف کامل به دست می‌آورد.
نظریه کیرشهف بر پایه مفهموم ماتریس لاپلاس یک گراف است که برابر با اختلاف بین ماتریس درجه (یک ماتریس قطری با درجه راس‌ها در قطرها) و ماتریس مجاورت آن است.
برای یک گراف همبند مشخص G با n راس نامگذاری شده فرض کنید  1 ,  2 , … ,  n −1 مقادیر ویژه غیر صفر ماتریس لاپلاس آن باشد. پس تعداد درخت‌های پوشای G برابر است با:
که یعنی تعداد درخت‌های پوشا برابر با هر هم عامل ماتریس لاپلاس G است.
مثالی از نظریه ماتریس درخت
برای به دست آوردن تعداد درخت‌های پوشای نامگذاری شده این گراف می‌توان از نظریه ماتریس درخت استفاده کرد.
در ابتدا، ماتریس لاپلاس Q را برای گراف الماسی G می‌نویسیم (تصویر را در سمت چپ ببینید):
Q = \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 تشکیل می‌دهیم. برای مثال، با حذف ردیف ۱ و ستون ۱ داریم:
Q^\ast =
\left\begin{array{rrr
3 - -1 - -1 \\
-1 - 3 - -1 \\
-1 - -1 - 2
\end{array\right.
در نهایت، دترمینان * Q را برای ساخت (t(G به دست می‌آوریم که برای گراف الماسی برابر ۸ است. (توجه کنید که (t(G یک هم عامل (۱،۱) از Q در این مثال است)
اثبات کلی
ابتدا در نظر داشته باشید که لاپلاس خاصیتی دارد که مجموع تعداد مقادیرش در هر ستون و در هر ردیف برابر با صفر است. پس می‌توانیم هر کهاد را با افزودن ستون‌ها و ردیف‌ها، جابه‌جا کردن آن‌ها یا ضرب یک ردیف یا ستون در ۱- یه یک کهاد دیگر تبدیل کنیم؛ بنابراین هم عامل‌ها مشابه هم هستند و می‌توان تایید کرد که در واقع آن‌ها علامت یکسانی دارند.
در ادامه اقدام به نشان دادن این می‌کنیم که دترمینان کهاد M 11 تعداد درخت‌های پوشا را می‌شمارد. فرض کنید n تعدا راس‌های گراف و m تعداد یال‌های آن باشد. ماتریس وقوع یک ماتریس n در m است که به این صورت تعریف می‌شود: فرض کنید که (i,j) یال k -ام گراف باشد، و i ik = ۱ و E jk = −۱، و تمام مقادیر ستون k برابر ۰ است. برای مثال قبل (با n = ۴ و m = ۵) داریم:
E = \begin{bmatrix
1 - 1 - 0 - 0 - 0 \\
-1 - 0 - 1 - 1 - 0 \\
0 - -1 - -1 - 0 - 1 \\
0 - 0 - 0 - -1 - -1 \\
\end{bmatrix.
در نظر داشته باشید که لاپلاس L می‌تواند به حاصل ضرب ماتریس وقوع و ترانهاده‌اش ساده شود، یعنی L = EE T . علاوه بر این، فرض کنید F همان ماتریس E باشد که اولین ردیفش حذف شده باشد، پس داریم FF T = M 11 .
حالا فرمول کوچی - بینت اجازه می‌دهد که بنویسیم:
که محدوده S بین زیرمجموعه‌های m با اندازه n-1 است و F S نشان می‌دهد که ماتریس (n − ۱) در (n − ۱) که ستون‌هایش همان F هستند که در S مرتب شده‌اند. پس هر S با n − ۱ یال از گراف اصلی، و می‌توان نشان داد که آن یال‌ها موجب یک درخت پوشا می‌شوند اگر و تنها اگر دترمینان F S برابر با ۱+ یا ۱- باشد، و موجب یک درخت پوشا نمی‌شوند اگر و تنها اگر دترمینان برابر ۰ شود. اثبات در همین‌جا به پایان می‌رسد.
موارد خاص و تعمیم‌ها
فرمول کیلی
فرمول کیلی از نظریه کیرشهف به عنوان یک حالت خاص تبعیت می‌کند چون هر بردار با طول ۱ در هر مکان، ۱- در مکان دیگر و ۰ در جایی دیگر یک بردار ویژه از ماتریس لاپلاس گراف کامل با مقدار ویژه متناظر با n است. این بردارها با هم دیگر یک فضا به اندازه n − ۱ پوشش می‌دهند که پس هیچ مقدار ویژه غیرصفر دیگری وجود ندارد.
متناوبا، توجه داشته باشید که همان‌طور که فرمول کیلی تعداد درخت‌های نامگذاری شده مجزای یک گراف کامل K n را به دست می‌آورد، ما باید هر هم عامل ماتریس لاپلاس K n را محاسبه کنیم. لاپلاس ماتریس در این مورد برابر است با:
\begin{bmatrix
n-1 - -1 - \cdots - -1 \\
-1 - n-1 - \cdots - -1 \\
\vdots - \vdots- \ddots - \vdots \\
-1 - -1 - \cdots - n-1 \\
\end{bmatrix.
هر هم عامل از ماتریس بالا برابر است با n n −2 . که همان فرمول کیلی است.
نظریه کیرشهف برای گراف‌های چندگانه
نظریه کیرشهف برای گراف‌های چندگانه نیز به خوبی صادق است؛ ماتریس Q به صورت زیر اصلاح شده‌است:
مقدار q i,j برابر با m- است. که m تعداد یال‌های بین i و j است؛
هنگام شمردن درجه یک راس، تمام دورها حذف می‌شوند.
فرمول کیلی برای یک گراف چندگانه کامل برابر با (m n-1 (n n-1 -(n-1)n n-2 است که از روش بالا ساخته شده‌است چون یک گراف ساده یه گراف چندگانه با m = ۱ است.
همچنین بخوانید
پروفر کد
درخت پوشای کمینه
لیست نظریه‌های مرتبط با گراف و درخت