به طور مثال بر اساس رابطه فوق در شکل (۲-۱) ۵ وجه داریم که با حروف بزرگ نمایش داده شده اند.
شکل۲-۱: گراف مدنظر گرفته شده
دو شرط لازم و نه کافی برای مسطح بودن یک گراف به صورت زیر هستند.
(۲-۲)
جدای از دو شرط ضروری گفته شده، یک نظریه وجود دارد که شرایط لازم و کافی برای مسطح بودن یک گراف را عنوان می کند. قبل از شرح این نظریه لازم است که دو نوع خاص از گرافها را معرفی کنیم. گرافهای کورتوفسکی[۳]و گرافهای همدیس[۴]. شکل (۲-۲) دو گراف کورتوفسکی را نشان میدهد.
شکل۲-۲: گرافهای کورتوفسکی
همچنین دو گراف را همدیس مینامند اگر بتوان با اضافه کردن یالهای جدید و یا حذف کردن یالهای موجود، یک گراف را از روی دیگری ساخت.با تعریف این دو نوع گراف میتوان نظریه را عنوان نمود. بر طبق نظریه، شرط لازم و کافی برای مسطح بودن یک گراف این است که آن گراف شامل هیچ دو گراف کورتوفسکیای نباشد یا اینکه هیچ زیرگرافی از آن، با زیرگراف دیگر گراف همدیس نباشد.
تجربه نشان داده است که تمام شبکه های توزیع، شروط لازم و کافی برای سطحی بودن را دارا میباشند.
حال به بررسی گراف دوگان میپردازیم. گراف دوگان G*از یک گراف مسطح G به صورت زیر تعریف می شود.
۱- به ازای هر وجه G، یک راس در G* وجود دارد.
۲- برای هر یالی که مابین دو وجه همسایه در G وجود دارد، یک یال متناظر بین دو گره(راس) G* وجود دارد.
۳- به ازای هر یال معلق(یالی که راس متصل شده به یک سمت آن از درجه ۱ است) در G، یک حلقه در راس متناطر با آن در G*داریم.
این تعریف نشان میدهد که اگر گراف G، n راس، m یال و f وجه، داشته باشد آنگاه G*، f راس، m یال و n وجه دارد.شکل (۲-۳) یک گراف و گراف دوگان آن را نشان میدهد که با خطچین نشان داده شده است.
شکل۲-۳: گراف و دوگان متناظر با آن
قید شعاعی بودن یک شبکه توزیع مشابه با قید درخت پوشا در نظریه گراف است. یک گراف پوشای مینیمم در یک گراف غیرجهتدار وزنی، زیرگرافی است که اولا درخت باشد و ثانیا اینکه جمع اوزان یالهای آن مینیمم مقدار ممکن را داشته باشد.ابتدا یک گراف غیرجهتدار را به دو گراف جهتدار تبدبل میکنیم. متغیرهای زیر تعریف شده و آنها را در گراف g تنظیم(مقداردهی) میکنیم.
Xij: حالت یال مابین دو راس i و j.
Wij: وزن یال مابین دو راس i و j.
Ni: مجموعه رئوسی که به طور مستقیم به راس i وصل شده اند.
و در گراف دوگان G*:
Y(k,l),e: حالت یالی( یا یالهایی) که راس k را به راس l متصل می کند. اندیس e برای تشخیص یالهایی استفاده می شود که بین دو راس مشابه قرار دارند.
Mk: مجموعه راسهایی که به صورت مستقیم با راس k در ارتباط هستند.
Sk,l: مجموعه یالهایی که بین دو راس k و l قرار دارند.
مسئله مینیمم درخت پوشا به صورت زیر فرمولبندی شده است.
(۲-۳)
با توجه به اینکه:
(۲-۴)
و همچنین برای تمام یالهای موجود در G، باید رابطه زیر وجود داشته باشد.
بنابراین ابتدا تمام پارامترهای زیر را برای گراف شبکه بدست میآوریم و از روی آنها گرافهای پوشا را تشکیل میدهیم. به عبارت دیگر در روش ارائه شده در مرجع [۱] با بهره گرفتن از روابط گفته شده در فوق، برای کاندیدای پاسخ آرایش بهینه شبکه، پارامترهای مختلف اشاره شده را بدست آورده و با توجه به روابط درخت پوشا، چک میکنیم که آیا این کاندید پاسخ، یک درخت پوشا هست و یا خیر؟ شعاعی بودن مترادف با تشکیل درخت پوشاست[۱].
فرمول بندی قیود شعاعی
فرمولاسیون قید شعاعی برای سیستم ۹ گره نشان داده شده در شکل (۱-۳) در این بخش با جزئیات بیشتری بررسی شده است.مجموعههای مورد نیاز فرمول بندی به صورت زیر می باشند.
در ادامه، مثالهایی داده شده است که نحوه نوشتن قیود مسئله را توضیح میدهند. در نمودار اولیه (۴a)
در نمودار دوگان(۴b)
برای(۴c)، هر شاخه یک معادله دارد
شکل ۲-۴: شبکه بدست آمده توسط استفاده از قیود شعاعی متداول
در صورتی که یک گره مستقل در شبکه وجود داشته باشد (گرهای که تنها یک شاخه به آن متصل است، که این شاخه در درختی پوشاست)، با قطع شاخه متصل به این گره گراف چندقسمتی میشود[۱].
۲-۳- نقاط ضعف در روشهای موجود در بررسی قید شعاعی
چندین روش مختلف در نشریات برای بررسی قید شعاعی بودن پیشنهاد شده است.
اولین روش ارائه دهنده قید شعاعی بودن، که سادهترین روش است، این است که تعداد شاخههای مورد نیاز با تعداد گرهها منهای یک برابر است. به عبارت دیگر
(۲-۵)