گره سلطه گر - ویکی‌پدیا، دانشنامهٔ آزاد

در گراف های جهت دار، زمانی می‌گوییم گره ${\displaystyle w}$ بر گره ${\displaystyle v}$ غلبه می‌کند که به ازای هر گره ${\displaystyle n}$ همه مسیر ها از ${\displaystyle n}$ به ${\displaystyle v}$، از گره ${\displaystyle w}$ عبور کند. در نتیجه می‌توان گفت هر گره بر خودش غلبه می‌کند. با توجه به تعریف می‌توان برای هر گره مجموعه‌ای از گره های سلطه گر در نظر گرفت که بر این گره غلبه می‌کنند. همچنین می‌توان برای هر گراف یک درخت سلطه گر تعریف کرد که به ازای هر گره در گراف، اجداد این گره در درخت، گره های سلطه گر بر این گره در گراف هستند.

• گره ${\displaystyle v}$ بر گره ${\displaystyle w}$ اکیداً غلبه می‌کند زمانی که گره ${\displaystyle v}$ بر گره ${\displaystyle w}$ غلبه کرده و ${\displaystyle v\neq w}$ باشد.
• گره‌های سلطه گر آنی گره ${\displaystyle v}$ به مجموعه گره‌هایی می گویند که فقط بر گره ${\displaystyle v}$ به صورت اکید غلبه کرده و بر هیچ گره دیگری اکیداً غلبه نکند^[۱].
• گره‌های سلطه گر مرزی گره ${\displaystyle v}$ به مجموعه گره‌هایی می‌گویند که گره ${\displaystyle v}$ بر والدهای مستقیم آنها غلبه کرده ولی به صورت اکید بر آن گره‌ها غلبه نکند.

بنابر تعریف می‌توان برای سلطه گری اکید نتیجه گرفت که نزدیک گره سلطه گر اکید برای هر گره یکتا بوده و یک گره برای آن وجود دارد.

تعریف گره سلطه گر یا غالب برای اولین بار توسط ریس پروسر در مقاله‌ای تحت عنوان کاربردهای ماتریس بولی برای تحلیل نمودارهای جریان^[۲] ارائه شد. او در این مقاله الگوریتمی برای پیدا کردن گره های سلطه گر ارائه نکرد و صرفاً آن را تعریف کرده. اولین الگوریتم برای این مساله ده سال بعد توسط ادوارد لوری و مدلاک ارائه شد^[۳]. از کاربرد های آن می‌توان به زمینه های بهینه سازی برنامه، تولید کد، تست مدار اشاره کرد. همچنین در کامپایلر ها از اطلاعات حاصل از سلطه گری گره‌ها استفاده زیادی می‌شود. برای مثال یک کاربرد آن در کامپایلر برای پیدا کردن حلقه ها در بهینه سازی کد به کمک بلوک های پایه است^[۴].

با توجه به تعریف برای هر گره ${\displaystyle n}$ اگر ${\displaystyle {\text{Dom}}(n)}$ برابر با مجموعه گره‌های سلطه گر بر گره ${\displaystyle n}$ در نظر بگیریم آنگاه رابطه زیر را خواهیم داشت.

$${\displaystyle {\text{Dom}}(n)=(\bigcap _{p\in preds(n)}{\text{Dom}}(p))\ \cup \ \{n\}}$$در اینجا ${\displaystyle preds(n)}$ برابر است با مجموعه تمام گره‌هایی که وارد گره ${\displaystyle n}$ می‌شوند یعنی یک یال از سمت آنها به ${\displaystyle n}$ وجود دارد. همچنین برای گره شروع در گراف داریم

$${\displaystyle {\text{Dom}}(n_{0})=\{n_{0}\}}$$

با داشتن این اطلاعات برای پیدا کردن گره‌های سلطه گر هر گره در گراف می‌توان الگوریتم زیر را پیاده سازی کرد.

// n0 : start node for n in graph - {n0}:     Dom[n] = graph  changed = True while changed:     changed = False     for n in graph:         new = []         for p in preds(n):             new = intersection(new, Dom[p])         new = new + [n]         if new != dom[n]:             dom[n] = new             changed = True 

این الگوریتم در زمان اجرای ${\displaystyle O(n^{2})}$ تمام مجموعه های سلطه گر را می‌یابد که می‌توان با استفاده از داده ساختار های خاص زمان اجرا را بهتر کرد^[۵]. الگوریتم دیگری توسط رابرت تارجان و توماس لینگوار ارائه شده که به وسیله الگوریتم جستجوی اول عمق (الگوریتم dfs) در زمان تقریباً خطی این کار را انجام می‌دهد^[۱].

با توجه به تعریف برای گره سلطه گر مرزی می‌توان رابطه های زیر را بدست آورد.

$${\displaystyle {\text{DF}}(v)={\text{SUCC}}(DOM^{-1}(v))-{\text{DOM!}}^{-1}(v)}$$

که در اینجا ${\displaystyle {\text{DF}}(v)}$ همان مجموعه گره‌های سلطه گر مرزی ${\displaystyle v}$ است و ${\displaystyle {\text{DOM}}^{-1}(v)}$ برابر مجموعه گره‌هایی است که ${\displaystyle v}$ بر آن‌ها غلبه می‌کند و ${\displaystyle {\text{DOM!}}^{-1}(v)}$ برابر است با ${\displaystyle {\text{DOM!}}^{-1}(v)-\{v\}}$. همچنین برای ${\displaystyle {\text{SUCC}}(S)}$ که ${\displaystyle S}$ یک مجموعه است داریم ${\displaystyle {\text{SUCC}}(S)=\bigcup _{s\in S}{\text{SUCC}}(s)}$ که اینجا ${\displaystyle {\text{SUCC}}}$ برای گره ${\displaystyle s}$ برابر است مجموعه تمام گره هایی که از ${\displaystyle s}$ به آنها در گراف جهت دار مسیر وجود دارد. با این رابطه ها می‌توان رابطه زیر را بدست آورد.

$${\displaystyle {\text{DF}}(v)={\text{DF}}_{local}(v)\cup (\bigcup _{w\in Children(v)}{\text{DF}}_{up}(w))}$$

که در اینجا ${\displaystyle Children(v)}$ فرزندان ${\displaystyle v}$ در درخت سلطه گر اند. ${\displaystyle {\text{DF}}_{local}(v)}$ برابر است با تمام ${\displaystyle {\text{SUCC}}(v)}$ که ${\displaystyle v}$ بر آنها را به صورت اکید غلبه نمی‌کند. ${\displaystyle {\text{DF}}_{up}(w)}$ زیر مجموعه‌ای از ${\displaystyle {\text{DF}}(w)}$ است که ${\displaystyle v}$ بر آنها به صورت اکید غلبه نمی‌کند. با توجه به این رابطه الگوریتم زیر بدست می‌آید^[۶].

def FindDF(v):     DF[v] = []     for w in children(v):         FindDF(w)         for u in DF[w]:             if not strictly_dom(v,u):                 DF[v].append(u)     for w in succ(v):         if not strictly_dom(v,w):                 DF[v].append(w)