المپدیا

در ریاضیات و علوم کامپیوتر، راس برشی (به انگلیسی: Cut Vertex یا Articulation Point) راسی از گراف است که حذف آن باعث افزایش تعداد مولفه‌های همبندی گراف می شود. اگر گراف قبل از حذف آن راس همبند باشد، بعد از حذف ناهمبند می شود. راس برشی در شبکه‌های کامپیوتری (به عنوان گره) اهمیت ویژه ای دارد.

به طور کلی یک گراف غیر جهت دار همبند با n راس، حداکثر n - 2 راس برشی دارد (حالت زنجیر مانند که دقیقا n - 2 راس برشی دارد).

طبیعتا ممکن است گرافی راس برشی نداشته باشد.

رئوسی که دارای راس مجاوری از درجهٔ 1 باشند برشی هستند (بجز در گراف با 2 راس).

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

در نظریهٔ گراف، یال برشی (به انگلیسی: 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 است که به تناقض می رسیم.