در ریاضیات و علوم کامپیوتر، راس برشی ( به انگلیسی: Cut Vertex یا Articulation Point ) راسی از گراف است که حذف آن باعث افزایش تعداد مولفه های همبندی گراف می شود. اگر گراف قبل از حذف آن راس همبند باشد، بعد از حذف ناهمبند می شود. راس برشی در شبکه های کامپیوتری ( به عنوان گره ) اهمیت ویژه ای دارد.
به طور کلی یک گراف غیر جهت دار همبند با n راس، حداکثر n - 2 راس برشی دارد ( حالت زنجیر مانند که دقیقا n - 2 راس برشی دارد ) .
طبیعتا ممکن است گرافی راس برشی نداشته باشد.
رئوسی که دارای راس مجاوری از درجهٔ 1 باشند برشی هستند ( بجز در گراف با 2 راس ) .
یال برشی نیز مشابه راس برشی است، به طوری که حذف آن باعث افزایش تعداد مؤلفه های همبندی گراف می شود.
یک الگوریتم بدیهی از مرتبهٔ ( | O ( | V | . | E :
1 C = empty set ( at the end of the algorithm it will contain the cut vertices ) 2 a = number of components in G ( found using DFS/BFS ) 3 for each i in V with incident edges 4 b = number of components in G with i removed 5 if b> a 6 i is a cut vertex 7 C = C + {i} 8 endif 9 endfor
این راه حل از مرتبهٔ ( | O ( | V | + | E می باشد ( برای گراف همبند ) . بدیهتا در صورتی که گراف ناهمبند باشد الگوریتم را برای تک تک مؤلفه ها جداگانه به کار می بریم.
نخست با شروع از یک راس دلخواه، الگوریتم Depth - first search ( جستجوی اول عمق ) را اعمال می کنیم. از آنجا که ترتیب پیمایش در اینجا مهم است، برای یال های درخت حاصل از جستجو جهت تعیین می کنیم. در هنگام اعمال الگوریتم اگر به راسی رسیدیم که قبلاً ملاقات شده از یال جهت دار نقطه چین شده استفاده می کنیم ( به آن ها یال برگشت - Back Edge - می گوییم ) .
با رسیدن به هر راس، آن را شماره گذاری کنید ( شماره هر راس = ( Num ( v ) ، برای هر راس، ( Low ( v را به صورت زیر تعریف می کنیم:
Low ( v ) = min{ Num ( v ) ( Rule 1 ) , lowest Num ( w ) among all back edges ( v, w ) ( Rule 2 ) , lowest Low ( w ) among all tree edges ( v, w ) ( Rule 3 ) } توجه کنید که ( Low ( v از سه مقدار ممکن کمترین را به خود اختصاص می دهد.
برای گراف سادهٔ زیر با شروع از راس A درخت جستجوی ذیل بدست می آید:
کلید: B 2/1 نشان دهندهٔ Low ( B ) = 1 و Num ( B ) = 2 است. همان طور که در تعریف ( Low ( v آمد برای هر راس با توجه به اینکه کدام یک از سه شرط کمینه است ( Low ( v را تعیین می کنیم.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبه طور کلی یک گراف غیر جهت دار همبند با n راس، حداکثر n - 2 راس برشی دارد ( حالت زنجیر مانند که دقیقا n - 2 راس برشی دارد ) .
طبیعتا ممکن است گرافی راس برشی نداشته باشد.
رئوسی که دارای راس مجاوری از درجهٔ 1 باشند برشی هستند ( بجز در گراف با 2 راس ) .
یال برشی نیز مشابه راس برشی است، به طوری که حذف آن باعث افزایش تعداد مؤلفه های همبندی گراف می شود.
یک الگوریتم بدیهی از مرتبهٔ ( | O ( | V | . | E :
1 C = empty set ( at the end of the algorithm it will contain the cut vertices ) 2 a = number of components in G ( found using DFS/BFS ) 3 for each i in V with incident edges 4 b = number of components in G with i removed 5 if b> a 6 i is a cut vertex 7 C = C + {i} 8 endif 9 endfor
این راه حل از مرتبهٔ ( | O ( | V | + | E می باشد ( برای گراف همبند ) . بدیهتا در صورتی که گراف ناهمبند باشد الگوریتم را برای تک تک مؤلفه ها جداگانه به کار می بریم.
نخست با شروع از یک راس دلخواه، الگوریتم Depth - first search ( جستجوی اول عمق ) را اعمال می کنیم. از آنجا که ترتیب پیمایش در اینجا مهم است، برای یال های درخت حاصل از جستجو جهت تعیین می کنیم. در هنگام اعمال الگوریتم اگر به راسی رسیدیم که قبلاً ملاقات شده از یال جهت دار نقطه چین شده استفاده می کنیم ( به آن ها یال برگشت - Back Edge - می گوییم ) .
با رسیدن به هر راس، آن را شماره گذاری کنید ( شماره هر راس = ( Num ( v ) ، برای هر راس، ( Low ( v را به صورت زیر تعریف می کنیم:
Low ( v ) = min{ Num ( v ) ( Rule 1 ) , lowest Num ( w ) among all back edges ( v, w ) ( Rule 2 ) , lowest Low ( w ) among all tree edges ( v, w ) ( Rule 3 ) } توجه کنید که ( Low ( v از سه مقدار ممکن کمترین را به خود اختصاص می دهد.
برای گراف سادهٔ زیر با شروع از راس A درخت جستجوی ذیل بدست می آید:
کلید: B 2/1 نشان دهندهٔ Low ( B ) = 1 و Num ( B ) = 2 است. همان طور که در تعریف ( Low ( v آمد برای هر راس با توجه به اینکه کدام یک از سه شرط کمینه است ( Low ( v را تعیین می کنیم.
wiki: مؤلفه دوهمبند