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

 

فهرست

تعریف [ ویرایش ]

ماتریس لاپلاس برای نمودارهای ساده [ ویرایش ]

با یک گراف سادهG باn رئوس ، ماتریس لاپلاسی آن است {\ متن سبک L_ {n \ بار n}}به این صورت تعریف می شود: [1]

{\ displaystyle L = DA ،}

که در آن D است ماتریس درجه و است ماتریس مجاورت گراف. از آنجا که{\ متن سبک G} یک نمودار ساده است ، {\ متن سبک A} فقط شامل 1s یا 0s است و عناصر مورب آن همه 0s هستند.

در مورد نمودار کارگردانی ، یا indegree یا outdegree ممکن است مورد استفاده قرار گیرد، بسته به نرم افزار است.

عناصر {\ متن سبک L}{\ متن سبک L} داده شده توسط

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

جایی که {\ displaystyle \ operatorname {deg} (v_ {i})} درجه راس است من.

لاپلاسی نرمال متقارن [ ویرایش ]

ماتریس لاپلاسی نرمال متقارن به این صورت تعریف می شود: [1]

{\ displaystyle L ^ {\ text {sym}}: = D ^ {- {\ frac {1} {2}}} LD ^ {- {\ frac {1} {2}}} = شناسه ^ {- { \ frac {1} {2}}} AD ^ {- {\ frac {1} {2}}}}،

عناصر {\ textstyle L ^ {\ text {sym}}} داده شده توسط

{\ displaystyle L_ {i، j} ^ {\ text {sym}}: = {\ begin {موارد} 1 & {\ mbox {if}} i = j {\ mbox {و}} \ deg (v_ {i} ) \ neq 0 \\ - {\ frac {1} {\ sqrt {\ deg (v_ {i}) \ deg (v_ {j})}}}} و {\ mbox {if}} i \ neq j {\ mbox {و}} v_ {i} {\ mbox {مجاور}} v_ {j} \\ 0 & {\ mbox {در غیر این صورت}} است. \ end {موارد}}}

پیاده روی تصادفی لاپلاسی نرمال شده [ ویرایش ]

ماتریس نرمال لاپلاسی با راه رفتن تصادفی به این صورت تعریف می شود:

{\ displaystyle L ^ {\ text {rw}}: = D ^ {- 1} L = ID ^ {- 1} A}

عناصر {\ textstyle L ^ {\ text {rw}}} داده شده توسط

{\ displaystyle L_ {i، j} ^ {\ text {rw}}: = {\ begin {موارد} 1 & {\ mbox {if}} i = j {\ mbox {و}} \ deg (v_ {i} ) \ neq 0 \\ - {\ frac {1} {\ deg (v_ {i})}}} و {\ mbox {if}} i \ neq j {\ mbox {and}} v_ {i} {\ mbox {در مجاورت}} v_ {j} \\ 0 & {\ mbox {در غیر این صورت}} است. \ پایان {موارد}}}

لاپلاسی تعمیم یافته [ ویرایش ]

لاپلاسی تعمیم یافته سبه این صورت تعریف می شود: [2]

{\ displaystyle {\ begin {موارد} Q_ {i ، j} <0 & {\ mbox {if}} i \ neq j {\ mbox {و}} v_ {i} {\ mbox {مجاور}} v_ { j} \\ Q_ {i، j} = 0 & {\ mbox {if}} i \ neq j {\ mbox {and}} v_ {i} {\ mbox {مجاور}} v_ {j} \\ نیست {\ mbox {هر تعداد}} و {\ mbox {در غیر این صورت}}. \ end {موارد}}}

توجه کنید که لاپلاسیای معمولی یک لاپلاسیا تعمیم یافته است.

منبع

https://en.wikipedia.org/wiki/Laplacian_matrix