گره سلطه گر کیست؟ توضیح بده.
در گراف های جهت دار، زمانی می‌گوییم گره formula_1 بر گره formula_2 غلبه می‌کند که به ازای هر گره formula_3 همه مسیر ها از formula_3 به formula_2، از گره formula_1 عبور کند. در نتیجه می‌توان گفت هر گره بر خودش غلبه می‌کند. با توجه به تعریف می‌توان برای هر گره مجموعه‌ای از گره های سلطه گر در نظر گرفت که بر این گره غلبه می‌کنند. همچنین می‌توان برای هر گراف یک درخت سلطه گر تعریف کرد که به ازای هر گره در گراف، اجداد این گره در درخت، گره های سلطه گر بر این گره در گراف هستند. بنابر تعریف می‌توان برای سلطه گری اکید نتیجه گرفت که نزدیک گره سلطه گر اکید برای هر گره یکتا بوده و یک گره برای آن وجود دارد.تاریخچه و کاربرد.تعریف گره سلطه گر یا غالب برای اولین بار توسط ریس پروسر در مقاله‌ای تحت عنوان کاربردهای ماتریس بولی برای تحلیل نمودارهای جریان ارائه شد. او در این مقاله الگوریتمی برای پیدا کردن گره های سلطه گر ارائه نکرد و صرفاً آن را تعریف کرده. اولین الگوریتم برای این مساله ده سال بعد توسط ادوارد لوری و مدلاک ارائه شد. از کاربرد های آن می‌توان به زمینه های بهینه سازی برنامه، تولید کد، تست مدار اشاره کرد. همچنین در کامپایلر ها از اطلاعات حاصل از سلطه گری گره‌ها استفاده زیادی می‌شود. برای مثال یک کاربرد آن در کامپایلر برای پیدا کردن حلقه ها در بهینه سازی کد به کمک بلوک های پایه است.الگوریتم پیدا کردن گره‌های سلطه گر.با توجه به تعریف برای هر گره formula_3 اگر formula_17 برابر با مجموعه گره‌های سلطه گر بر گره formula_3 در نظر بگیریم آنگاه رابطه زیر را خواهیم داشت.formula_19در اینجا formula_20 برابر است با مجموعه تمام گره‌هایی که وارد گره formula_3 می‌شوند یعنی یک یال از سمت آنها به formula_3 وجود دارد. همچنین برای گره شروع در گراف داریمformula_23با داشتن این اطلاعات برای پیدا کردن گره‌های سلطه گر هر گره در گراف می‌توان الگوریتم زیر را پیاده سازی کرد.// n0 : start nodefor n in graph - {n0}: Dom[n] = graphchanged = Truewhile 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 این الگوریتم در زمان اجرای formula_24 تمام مجموعه های سلطه گر را می‌یابد که می‌توان با استفاده از داده ساختار های خاص زمان اجرا را بهتر کرد. الگوریتم دیگری توسط رابرت تارجان و توماس لینگوار ارائه شده که به وسیله الگوریتم جستجوی اول عمق (الگوریتم dfs) در زمان تقریباً خطی این کار را انجام می‌دهد.الگوریتم پیدا کردن گره‌های سلطه گر مرزی.با توجه به تعریف برای گره سلطه گر مرزی می‌توان رابطه های زیر را بدست آورد.formula_25که در اینجا formula_26 همان مجموعه گره‌های سلطه گر مرزی formula_2 است و formula_28 برابر مجموعه گره‌هایی است که formula_2 بر آن‌ها غلبه می‌کند و formula_30 برابر است با formula_31. همچنین برای formula_32 که formula_33 یک مجموعه است داریم formula_34 که اینجا formula_35 برای گره formula_36 برابر است مجموعه تمام گره هایی که از formula_36 به آنها در گراف جهت دار مسیر وجود دارد. با این رابطه ها می‌توان رابطه زیر را بدست آورد.formula_38که در اینجا formula_39 فرزندان formula_2 در درخت سلطه گر اند. formula_41 برابر است با تمام formula_42 که formula_2 بر آنها را به صورت اکید غلبه نمی‌کند. formula_44 زیر مجموعه‌ای از formula_45 است که formula_2 بر آنها به صورت اکید غلبه نمی‌کند. با توجه به این رابطه الگوریتم زیر بدست می‌آید.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)