دانلود تحقیق درباره تحلیل مساله کوتاهترین مسیر در گراف جهت دار 10 ص

اختصاصی از ژیکو دانلود تحقیق درباره تحلیل مساله کوتاهترین مسیر در گراف جهت دار 10 ص دانلود با لینک مستقیم و پر سرعت .

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 10

تحلیل مساله کوتاهترین مسیر در گراف جهت دار

اگر یک گراف جهت دار باشد فرض کنید هر لبه با وزن مشخص می گردد و هزینه رفتن مستقیم از گره i به j را مشخص میسازد بزودی الگوریتم دایجسترا را که برای یافتن کوتاهترین مسیر در گراف با وزن های مثبت کاربرد دارد را بیان میکنیم . در این بخش و بخش بعدی دو مساله مرتبط با گراف را بیان خواهیم کرد .

1 ) گراف G را در نظر بگیرید ( وزن دار ) اگر این گراف دارای سیکل منفی باشد آنگاه یک سیکل جهت دار c مثل :

2) اگر گراف شامل هیچ دوره ( سیکل‌)‌ منفی نباشد یافتن مسیری به نام p از گره آغازی s و گره پایانی t با کمترین هزینه : باید کمترین باشد به ازای هر مسیر از s به t . این مساله به هر دو نام مسیر با کمترین هزینه و کوتاهترین مسیر نامیده می شود .

طراحی و آنالیز الگوریتم :

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

در این گراف یک مسیر از s به t با ملاقات چندین دفعه دوره ( سیکل ) C بدست می آید .

کوتاهترین مسیر با شروع از گره آغازین s به هر نود v در یک گراف اصولا یک الگوریتم حریصانه است . ایده اصلی از یک مجموعه S تشکیل شده است که کوتاهترین مسیر از هر نود s به هر نود داخل مجموعه S شناخته شده است . در این شکل این الگوریتم را نشان می دهیم با شروع میکنیم . ما میدانیم کوتاهترین مسیر از s به s دارای هزینه صفر است زمانیکه هیچ لبه با وزن منفی نداشته باشیم . سپس این عنصر را به طور حریصانه به مجموعه اضافه میکنیم . در طی مرحله اول الگوریتم حریصانه ما کمترین هزینه لبه های گره s را تشکیل خواهیم داد . بعبارت دیگر یعنی : . یک نکته مهم با توجه به الگوریتم دایجسترا این است که کوتاهتری مسیر از s به v با یک یال نمایش داده می شود بنابراین بلافاصله نود v را به مجموعه S اضافه میکنیم . پس مسیر مسلما کوتاهترین مسیر به v است اگر هیچ یالی با هزینه منفی نداشته باشیم . مسیر های دیگر از s به v باید از یک یال خارج شده از s که حداقل هزینه بیشتری نسبت به لبه (s,v) داشته باشند شروع میشوند .

این ایده همواره صحیح نیست بویژه زمانی که دارای لبه های با وزن منفی هستیم .

یک ایده برنامه نویسی پویا :

یک روش برنامه نویسی پویا سعی بر حل این مساله برای یافتن کوتاهترین مسیر از s به t زمانیکه لبه با وزن منفی داشته باشیم اما سیکل ( دوره ) با طول منفی نداشته باشیم . زر مساله i می تواند کوتاهترین مسیر را تنها بوسیله استفاده از i گره اولیه پیدا کند . این ایده بلافاصله جواب نمی دهد بلکه با اعمال اندکی تغییرات جواب دلخواه را به ما میدهد . الگوریتم Bellman-Ford algorithm این الگوریتم را بوسیله برنامه نویسی پویا مطرح کرده و حل کرده اند .

(6.22)

اگر G دورهای منفی نداشته باشد؛‍‍‍ پس کوتاهترین مسیر ساده از S به t وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1 یال دارد.

اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P از s به t با بیشترین تعداد از یالها هیچ راس v را مرور نمی کند. اگر P ؛ راس v را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد.

اجازه دهید OPT(i,v) را برای تفکیک کمترین هزینه یک مسیر v-t با استفاده از بیشترین یال i مورد استفاده قرار دهیم. مطابق مساله (6.22) اصی ترین مشکل؛ محاسبه OPT(n-1.s) است.(ما می توانیم به جای ساخت الگوریتم؛ زیر مسائل مرتبط با کمینه هزینه مسیر s-v را با استفاده از بیشترین یالi جایگزین کنیم. این یک موازی طبیعی با الگوریتم دایجسترا شکل خواهد داد. اما در پروتوکل های مسیر یابی که بعدا شرح خواهیم داد؛ این یک روش طبیعی نخواهد بود.)

اکنون راه ساده ای را برای بیان OPT(i,v) با استفاده از زیرمسائل کوچکتر نیازداریم. ما دیداه طبیعی تری که نکات بسیاری حالات مختلف را در بر می گیرد را مرور خواهیم کرد؛ این مثال دیگری است از اصل "انتخابهای چند مسیره" که در الگوریتم مساله کوچکترین مربعات بخش شده خواهیم دید.

اجازه دهید؛ مسیر بهینه p OPT(i,v) را که در شکل 6.22 نمایش داده شده است را اثبات کنیم.

اگر مسیر p در حداکثر i-1 مورد استفاده قرار گیرد؛ در اینصورت خواهیم داشت:

OPT(i, v) = OPT(i −1, v)

اگر مسیر p ؛ i یال را مورد استفاده قرار دهد و اولین یال (v,w) باشد؛ در اینصورت:

OPT(i, v) = cvw + OPT(i − 1, w)

این موارد ما را به فرمول بازگشتی زیر می رساند:

نظریه گراف و کاربردهای آن

اختصاصی از ژیکو نظریه گراف و کاربردهای آن دانلود با لینک مستقیم و پر سرعت .

مقالات  ریاضی  با فرمت           DOC           صفحات  58

عنوان ...........................................................صفحه

فصل اول .............................................................................. 6

مقدمه...................................................................................................... 7

آشنایی با گراف ............................................................................................8

یک ریختی گراف ها..................................................................................... 9

ماتریس وقوع . مجاورت.............................................................................. 10

زیر گراف ها................................................................................................ 10

درجه راس ها.............................................................................................. 12

مسیرها..................................................................................................... 12

دور ها........................................................................................................ 13

مساله کوتاه ترین مسیر.............................................................................. 15

فصل دوم  .............................................................................................20

درخت ها ................................................................................................... 21

یال های برشی  و باندها............................................................................... 23

راس های برشی........................................................................................... 24

فرمول کیلی............................................................................................... 25

مساله ارتباط دهی....................................................................................... 26

فصل سوم  ...........................................................................................28

همبندی..................................................................................................... 29

ساخت شبکه های ارتباطی قابل اعتماد......................................................... 31

تورهای اویلری و دورهای همیلتنی ................................................................. 33

دور های همیلتنی........................................................................................ 34

مساله پستچی چینی ................................................................................... 36

الگوریتم فلوری........................................................................................... 37

مساله فروشنده دوره گرد............................................................................. 37

فصل چهارم ..........................................................................................39

تطابق ها................................................................................................... 40

تطابق ها و پوشش ها در گراف های دو بخشی................................................ 41

تطابق کامل.............................................................................................. 43

رنگ آمیزی یالی......................................................................................... 43

قضیه ویزینگ............................................................................................. 45

مساله زمان بندی ...................................................................................... 47

فصل پنجم .............................................................................52

پیوست .....................................................................................................53  

  فصل اول

مقدمه:

در دنیای اطراف ما، وضعیف های فراوانی وجود دارند که می توان توسط نموداری متشکل از یک مجموعه نقاط ، به علاوه خطوطی که برخی از این نقاط را به یکدیگر متصل می کنند، به توصیف آنها پرداخت، به عنوان مثال ، برای نشان دادن رابطه دوستی بین یک دسته از انسان ها می نوانیم هر شخص را با یک نقطه مشخص کنیم . نقاط متناظر با هر دو دوست را با یک خط به یکدیگر وصل نماییم، یا در جای دیگر ممکن است برای نشان دادن یک شبکه ارتباطی، از نموداری استفاده کنیم که در آن ، نقاط نمایانگر مراکز ارتباطی و خطوط، نشان دهنده پیوندهای ارتباطی بین مراکز باشند. توجه داشته باشید که در این گونه نمودارها، آن چه بیشتر مورد توجه است این است که آیا دو نقطه داده شده ، به وسیله یک خط به یکدیگر متصل هستند یا نه و طریقه اتصال آنها اهمیتی ندارد. تجربه ریاضی این وضعیت ها به مفهوم گراف منتهی می شود.

گراف G یک سه تایی مرتب است که تشکیل شده از یک مجموعه ناتهیV(G) از راس ها، یک مجموعه E(G) – مجزای از V(G) – از یال ها و یک تابع وقوع که به هر یال G ، یک زوج نا مرتب از راس های G را – که الزاماً متمایز نیستند – نسبت می دهد. اگر e یک یال وu و دو راس باشند به طوری که ، در این صورت گفته می شود که e، راس هایu و را به یکدیگر وصل کرده است و راس های u و  ، دو سر یال e نامیده می شوند.

دلیل نامگذاری گراف ها بدین نام، این است که می توان آنها را به صورت گرافیکی نمایش داد و همین نمایش گرافیکی است که ما را در درک بسیاری از خواص گراف ها یاری می کند. در این گونه نمایش داده می شود.

آشنایی با گراف

نمودار یک گراف ، فقط رابطه وقوعی را که بین راس ها و یال ها برقرار است، نشان می دهد، با این حال در غالب اوقات ، نموداری از یک گراف را رسم کرده ، به جای خود گراف ، به نمودار آن اشاره می کنیم. به همین منوال نقطه های آن را «راس» و خطوط آن را «یال» می نامیم.

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

مقاله فرهنگ لغات نظریه گراف ها

اختصاصی از ژیکو مقاله فرهنگ لغات نظریه گراف ها دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود در "پایین مطلب"

فرمت فایل: word (قابل ویرایش و آماده پرینت)
تعداد صفحات 11

از wikipedia، دایره المعارف آزاد.

نظریه گراف یک منطقة رشد در تلفیق ریاضی می باشد و یک واژگان تخصصی زیادی دارد. بعضی از نویسندگان کلمه یکسان با معانی، مختلف به کار می برند. بعضی نویسندگان کلمات مختلف با کلمات معانی یکسان بکار می برند. این مقاله تلاش در جهت               کاربرد فعلی را دارد.

مندرجات

1-اصول ها

101-زیر مجموعة گراف ها

102-waiks

103-درفت ها

104-دسته ها

105-مولنه های متصل شدید

106-گره ها

107-جزئی ها

108-جایگزین ها

2-نزدیکی مجاورت و درجه

201-مستقل

3-اتصال

4-فاصله

5-نوع

6-گراف های وزنی و شبکه ها

7-سازماندهی

8-تنوع

9-ترکیب شده

10-رجوع کردن به

11- منابع

اصول ها

یک گراف G شامل دو عنصر به نام رئوس ها و لبه ها می شود. هر لبه ای، دو       پایان در یک دسته اتوس دارد که به این دو نقطه پایانی اتصال یا الحاق گفته می شود همچنین یک دسته از لبه ها را می توان به عنوان یک زیر مجموعه از ترکیب دسته های دو عنصری رئوس ها تعریف نمود. بنابراین، دستة رئوس ها به عنوان یک دسته مورد بررسی قرار می گیرند و یک نسبت تلاقی وجود دارد که هر لبه ای را با یک جفت رئوس ترسیم می کنند که در اصل نقاط پایانی آن می باشد. 

لبه ها ممکن است به سازمان عملی، راهنمایی نظریه ای از یک کران هدایت شده یا دو گرافی واگذار شده باشند، به بخش سازماندهی رجوع کنید.

مدل های جایگزین گراف موجود می باشد، برای مثال یک گراف ممکن است به عنوان یک تابع دو تائی بولی بیش از یک دسته رئوس یا به عنوان یک مجذور ماندیس (1/0) در نظر گرفته شده باشد.

یک رأس (عنصر اساس) معمولاٌ به عنوان یک گره یا یک نقطه ترسیم می شود. دست رأس از G معمولاٌ با علامت (G)Vیا با علامت V در زمان که هیچ بهم ریختگی مهمی وجود ندارد، مشخص می گردد. ترتیب یک گراف تعدادی از رئوس هایش با علامت

‍               می باشد.

یک لبه ای که (یک دسته از دو عنصرها)، به عنوان یک خط متصل به دو رأس، رئوس پایانی یا نقاط پایانی نامیده می شوند. یک لبه با رئوس پایانی x وy به وسیله xy علامت گذاری می شوند (بدون هر نشانه دیگری در میانشان). دسته لبه  Gمعمولاٌ به وسیلة علامت (G)E، یا علامت E در زمانی که هیچ به هم ریختگی مهمی وجود ندارد، مشخص می گردد.

تحقیق درمورد شبکه ها و تطابق در گراف

اختصاصی از ژیکو تحقیق درمورد شبکه ها و تطابق در گراف دانلود با لینک مستقیم و پر سرعت .

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 50

دانشگاه پیام نور

(تهران مرکز)

رشته ریاضی کاربردی

موضوع

شبکه ها و تطابق در گراف

استاد راهنما

سرکارخانم بشارتی

تهیه کننده

مرضیه یوسفی

پاییز 1383

فهرست مطالب

عنوان

صفحه

مقدمه

فصل 1

شبکه ها

1-1 شارش ها

1-2 برش ها

1-3 قضیه شارش ماکزیمم – برش مینیمم

1-4 قضیه منجر

فصل 2

تطابق ها

2-1 انطباق ها

2-2 تطابق ها و پوشش ها در گراف های دو بخش

2-3 تطابق کامل

2-4 مسأله تخصیص شغل

منابع

شبکه ها

شارش ها

شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.

تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:

(الف) رأس یکتایی مانند وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.

(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد که به هر کمان یک ظرفیت، که با نشان داده می‌شود، نسبت می‌دهد.

برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.

مثال 1-1 گراف شکل 1-1 یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و

تحقیق شبکه ها و تطابق در گراف

اختصاصی از ژیکو تحقیق شبکه ها و تطابق در گراف دانلود با لینک مستقیم و پر سرعت .

42 صفحه

شبکه ها

• شارش ها

شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.

تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:

(الف) رأس یکتایی مانند وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.

(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعة اعداد صحیح نامنفی، وجود دارد که به هر کمان یک ظرفیت، که با نشان داده می‌شود، نسبت می‌دهد.

برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.

مثال 1-1 گراف شکل 1-1 یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است