پل (نظریه گراف)

ِگرافی با ۶ یال برشی (قرمز)

گراف غیر جهت دار فاقد یال برشی

در نظریهٔ گراف، یال برشی (به انگلیسی: Bridge یا Cut edge) یالی از گراف است که حذف آن باعث افزایش تعداد مولفه‌های همبندی گراف می‌شود. اگر گراف قبل از حذف آن یال همبند باشد، بعد از حذف ناهمبند می‌شود. یال برشی در شبکه‌های کامپیوتری اهمیت ویژه‌ای دارد چرا که حذف آن کلا اتصال شبکه را مختل می‌کند.

یالی از گراف برشی است اگر و فقط اگر در هیچ دوری قرار نگرفته باشد.

طبیعتاً ممکن است گرافی یال برشی نداشته باشد. راس برشی نیز مشابه یال برشی است، به‌طوری‌که حذف آن باعث افزایش تعداد مؤلفه‌های همبندی گراف می‌شود.

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

همهٔ یال‌های درخت برشی هستند.

حدس پوشش مضاعف دورها

یک مسئلهٔ باز که یال‌های برشی را نیز شامل می‌شود مسئلهٔ پوشش مضاعف دورها، بوسیلهٔ جرج زکارس و پل سیمور (در سال‌های ۱۹۷۸ و ۱۹۷۹، مستقل از هم) است که بیان می‌کند هر گراف فاقد یال برشی دورهایی دارد که هر یال را دقیقاً دو بار در بر می‌گیرند.

اثبات یک قضیه

یالی از گراف برشی است اگر و فقط اگر در هیچ دوری قرار نگرفته باشد.

اثبات با برهان خلف: فرض کنید e = uv یال برشی از گراف همبند G است و e در دور C شامل u,v،w، …x,u قرار گرفته‌است. گراف G – e دارای یک مسیر u-v به شکل u,x، …،w,v است، یعنی u به v متصل است. حال a و b را دو راس دلخواه از G – e در نظر می‌گیریم و نشان می‌دهیم که G – e مسیری از a به b دارد. چون G همبند بود پس مسیر a-b مانند P در G یافت می‌شود. اگر یال e در آن مسیر قرار نداشته باشد مسلماً باز هم همان مسیر P در G – e نیز وجود دارد و a به b در G – e راه دارد. فرض کنید e در مسیر P قرار دارد؛ بنابراین P را می‌توان به صورت a، …،u,v، …،b یا a، …،v,u، …،b نشان داد. قبلاً ثابت کردیم در G – e، از v به u مسیر وجود دارد؛ بنابراین اگر e در دوری قرار گرفته باشد، با حذف آن هنوز هم بین هر دو راس دلخواه a و b از G – e مسیر وجود دارد که یعنی e یال برشی نیست. پس به تناقض رسیدیم.

برعکس فرض کنید e = uv یالی است که در هیچ دوری قرار نگرفته‌است. دوباره با برهان خلف فرض کنید e یال برشی نیست. پس G – e همبند است و مسیری مثل P از u به v در G – e وجود دارد. در این صورت P باضافه e دوری در G ایجاد می‌کند که شامل e است که به تناقض می‌رسیم.

تعیین یال‌های برشی

برای گراف روبرو با مراجعه به روش‌های یافتن راس برشی گراف پیمایش شدهٔ زیر را بدست می‌آوریم که B 2/1 به معنای Low(B) = ۱ و Num(B) = ۲ است.

• هر راس v که (Num(v) = Low(v به همراه پدرش یک یال برشی را تشکیل می‌دهند.

در گراف بالا Num(G) = Low(G) = ۷ پس GC (تنها) یال برشی است. در درخت دور وجود ندارد.

گراف‌های بدون پل

گراف‌هایی که هیچ پلی ندارند را بدون پل می‌نامند. حالت معادل گراف بدون پل وقتی است که اجزای متصل گراف دارای یک تجزیه گوشی باز باشند و هر جزء دارای درجه دو (دو اتصال) باشد.

پیوند به بیرون

• توضیح و مثال‌هایی از یال و راس برشی
• مباحث نظریهٔ گراف
• یال برشی در سایت wolfram

مطالعهٔ بیشتر

• An Optimal Distributed Bridge-Finding Algorithm, David Pritchard, Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada
• Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs, Hon-Chan Chen, Department of Information Management, National Chin-Yi Institute of Technology, Taichung, Taiwan
• R. E. Tarjan. A note on finding the bridges of a graph. Inform. Process. Lett. , 2:160{161, 1974}

منابع

• https://web.archive.org/web/20100714010430/http://www.cse.ohio-state.edu/~lai/780/graph.pdf
• http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/mst.pdf بایگانی‌شده در ۲۷ ژوئن ۲۰۱۰ توسط Wayback Machine
• http://algorithmics.comp.nus.edu.sg/wiki/_media/training/graph.ppt?id=training:icpc_workshop_2006&cache=cache بایگانی‌شده در ۲۲ آوریل ۲۰۰۸ توسط Wayback Machine
• مشارکت‌کنندگان ویکی‌پدیا. «Bridge». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ می ۲۰۱۱.