1-ماتریس لاپلاسین

توسط علی رضا نقش نیلچی | یکشنبه نهم شهریور ۱۴۰۴ | 0:8

از ویکی‌پدیا، دانشنامه آزاد

در حوزه ریاضی نظریه گراف ، ماتریس لاپلاسین که به آن لاپلاسین گراف ، ماتریس ادمیتانس ، ماتریس کیرشهف یا لاپلاسین گسسته نیز گفته می‌شود ، نمایش ماتریسی از یک گراف است . این ماتریس که به نام پیر-سیمون لاپلاس نامگذاری شده است ، می‌تواند به عنوان فرم ماتریسی از عملگر لاپلاس گسسته منفی روی گرافی که لاپلاسین پیوسته منفی به دست آمده با روش تفاضل محدود را تقریب می‌زند، در نظر گرفته شود .

ماتریس لاپلاسین به بسیاری از ویژگی‌های تابعی گراف مربوط می‌شود. از قضیه کیرشهف می‌توان برای محاسبه تعداد درخت‌های پوشا برای یک گراف مشخص استفاده کرد. پراکنده‌ترین برش یک گراف را می‌توان از طریق بردار فیدلر - بردار ویژه مربوط به دومین کوچکترین مقدار ویژه لاپلاسین گراف - همانطور که توسط نابرابری چیگر ثابت شده است، تقریب زد . تجزیه طیفی ماتریس لاپلاسین امکان ساخت جاسازی‌های کم‌بعد را فراهم می‌کند که در بسیاری از کاربردهای یادگیری ماشین ظاهر می‌شوند و یک طرح طیفی را در ترسیم گراف تعیین می‌کنند . پردازش سیگنال مبتنی بر گراف بر اساس تبدیل فوریه گراف است که تبدیل فوریه گسسته سنتی را با جایگزینی پایه استاندارد سینوسی‌های مختلط برای بردارهای ویژه ماتریس لاپلاسین یک گراف مربوط به سیگنال، گسترش می‌دهد.

ماتریس لاپلاسین ساده‌ترین تعریف برای یک گراف ساده است ، اما در کاربردهایی برای یک گراف با وزن لبه‌ای ، یعنی با وزن‌هایی روی لبه‌های آن - ورودی‌های ماتریس مجاورت گراف - رایج‌تر است . نظریه گراف طیفی، ویژگی‌های یک گراف را به یک طیف، یعنی مقادیر ویژه و بردارهای ویژه ماتریس‌های مرتبط با گراف، مانند ماتریس مجاورت یا ماتریس لاپلاسین آن، مرتبط می‌کند. وزن‌های نامتعادل ممکن است به طور نامطلوبی بر طیف ماتریس تأثیر بگذارند و منجر به نیاز به نرمال‌سازی - مقیاس‌بندی ستون/ردیف ورودی‌های ماتریس - شوند که منجر به ماتریس‌های مجاورت و لاپلاسین نرمال‌شده می‌شود.

تعاریف برای گراف‌های ساده

[ ویرایش ]

ماتریس لاپلاسین

[ ویرایش ]

با توجه به یک گراف ساده $G$ $n$ رأس‌ها $v_{1},\ldots,v_{n}$ ، ماتریس لاپلاسین ${\textstyle L_{n\times n}}$ به صورت عنصر به عنصر به صورت [ 1 ] تعریف می‌شود.

مجاور است و0در غیر این صورت، ${\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ مجاور }}v_{j}\\0&{\mbox{otherwise}},\end{cases}}}} است.$

یا به طور معادل توسط ماتریس

$L=DA,$

که در آن D ماتریس درجه و A ماتریس مجاورت گراف است . از آنجایی که ${\textstyle G}$ یک گراف ساده است، ${\textstyle A}$ فقط شامل ۱ یا ۰ است و عناصر قطری آن همگی ۰ هستند.

در اینجا یک مثال ساده از یک گراف بدون جهت و برچسب‌گذاری شده و ماتریس لاپلاسین آن آورده شده است.

گراف برچسب‌گذاری شده	ماتریس درجه	ماتریس مجاورت	ماتریس لاپلاسین
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0\\0&0&1&0&1&0\\0&0&1&0&1\\1&1&0&1&0\\0&0&0&1&0\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\\-1&-1&0&-1&3&-1&\\0&0&0&-1&0&\\end{array}}\right)}$

برای گراف بدون جهت مشاهده می‌کنیم که هم ماتریس مجاورت و هم ماتریس لاپلاسین متقارن هستند و مجموع سطرها و ستون‌های ماتریس لاپلاسین همگی صفر هستند (که مستقیماً نشان می‌دهد که ماتریس لاپلاسین منفرد است).

برای گراف‌های جهت‌دار ، بسته به کاربرد، می‌توان از درجه ورودی یا درجه خروجی استفاده کرد، مانند مثال زیر:

گراف برچسب‌گذاری شده	ماتریس مجاورت	ماتریس درجه خروجی	لاپلاسین خارج از درجه	ماتریس درجه ورودی	لاپلاسین درون درجه‌ای
	${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&-1&-1\\0&1&-1\\-1&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&0&0\\0&1&0\\0&0&2\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}1&-1&-1\\0&1&-1\\-1&0&2\\\end{array}}\right)}$

در گراف جهت‌دار، ماتریس مجاورت و ماتریس لاپلاسین نامتقارن هستند. در ماتریس لاپلاسین آن، مجموع ستون‌ها یا مجموع سطرها صفر است، بسته به اینکه از درجه ورودی یا درجه خروجی استفاده شده باشد.

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی