دسته بندی موضوعات آموزشی

عنوان اصلی ۱
title 2

محتوای دسته بندی دوره های آموزشی

  • subtitle 1.1
  • subtotle 1.2
  • 11
  • 12

جستجو در بین هـــزاران ساعت آمـــــوزش

پایگــــــاه اطلاعات علمـــــــی جهــــــــاد دانشگاهی

مفهوم برش در گراف

تاریخ: 1399/10/28

بازدید: 1537

 | 


Cut graph theory

یک گراف متصل، به گرافی گفته می‌شود که میان هر جفت گره آن مسیری وجود داشته باشد. عمل برش در گراف به عملیاتی گفته می‌شود که طی آن گراف به دو قسمت تقسیم می شود (دو مجموعه غیرتهی از گره‌ها). به مجموعه یال‌هایی که یک سر آن‌ها در قسمت اول و سر دیگر آن‌ها در قسمت دیگر است، مجموعه برش می‌گویند. در واقع حذف مجموعه برش سبب انفصال گراف خواهد شد. گرافی با n گره، n2 برش دارد. این عدد در واقع جمع انتخاب‌های 1 تا n از n گره به عنوان اندازه مجموعه اول است. به صورت دیگر در انتخاب قسمت برای هر گره دو انتخاب وجود دارد، بنابراین در کل به عدد ذکر شده، حالت خواهیم داشت.

برای دریافت آخرین‌های بلاگ و کارگاه‌های مرکز اطلاعات علمی در خبرنامه عضو شوید.

یال برش (پل): یالی است که حذف آن گراف را به یک گراف منفصل می‌کند. در شکل زیر یال‌های سرمه‌ای پل هستند.

مفهوم برش در گراف

گره برش: گره‌ای که حذف آن گراف را منفصل کند.

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

مباحث پيشرفته يادگيري عميق؛ Graph Convolution Network (GCN)