موضوع مقاله: همبندی (نظریه گراف) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # همبندی (نظریه گراف) | مقدمه: همبندی یک گراف، یک مقیاس مهم برای سنجش میزانِ کمتر بودن خطاهایش به عنوان یک شبکه است. | ## بخش 1: همبندی (نظریه گراف) | تعریف مؤلفه‌ها، برش‌ها و همبندی در یک گراف بدون جهت ، دو رأس و را متصل می‌نامیم اگر گراف مسیری از به داشته باشد. اگر دو رأس با مسیری به طول یک (یک یال) به هم متصل باشند، رأس‌ها، مجاور(همسایه) نامیده می‌شوند. به یک گراف همبند می‌گوییم، اگر هر دو رأس دلخواه آن (از طریق حداقل یک مسیر) به هم متصل باشند. اگر در یک گراف جهت‌دار، جایگزین کردن تمام یال‌های جهت‌دار با یال‌های بدون جهت منجر به ساخت یک گراف همبند (بدون جهت) شود، در این صورت به این گراف جهت‌دار همبند ضعیف می‌گوییم.به عبارت دیگر این گراف همبند است اگر به ازای هر دو رأس دلخواه و ، مسیری جهت‌دار از به یا از به ، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه و ، مسیری جهت‌دار هم از به و هم از به داشته باشیم. یک برش، رأس برشی، یا مجموعهٔ جداکنندهٔ گراف همبند ، مجموعه‌ای از رئوس است که با حذفشان گراف ناهمبند می‌شود. عدد همبندی یا عدد همبند رأسی که با نشان داده می‌شود (و G در آن گراف کامل نیست) تعداد مینیمال رأس‌های برشی است. یک گراف k-همبند یا k-همبند رأسی نامیده می‌شود اگر تعداد رئوس همبندی آن، حداقل k باشد. این بدین معنی است که گراف را زمانی k-همبند می‌نامیم که در آن، یک مجموعه ی k-1 عضوی از رأس‌هایی که با حذفشان گراف، ناهمبند می‌شود، وجود نداشته باشد. یک گراف کامل با n رأس که با نشان داده می‌شود، هیچ رأس برشی ندارد، ولی بنابر قرارداد داریم . رأس برشی رئوس و مجموعه‌ای از رأس‌ها است که با حذف کردنشان، ارتباط بین و قطع می‌شود. | ## بخش 2: همبندی (نظریه گراف) | عدد همبندی محلی برابر با کمترین تعداد رئوس برشی است که با حذفشان، ارتباط و قطع می‌شود. علاوه بر این به استثنای گراف‌های کامل، به ازای هر دو انتخاب دلخواه از رأس‌های و برابر است با حداقل . به عنوان نمونه، اگر حذف یک یال خاص، آن گراف را ناهمبند کند، در این صورت این یال، پل نامیده می‌شود. به‌طور کلی، یال برشی گراف G مجموعه‌ای از یال‌ها است که حذف آن‌ها، گراف را ناهمبند می‌کند. عدد همبند یالی برابر با اندازهٔ کوچکترین مجموعهٔ یال‌های برشی است و عدد همبند یالی محلی رئوس u و v برابر با اندازه ی کوچکترین یال برشی است که u و v را از هم جدا می‌کند. قضیهٔ منگر یکی از مهمترین قضایا دربارهٔ همبندی در گراف‌ها قضیهٔ منگر است که عدد همبندی و عدد همبند یالی یک گراف را به صورت مسیرهای مستقل بین رئوس مشخص می‌کند. اگر و رأس‌های گراف باشند، آنگاه مجموعه‌ای از مسیرها بین و را مستقل می‌نامیم، اگر هیچ دوتایی از آن‌ها، رأس مشترک نداشته باشند (به جز رأس‌های u و v). به‌طور مشابه، یک مجموعه، یال-مستقل است، اگر هیچ دو مسیری از آن، یال مشترک نداشته باشند. تعداد مسیرهای دو به دو مستقل بین و به صورت و تعداد مسیرهای دو به دو یال-مستقل بین u و v به صورت نوشته می‌شوند. قضیهٔ منگر ادعا می‌کند که عدد همبندی محلی با برابر است و عدد همبندی یالی محلی با به ازای هر انتخاب دلخواه از رأس‌های u و v برابر است. | ## بخش 3: همبندی (نظریه گراف) | جنبه‌های محاسباتی مسئلهٔ تعیین اینکه آیا در یک گراف، دو رأس به هم متصل هستند یا نه، می‌تواند به صورت مؤثر با استفاده از الگوریتم سرچ، مثل جستجوی اول سطح، حل شود. به‌طور کلی، تعیین محاسباتی اینکه آیا یک گراف همبند است،(برای مثال با استفاده از مجموعه‌های مجزا در ساختمان داده)، یا شمارش تعداد مؤلفه‌های همبندی گراف آسان است. از این رأس با استفاده از جستجوی اول سطح یا جستجوی عمق اول، شروع به حرکت کن و تمام رأس‌هایی که به آن دسترسی پیدا کردی را بشمار. هر وقت گراف به‌طور کامل پیمایش شد، اگر تعداد رأس‌های شمرده شده برابر با تعداد رأس‌های گراف باشد، گراف همبند است، در غیر این صورت گراف ناهمبند است. با استفاده از قضیهٔ منگر، برای هر دو رأس دلخواه u و v در یک گراف همبند ، مقادیر و می‌توانند توسط الگوریتم جریان بیشینه - برش کمین تعیین شوند. در این صورت عدد همبندی و عدد همبند یالی گراف به ترتیب برابر با کمینه مقادیر و خواهند بود. مسئلهٔ محاسبهٔ احتمال اینکه یک گراف تصادفی، همبند باشد، اعتبار شبکه نامیده می‌شود. هردوی آن‌ها، از کمترین درجهٔ گراف، کوچکتر هستند، چون حذف کردن همهٔ رئوس مجاور یک رأس با کمترین درجه، ارتباط این رأس را با گراف قطع می‌کند. گراف G 2-همبند یالی است، اگر و تنها اگر یال‌های جهت داری داشته باشد که مجموعهٔ آن یال‌ها، قویاً همبند باشد. | ## جمع‌بندی | Dirac اگر یک گراف به ازای kهای بزرگتر مساوی 2، k-همبند باشد، آنگاه برای هر مجموعهٔ k رأسی در گراف، دوری وجود دارد که از همهٔ رئوس این مجموعه می‌گذرد.