همبندی (نظریه گراف)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات و علوم کامپیوتر، همبندی (به انگلیسی: Connectivity) یکی از مفاهیم اولیه‌ی نظریه‌ی گراف است: همبندی به دنبال حداقل تعداد رأس‌ها یا یال‌هایی است که با حذفشان، ارتباط رأس‌های باقی‌مانده از بین برود.[۱] این مبحث تا حد زیادی به مسئله‌های شبکه شاره مربوط است. همبندی یک گراف، یک مقیاس مهم برای سنجش میزان کمتر بودن خطاهایش به عنوان یک شبکه است.

تعریف مؤلفه‌ها، برش‌ها و همبندی[ویرایش]

در یک گراف بدون جهت G، دو رأس u و v را متصل می‌نامیم اگر گراف G مسیری از u به v داشته باشد. در غیر این صورت، آنها غیرمتصل نامیده می‌شوند. اگر دو رأس با مسیری به طول یک (یک یال) به هم متصل باشند، رأس‌ها، مجاور(همسایه) نامیده می‌شوند. به یک گراف همبند می‌گوییم، اگر هر دو رأس دلخواه آن (از طریق حداقل یک مسیر) به هم متصل باشند. یک مؤلفه‌ی همبندی یک زیرگراف همبند ماکسیمال از G است. هر رأس و یالی به یک مؤلفه‌ی همبندی مربوط است.

اگر در یک گراف جهت‌دار، جایگزین کردن تمام یال‌های جهت‌دار با یال‌های بدون جهت منجر به ساخت یک گراف همبند (بدون جهت) شود، در این صورت به این گراف جهت‌دار همبند ضعیف می‌گوییم.به عبارت دیگر این گراف همبند است اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار از u به v یا از v به u، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار هم از u به v و هم از v به u داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.

یک برش، رأس برشی، یا مجموعه‌ی جداکننده‌ی گراف همبند G، مجموعه‌ای از رئوس است که با حذفشان گراف G ناهمبند می‌شود. عدد همبندی یا عدد همبند رأسی که با \kappa(G) نشان داده می‌شود (و G در آن گراف کامل نیست) تعداد مینیمال رأس‌های برشی است. یک گراف k-همبند یا k-همبند رأسی نامیده می‌شود اگر تعداد رئوس همبندی آن، حداقل k باشد. این بدین معنی است که گراف G را زمانی k-همبند می‌نامیم که در آن، یک مجموعه ی k-1 عضوی از رأس هایی که با حذفشان گراف، ناهمبند می‌شود، وجود نداشته باشد. یک گراف کامل با n رأس که با K_n نشان داده می‌شود، هیچ رأس برشی ندارد، ولی بنابر قرارداد داریم \kappa(K_n) = n - 1. رأس برشی رئوس u و v مجموعه‌ای از رأس‌ها است که با حذف کردنشان، ارتباط بین u و v قطع می‌شود. عدد همبندی محلی \kappa(u,v) برابر با کمترین تعداد رئوس برشی است که با حذفشان، ارتباط u و v قطع می‌شود. همبندی محلی برای گراف‌های بدون جهت، متقارن است \kappa(u,v) = \kappa(v,u). علاوه بر این به استثنای گراف‌های کامل، \kappa(G) به ازای هر دوانتخاب دلخواه از رأس‌های u و v برابر است با حداقل \kappa(u,v).

گراف دوهمبند (به انگلیسی: biconnectivity) مثالی از گراف k-همبند است.

مفاهیم مشابهی را می‌توان برای یال‌ها تعریف کرد. به عنوان نمونه، اگر حذف یک یال خاص، آن گراف را ناهمبند کند، در این صورت این یال، پل نامیده می‌شود. به طور کلی، یال برشی گراف G مجموعه‌ای از یال‌ها است که حذف آن‌ها، گراف را ناهمبند می‌کند. عدد همبند یالی \lambda(G) برابر با اندازه‌ی کوچکترین مجموعه‌ی یال‌های برشی است و عدد همبند یالی محلی \lambda(u,v) رئوس u و v برابر با اندازه ی کوچکترین یال برشی است که u و v را از هم جدا می‌کند. همبند یالی محلی متقارن است. یک گراف k-همبند یالی نامیده می‌شود، اگرعدد همبندی یالی آن حداقل k باشد.

قضیه‌ی منگر[ویرایش]

یکی از مهمترین قضایا درباره‌ی همبندی در گراف‌ها قضیه‌ی منگر (به انگلیسی: Menger's theorem) است که عدد همبندی و عدد همبند یالی یک گراف را به صورت مسیرهای مستقل بین رئوس مشخص می‌کند. اگر u و v رأس های گراف G باشند، آنگاه مجموعه‌ای از مسیرها بین u و v را مستقل می‌نامیم، اگر هیچ دوتایی از آن‌ها، رأس مشترک نداشته باشند (به جز رأس های u و v). به طور مشابه، یک مجموعه، یال-مستقل است، اگر هیچ دو مسیری از آن، یال مشترک نداشته باشند. تعداد مسیرهای دو به دو مستقل بین u و v به صورت \kappa\prime(u,v) و تعداد مسیرهای دو به دو یال-مستقل بین u و v به صورت \lambda(u,v) نوشته می‌شوند.
قضیه‌ی منگر ادعا می‌کند که عدد همبندی محلی \kappa(u,v) با \kappa\prime(u,v) برابر است و عدد همبندی یالی محلی \lambda(u,v) با \lambda\prime(u,v) به ازای هر انتخاب دلخواه از رأس‌های u و v برابر است.[۲][۳] این قضیه، یک حالت خاص از قضیه‌ی جریان بیشینه - برش کمینه است.

جنبه‌های محاسباتی[ویرایش]

مسئله‌ی تعیین اینکه آیا در یک گراف، دو رأس به هم متصل هستند یا نه، می‌تواند به صورت مؤثر با استفاده از الگوریتم سرچ، مثل جستجوی اول سطح، حل شود. به طور کلی، تعیین محساباتی اینکه آیا یک گراف همبند است،(برای مثال با استفاده از مجموعه‌های مجزا در ساختمان داده)، یا شمارش تعداد مؤلفه‌های همبندی گراف آسان است. یک الگوریتم ساده به صورت شبه کد به صورت زیر است:

  1. از یک رأس دلخواه گراف G شروع کن.
  2. از این رأس با استفاده از جستجوی اول سطح یا جستجوی عمق اول، شروع به حرکت کن و تمام رأس‌هایی که به آن دسترسی پیدا کردی را بشمار.
  3. هر وقت گراف به طور کامل پیمایش شد، اگر تعداد رأس‌های شمرده شده برابر با تعداد رأس‌های گراف G باشد، گراف همبند است، در غیر این صورت گراف ناهمبند است.

با استفاده از قضیه‌ی منگر، برای هر دو رأس دلخواه u و v در یک گراف همبند G، مقادیر \kappa(u,v) و \lambda(u,v) می‌توانند توسط الگوریتم جریان بیشینه - برش کمین تعیین شوند. در این صورت عدد همبندی و عدد همبند یالی گراف G به ترتیب برابر با کمینه مقادیر \kappa(u,v) و \lambda(u,v) خواهند بود.
همبندی گراف‌های بدون جهت، در مرتبه‌ی O(\log n) قابل حل است. مسئله‌ی محسابه‌ی احتمال اینکه یک گراف تصادفی، همبند باشد، اعتبار شبکه(به انگلیسی: Network reliability) نامیده می‌شود. همچنین مسئله‌ی محاسبه‌ی اینکه آیا دو رأس داده شده، متصل هستند، ST-reliability problem نامیده می‌شود. هر دوی این مسائل sharp-P]] Hard]] هستند.

مثال‌ها[ویرایش]

  • عدد همبند رأسی و عدد همبند یالی یک گراف ناهمبند هر دو برابر صفر هستند.
  • 1-همبند با همبند بودن هم معنی است.
  • یک گراف کامل با n رأس دارای عدد همبند یالی برابر با N-1 هست. هر گراف ساده ی دیگر n رأسی، عدد همبند یالی کمتری دارد.
  • در یک درخت، عدد همبند یالی محلی بین هر دو جفت از رأس ها برابر با 1 است.

کران‌های همبندی[ویرایش]

  • عدد همبند رأسی یک گراف، کوچکتر یا مساوی عدد همبند یالی‌اش است \kappa(G) <\lambda(G). هردوی آن‌ها، از کمترین درجه‌ی گراف، کوچکتر هستند، چون حذف کردن همه‌ی رئوس مجاور یک رأس با کمترین درجه، ارتباط این رأس را با گراف قطع می‌کند.

ویژگی‌های دیگر[ویرایش]

  • اگر G همبند باشد آنگاه گراف خطی L(G) همبند است.
  • گراف G 2-همبند یالی است، اگر و تنها اگر یال‌های جهت داری داشته باشد که مجموعه‌ی آن یال‌ها، قویاً همبند باشد.
  • بنابر یکی از قضایای G. A. Dirac اگر یک گراف به ازای k های بزرگتر مساوی 2، k-همبند باشد، آنگاه برای هر مجموعه‌ی k رأسی در گراف، دوری وجود دارد که از همه‌ی رئوس این مجموعه می‌گذرد.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. Diestel, R., Graph Theory, Electronic Edition, 2005, p 12.
  2. Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. 
  3. Nagamochi, H., Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.