پرش به محتویات

قضیه کیرشهف. پیدا کردن تعداد درخت‌های پوشا

مسئله: یک گراف همبند بدون جهت (با امکان وجود یال‌های چندگانه) با استفاده از ماتریس مجاورت به شما داده شده است. تعداد درخت‌های پوشای مختلف این گراف را پیدا کنید.

فرمول زیر توسط کیرشهف در سال ۱۸۴۷ اثبات شد.

قضیه ماتریس-درخت کیرشهف

فرض کنید $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)$ پیدا کرد.

اثبات این قضیه بسیار دشوار است و در اینجا ارائه نمی‌شود؛ برای طرح کلی اثبات و نسخه‌های دیگر این قضیه برای گراف‌های بدون یال چندگانه و گراف‌های جهت‌دار به ویکی‌پدیا مراجعه کنید.

ارتباط با قوانین مداری کیرشهف

قضیه ماتریس-درخت کیرشهف و قوانین کیرشهف برای مدارهای الکتریکی به شکل زیبایی با هم مرتبط هستند. می‌توان نشان داد (با استفاده از قانون اهم و قانون اول کیرشهف) که مقاومت $R_{ij}$ بین دو نقطه $i$ و $j$ از مدار برابر است با:

$$R_{ij} = \frac{ \left| L^{(i,j)} \right| }{ | L^j | }.$$

در اینجا ماتریس $L$ از ماتریس معکوس مقاومت‌ها $A$ (که $A_{i,j}$ معکوس مقاومت رسانای بین نقاط $i$ و $j$ است) با استفاده از روشی که در قضیه ماتریس-درخت کیرشهف توضیح داده شد، به دست می‌آید. $L^j$ ماتریسی است که سطر و ستون $j$ از آن حذف شده، و $L^{(i,j)}$ ماتریسی است که دو سطر و دو ستون $i$ و $j$ از آن حذف شده‌اند.

قضیه کیرشهف به این فرمول معنای هندسی می‌دهد.

مسائل تمرینی