یال برشی
در نظریهٔ گراف، یال برشی (به انگلیسی: Bridge یا Cut edge) یالی از گراف است که حذف آن باعث افزایش تعداد مولفه های همبندی گراف می شود. اگر گراف قبل از حذف آن یال همبند باشد، بعد از حذف ناهمبند می شود. یال برشی در شبکههای کامپیوتری اهمیت ویژه ای دارد چرا که حذف آن کلا اتصال شبکه را مختل می کند.
یالی از گراف برشی است اگر و فقط اگر در هیچ دوری قرار نگرفته باشد.
طبیعتا ممکن است گرافی یال برشی نداشته باشد. راس برشی نیز مشابه یال برشی است، به طوری که حذف آن باعث افزایش تعداد مولفههای همبندی گراف می شود.
هر یال برشی حداقل یکی از راس هایش برشی است.(جز در حالات خاصی که یال حذف شده باعث ایجاد مولفه ای با یک راس می شود(در این حالات امکان دارد همچین چیزی رخ ندهد. مثلن اگر گراف فقط یک یال باشد))
همهٔ یالهای درخت برشی هستند.
محتویات |
حدس پوشش مضاعف دور ها [ویرایش]
یک مسالهٔ باز که یالهای برشی را نیز شامل میشود مسالهٔ پوشش مضاعف دورها، بوسیلهٔ جرج زکارس و پل سیمور (در سالهای 1978 و 1979، مستقل از هم) است که بیان میکند هر گراف فاقد یال برشی دور هایی دارد که هر یال را دقیقا دو بار در بر می گیرند.
اثبات یک قضیه [ویرایش]
یالی از گراف برشی است اگر و فقط اگر در هیچ دوری قرار نگرفته باشد.
اثبات با برهان خلف: فرض کنید 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) = 1 و Num(B) = 2 است.
- هر راس v که (Num(v) = Low(v به همراه پدرش یک یال برشی را تشکیل می دهند.
در گراف بالا Num(G) = Low(G) = 7 پس GC (تنها) یال برشی است.در درخت دور وجود ندارد.
پیوند به بیرون [ویرایش]
مطالعهٔ بیشتر [ویرایش]
- 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}
منابع [ویرایش]
- http://www.cse.ohio-state.edu/~lai/780/graph.pdf
- http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/mst.pdf
- http://algorithmics.comp.nus.edu.sg/wiki/_media/training/graph.ppt?id=training%3Aicpc_workshop_2006&cache=cache
- مشارکتکنندگان ویکیپدیا، «Bridge»، ویکیپدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).
