مؤلفه دوهمبند

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
ِگرافی با n=5 راس و n-2=3 راس برشی(قرمز)
گراف غیر جهت دار فاقد راس برشی

در ریاضیات و علوم کامپیوتر، راس برشی (به انگلیسی: 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 را تعیین می کنیم.

ابتدا به راس A، مقدار Low(A) = Num(A) = 1 می دهیم- طبق (Rule 1) - (طبیعتا ریشه همیشه 1 می گیرد). از آنجا بنا بر قانون دوم، Low(D) = Num(A) = 1 (چون از راس D به A یک بال برگشت وجود دارد).

حال برای راس C با توجه به قانون سوم، Low(C) = Low(D) = 1 و از آنجا طبق همان قانون Low(B) = Low(C) = 1.

از راس F به راس D یال برگشت وجود دارد پس طبق قانون دوم، Low(F) = Num(D) = 4 در نتیجه Low(E) = Low(F) = 4.

و در آخر چون G هیج یال برگشتی ندارد پس Low(G) = Num(G) = 1.

تعیین راس‌های برشی[ویرایش]

با توجه به اعداد بدست آمده برای هر راس:

  • ریشه یک راس برشی است اگرو تنها اگر بیش از یک فرزند داشته باشد
  • هر راس v غیر ریشه، برشی است اگر و تنها اگر فرزندی مانند w داشته باشد بطوریکه (Low(w) ≤ Num(v

حالت دوم تداعی کنندهٔ اینست که راس v فرزندی مانند w دارد که نمی تواند قبل از اینکه v پیمایش شود به راس دیگری دسترسی داشته باشد، یعنی حذف کردن v باعث انفصال w می شود.

در مثال بالا برای راس Low(G) = 7 ≥ 3 = Num(C) ،C و برای راس Low(E) = 4 ≥ 4 = Num(D) ،D، یعنی C و D راس‌های برشی هستند که رجوع به خود گراف این را تایید می کند.

مثالی دیگر[ویرایش]

درخت شکل مقابل پیمایش همان گراف این بار با شروع از راس C است که نشان می دهد راس شروع کنندهٔ پیمایش تاثیری در نتیجهٔ نهایی ندارد(البته اعداد بدست آمده برای راس‌ها تغییر می کند).

مشاهده می کنیم که: برای راس Low(G) = 7 ≥ 1 = Num(C) ،C و برای راس Low(E) = 2 ≥ 2 = Num(D) ،D، که نشان می دهد C و D رئوس برشی هستند.

الگوریتم[ویرایش]

با فرض اینکه درخت پیمایش (که یالهای برگشتش نیز رسم شده)داده شده است.

شماره گذاری و تعیین والدین[ویرایش]
1  // Assign Num and compute parents
2  Void Graph::assignNum(Vertex v)
3  {
4       v.Num = counter++;
5       V.visited = true;
6       for each Vertex w is adjacent to v
7               if(!w.visited)
8               {
9                       w.parent = v;
10                      assignNum(w);
11              }
12  }
تعیین Low و چاپ راس‌های برشی[ویرایش]
1  //Assign Low and check for cut vertex
2  //Check for Root omitted
3  void Graph::assignLow(Vertex v)
4  {
5       v.Low = v.Num; // Rule 1
6       for each Vertex w adjacent to v
7       {
8               if( w.Num> v.Num) // Forward edge
9               {
10                      assignLow(w);
11                      if(w.Low>= v.Num)
12                              cout <<v <<” is a cut vertex” <<endl;
13                      v.Low = min(v.Low, w.Low);
14              }
15              else
16              if(v.parent != w) // Back edge
17                      v.Low = min(v.Low, w.Num); // Rule 2
18      }
19  }

راه حل سوم[ویرایش]

همانند راه حل بالا، الگوریتم DFS را اعمال می کنیم و درخت جستجوی جهت دار را بدست می آوریم. همان طور که گفته شد اگر راس v فرزند wای داشته باشد که به هیچ ترتیب پیمایشی نتواند قبل از v ملاقات شود، حذف v باعث منفصل شدن w می‌شود یعنی v راس مفصل است. با تکیه بر این مطلب، در درخت جست و جوی بدست آمده:

  • ریشه مفصل است اگر و تنها اگر دارای بیش از 1 فرزند باشد.
  • هر راس v غیر ریشه مفصل است اگر دارای فرزند یا فرزندهایی مانند w باشد بطوریکه هیچ راسی در زیر درخت به ریشهٔ w به هیچ یک از اجداد v با استفاده از یال برگشت وصل نشده باشند.

برای مثال در درخت روبرو، B مفصل نیست زیرا در زیر گراف به ریشهٔ C، از راس D به راس A به عنوان نیای B یال برگشت وجود دارد ولی D مفصل است زیرا در زیرگراف به ریشهٔ E هیچ راسی را نمی توان پیدا کرد که یال برگشتی به یکی از اجداد D داشته باشد. C نیز مفصل است زیرا در زیر گراف به ریشهٔ G هیچ یال برگشتی وجود ندارد.

خوبی این روش نسبت به روش بالا در عدم نیاز به محاسبهٔ Low و Num برای راس‌ها است.

راس‌های برشی در درخت ها[ویرایش]

در هر درخت، همهٔ راس‌ها به جز برگ‌ها راس برشی هستند، چون در درخت دور وجود ندارد.

پیوند به بیرون[ویرایش]

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

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