بلاگ

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

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


Cut graph theory

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

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

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

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

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

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

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

پست های مرتبط

وبینار تقسیم بندی قابل قبول تصاویر پزشکی با استفاده از برچسب های فشرده تا ساختارهای گرافی

تاریخ: 1400/08/09

بازدید: 854

1400

زمان مطالعه: 5 دقیقه دقیقه

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

مدرس

@ins

یک ریختی گراف چیست

تاریخ: 1399/11/02

بازدید: 2206

1399

زمان مطالعه: 5 دقیقه دقیقه

تابع دوسویی (bijection) چیست؟

مدرس

@ins

گراف کامل چیست

تاریخ: 1399/11/11

بازدید: 2369

1399

زمان مطالعه: 5 دقیقه دقیقه

تعریف گراف کامل

مدرس

@ins

Graph Attention Network (GAT) چیست؟

تاریخ: 1400/11/19

بازدید: 577

1400

زمان مطالعه: 5 دقیقه دقیقه

یادگیری ماشین یکی از روش های تحلیل داده است که به ساخت مدل های تحلیلی خودکار می پردازد .

مدرس

@ins