دورها
می‌گوئیم یک گشت ، بسته است ، اگر طول آن مثبت بوده ابتدا و انتهای آن یکسان باشند. یک گذرگاه بسته که ابتدا و راس‌های داخلی آن متمایز باشند، دور نامیده می‌شود. همانند مسیرها، گاهی اوقات لفظ «دور» را به منظور اشاره به گرافی که متناظر با یک دور است به کار می‌بریم ، یک دور با طول k راk- دور می‌نامیم.
یک k- دور بسته به اینکهk زوج یا فرد باشد ، یک دور زوج یا فرد می‌نامیم. غالباً به ۳- دور ، مثلث گفته می‌شود.
یک گراف ، دو بخشی است اگر و تنها اگر هیچ دور فردی نداشته باشد.
اثبات: فرض کنید G یک گراف دوبخشی با دو بخش XوY و  یک دور از G باشد. بدون اینکه از کلیت مساله کاسته شود، می‌توانیم فرض کنیم که  .چون  دو بخشی  به همین دلیل  و در حالت کلی داریم:  . از آن جایی که  پس  ، در نتیجه به ازای یک مقدار i داریم  و بنابراین c زوج خواهد بود.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

واضح است که اثبات عکس ، برای گراف‌های همبند کافی است. فرض کنید G یک گراف همبند باشد که هیچ دور فردی ندارد یک راس دلخواه مانند  را انتخاب کرده، افزار (X,Y) از V را به صورت زیر تعریف می‌کنیم.
زوج است
زوج است
نشان خواهیم داد که G یک گراف دوبخشی با دو بخش X و Y است فرض کنید  دو راس X باشند.P را به عنوان کوتاه‌ترین  - مسیر و Q را به عنوان کوتاه‌ترین  - مسیر در نظر می‌گیریم.آخرین راس مشترک P وq را با  نشان می‌دهیم. چون P و Q کوتاه‌ترین مسیر‌ها هستند،  - قسمت‌های P و Q نیز کوتاه‌ترین  - مسیر‌ها می‌باشند و بنابراین طول برابری خواهند داشت. از آن جایی که طول‌های P و Q هر زوج هستند، طول  - قسمت  از  و  - قسمت  از  باید از نظر زوج و فرد بودن ، یکسان باشند. از اینجا نتیجه می‌شود که طول  - مسیر  زوج است. بنابراین هیچ دو راسی در X مجاور نیستند. به طور مشابه هیچ دو راسی از Y نیز مجاور نخواهند بود.
مروری بر تحقیقات انجام شده

مقدمه
مساله‌ی بودجه بندی در یک گراف بصورت نظری و در عمل خیلی خوب بررسی شده و بصورت گسترده در صنعت و تحقیقات امروزی در حال استفاده است. رویکرد ما مجموعه بزرگی از نمونه‌های مدیریت بودجه موجود را تجمیع و یکپارچه می‌کند. مثال‌هایی از این دست شامل بودجه بندی زمانی برای به حداکثر رساندن کاهش تاخیر وزنی کل، به حداقل رساندن بیشترین میزان کاهش و انحراف معیار توزیع بودجه زمانی هستند. نشان می‌دهیم که خیلی از مسائل بودجه بندی زمانی می‌تواند به یک نمونه‌ی با حداقل هزینه تبدیل شود که می‌تواند بصورت بهینه و موثر از طریق تکنیک‌های ترکیبی شناخته شده حل شوند.
کاربردهای بودجه بندی در یک گراف
بودجه بندی کاربردهای مختلفی در بهینه‌سازی طراحی دارد، که عبارتند از:
طراحی محدوده زمان‌بندی: در طول جریان بهینه‌سازی طراحی، بودجه‌ی زمانی تحت یک محدوده زمانی به هر گره تخصیص داده می‌شود و بهینه‌سازی بکار برده می‌شود. اگر محدودیت زمان‌بندی رعایت نشود، بودجه تاخیر مجددا تخصیص داده می‌شود. توزیع بودجه تاخیر برای تعیین طول مسیر تحت محدوده‌های زمانی داده شده بکار گرفته می‌شود.
جایگذاری بر طبق زمان و برنامه ریزی حداقل: بودجه بندی تاخیر در طول جایگذاری و برنامه ریزی حداقل بصورت گسترده توسط محققان مختلف ازجمله آ کاهنگ و همکاران^[۱۷]، سی کئو و همکاران^[۱۸] و… ]۲۳[،]۲[،]۶[،]۵[ مورد مطالعه قرار گرفته است. در جایگذاری بر طبق زمان، هدف بهینه‌سازی تاخیر مسیرها با کم کردن تکرارهاست. بودجه‌ی تاخیر به یال‌ها در گراف اختصاص داده می‌شود. محدوده‌های تاخیر به ازای هر دور در نظر گرفته می‌شوند تا توزیع بهتری از بودجه‌های تاخیر در گراف داشته باشیم. در منابع ۲۴ و ۲۳ جایگذاری و بودجه بندی مجدد ترکیب شده اند. مساله‌ی بهینه‌سازی بودجه در یال‌های یک گراف بصورت یک تابع خطی هدف و بصورت مقطعی فرمول سازی می‌شود و با بهره گرفتن از یک الگوریتم ساده سازی گراف اصلاح شده حل می‌شود.
اندازه بندی دروازه/خطوط و بهینه‌سازی انرژی: تحت یک محدوده زمانی داده شده، مدیریت بودجه می‌تواند بکار رود تا مجموعه‌ای ‌از یال‌ها/گره‌ها را در گراف به گونه‌ای ‌پیدا کنیم که اندازه فیزیکی آن ها یا مصرف انرژی آن ها کاهش داده شود و این کار با تغییر مسیر به نمونه‌های سلولی کوچکتر یا مصرف انرژی بهینه تر با تاخیر بزرگتر از کتابخانه‌های هدف انجام می‌شود.
فشرده سازی الگوی مدارهای مجتمع: هدف اصلی حداقل کردن فضای فیزیکی الگو است. بعلاوه حداقل کردن طول خطوط نمی‌تواند طی بهینه‌سازی نادیده گرفته شود. مفهوم بودجه در چنین مسائلی برای این استفاده می‌شود که طول خطوط کاهش داده شود. یک محدودیت مهم در طراحی IC آنالوگ محدودیت تشابه در الگو است. با چندین محدودیت تشابه، فشرده سازی الگو با بهره گرفتن از راه حل LP حل می‌شود. در منبع ۳۲ اس ال لین^[۱۹] و جی آلن^[۲۰] یک شیوه‌ی ساده سازی بر اساس گراف بکار می گیرند تا زمان اجرای الگوریتم برنامه نویسی خطی را ارتقا بخشند. فرمول سازی LP برای فشرده سازی، مشابه مساله‌ی بودجه بندی است. بودجه‌ی فضا در طول محور X یا محور Y اختصاص داده می‌شود تا فضای کافی برای کشیدن خطوط باقی بماند.
استفاده از شناور در ترکیبات با سطوح بالا: کارهای مشابه زیادی در زمینه‌ی ترکیبات سطح بالا وجود دارد که در آنها زمانبندی شناور گره‌ها در گراف‌های جریان داده در نظر گرفته می‌شوند تا بهینه‌سازی فضا و مصرف انرژی به وجود آید. مثال‌هایی از این دست، الگوریتم‌ها و تکنیک‌هایی هستند که برای به حداقل رساندن فضا در مسیرهای خط کشی لوله، حداقل کردن مصرف انرژی در محدوده‌ی زمانی و غیره است. در منبع ۲۹ بخشی^[۲۱] و گاجسکی^[۲۲] ورودی طراحی یک مسیر خط کشی لوله گرفتند. در مساله‌ی فرمول سازی، مجموعه‌ای ‌از محدودیت‌ها وجود دارند که بر تعداد ثبات‌ها و عمق خطوط لوله تاثیرگذار هستند؛ که در بودجه بندی بر روی DAG در نظر گرفته نمی‌شوند. تمام الگوریتم‌های پیشنهادی، الگوریتم‌های نیمه بهینه و ابتکاری هستند.
کم هزینه‌ترین جریان
الگوریتمی‌برای به دست آوردن کم هزینه ترین مسیرها برای ارسال جریان در یک مدار را از نقطه شروع به نقطه پایان می‌باشد. حل این مسئله کاربردهای زیادی در مسائل روزمره دارد به طور مثال شبکه‌هایی که دارای هزینه اند همچون شبکه‌های مخابراتی یا مسائلی که تناسب آن‌ها چنان با مسئله مورد بحث مشهود نیست مثل محل قرارگیری انبارها.

تعریف مسئله و شرایط
یک شبکه شاره داریم که آن را با گراف جهت‌دار  با مبدا  و مقصد  که در آن یال  دارای ظرفیت  ، جریان  و هزینه  می‌باشد، نشان می‌دهیم (اکثر الگوریتم‌های کم‌هزینه‌ترین جریان یال با هزینه منفی را پشتیبانی می‌کنند.) هزینه فرستادن این جریان  است. شما باید جریان d را از s به t بفرستید.
تعریف مسئله کمینه کردن هزینه کل جریان است:
(‏۲‑۱)
با شرط‌های زیر:

بیشینه جریان