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

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

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

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

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

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

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