دانلود پروژه شبکه ها و تطابق در گراف (ریاضیات)

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

فرمت فایل 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 است.

پروژه شبکه ها و تطابق در گراف (ریاضیات)

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

فرمت فایل 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 است.

تطابق علم و دین

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

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

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

تطابق علم و دین

مطابقت دین با علم و عقل یکی از ۱۲ تعلیم اجتماعی دیانت بهائی است.

بهائیان اعتقاد دارند که دین و علم و عقل هماهنگ بوده و با یکدیگر تطابق دارند. از نظر بهائیان علم موهبت الهی است. از انجا که علم کاشف حقایق اشیاء است بهائیان علم را بزرگ‌ترین منقبت جهان می‌دانند.

عبدالبهاء می‌گوید: «...دین با علم توأم است زیرا دین و علم هر دو حقیقت است اگر دین مخالف حقیقت باشد وهم است و هر مسئلهٔ دینی که مخالف علم صحیح و عقل کامل باشد شایان اعتماد نه. پس تقالید و رسوماتی که منافی علم و ترقّی است باید زائل نمود...»

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

عبدالبهاء ، همچنین جهل و تقلید را موجب گمراهی و عامل اختلافات میان اقوام مختلف می‌داند و علم را سبب عزت و رفع بسیاری از مشکلات بشر معرفی می‌نماید . به علاوه مقام علما و فلاسفهٔ روشنفکر را عظیم می‌شمارد.

انواع علم

عبدالبهاء می‌گوید:

علم بر دو قسم است: علوم مادیه و علوم الهیه. علوم مادیه کشف اسرار طبیعت کند، علوم الهیه کشف اسرار حقیقت نماید. عالم انسانی باید تحصیل هر دو علم کند ؛ اکتفای به یک علم ننماید، زیرا هیچ پرنده‌ای بجناح واحد پرواز نکند. باید به دو بال پرواز نماید. ... مقصود از علم لاهوتی (الهی) کشف اسرار الهی است، ادراک حقایق معنوی است.

تطابق علم و دین

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

ضعف عقل

طبق اعتقادات بهائی عقل انسان با تمام توانائی‌های انکارناپذیرش، نمی‌تواند کاملاً درست تصمیم بگیرد و اگر نتواند مطلبی را که دین می‌گوید ادراک نماید، قصور از دین نیست بلکه از عقل است. و تنها عقل کامل، عقل کلّی الهی است که ماوراء طبیعت است و محیط بر جمیع اشیاء است. این عقل فقط مخصوص مظاهر مقدسه‌است.

علم و دین

شاید اعتقاد آنها باعث شگفتی کسانی شوند که گمان می‌کنند علم و دین دو راه سازش‌ناپذیرند. زندگی معنوی فضانوردان و هزاران دانشمند دیگر، سرّی را فاش می‌کند که در آن دین، کشفیات علمی را تقویت و حمایت می‌کند.

برنامة فضایی در تاریخ خود، فضانوردانی را دیده است که با بی‌باکی و بی‌پروایی اعتقادشان را با خود به فضا برده‌اند و حتی زمانی که آمریکایی‌ها با مسائلی دست و پنجه نرم می‌کردند که علم و دین را از هم جدا می‌کرد – همانند مسائلی در باب آفرینش و تکامل - سازمان‌های بسیاری به وجود آمدند که می‌خواستند پیشه و مهارت‌شان در علم را با اعتقادشان به خداوند درآمیزند.

فرانسیس کالینز، سرپرست مؤسسة ملی تحقیقات ژن انسانی در مصاحبه‌اش با Beliefnet، وب‌سایت مختص موضوعات معنوی می‌گوید: «من دریافته‌ام که باورهای مذهبی‌ام، درک و لذت‌ام را از علم پربارتر کرده است. وقتی چیزی را در ارتباط با ژن‌های انسانی کشف می‌کنم، یک حس شگفتی توأم با ترس دربارة رموز زندگی به من دست می‌دهد. به خودم می‌گویم، فقط خداوند این چیزها را از قبل می‌دانسته. این احساسی شدیداً تکان‌دهنده و زیباست که به من کمک می‌کند خدا را ستایش کنم. افزون بر این علم را برای من ارضاکننده و ارزشمندتر می‌کند.»

در سال 1958 نخستین هفت فضانورد ناسا در یک کنفرانس خبری شرکت کردند. در آنجا جان گلن گفته بود: «من در این پروژه شرکت کردم، چون احتمالاً این پروژه نزدیک‌ترین چیز به بهشت است و من می‌خواستم از آن نهایت استفاده را بکنم.»

در سال 1962، گلن نخستین آمریکایی‌ای بود که دور مدار زمین گشت. در سال 1998، در سن هفتاد و هفت سالگی باز به فضا برگشت و گفت: «این برای من غیرممکن است که به چنین مخلوقی بنگرم در حالی که به خدا ایمان نداشته باشم.»

خدمة «آپولوی 8» اولین شبی را که گرد ماه چرخیدند، جشن گرفتند و در جشن‌شان «سفر تکوین Genesis» - اولین کتاب مقدسی که خلقت را تشریح می‌کند - خواندند. اولین وعدة غذایی بر روی ماه هم عشای ربانی بود که، باز آلدرین (Buzz Aldrin)با خود برده بود. مذهب (دین) در آخرین مأموریت کلمبیا هم در سفینه حاضر بود.

مخلوقی زیبا

هازبند، مهندسی که اولین پرواز فضایی خود را در سال 1999 انجام داد در مصاحبه با شبکه فرسنو بی (Fresno Bee) گفته بود: «من یک مسیحی معتقد و سرسخت هستم. از این پنجره به بیرون نگاه می‌کنم، به این مخلوق زیبایی که خداوند آفریده است.»

تنها عدة اندکی از دانشمندان، فضانورد می‌شوند، اما بسیاری از آنان کارشان را با همان واژه‌های حیرت‌آوری توصیف می‌کنند که فضانوردان به کار می‌برند.

کیتی فرگوسن نویسندة کتاب‌های علمی و نویسندة کتابی دربارة یوهانس کپلر [پروتستان لوتری آلمانی قرن 17 که قوانین حرکت سیاره‌ای را کشف کرد. این قوانین به نام او نامگذاری شده‌اند] می‌گوید: «مطالعة واقعی علم و طبیعت، محقق را به سوی حسی از سرگشتگی و کوچکی انسان در برابر ذهنی بسیار بزرگ‌تر سوق می‌دهد. بسیاری از این محققان خواهند گفت که کمتر می‌توان مثالی چنین باشکوه از نبوغ خداوند در خلقت بیاوریم. مثالی شکوهمندتر از تکامل.»

تطابق علم و دین

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

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

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

تطابق علم و دین

مطابقت دین با علم و عقل یکی از ۱۲ تعلیم اجتماعی دیانت بهائی است.

بهائیان اعتقاد دارند که دین و علم و عقل هماهنگ بوده و با یکدیگر تطابق دارند. از نظر بهائیان علم موهبت الهی است. از انجا که علم کاشف حقایق اشیاء است بهائیان علم را بزرگ‌ترین منقبت جهان می‌دانند.

عبدالبهاء می‌گوید: «...دین با علم توأم است زیرا دین و علم هر دو حقیقت است اگر دین مخالف حقیقت باشد وهم است و هر مسئلهٔ دینی که مخالف علم صحیح و عقل کامل باشد شایان اعتماد نه. پس تقالید و رسوماتی که منافی علم و ترقّی است باید زائل نمود...»

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

عبدالبهاء ، همچنین جهل و تقلید را موجب گمراهی و عامل اختلافات میان اقوام مختلف می‌داند و علم را سبب عزت و رفع بسیاری از مشکلات بشر معرفی می‌نماید . به علاوه مقام علما و فلاسفهٔ روشنفکر را عظیم می‌شمارد.

انواع علم

عبدالبهاء می‌گوید:

علم بر دو قسم است: علوم مادیه و علوم الهیه. علوم مادیه کشف اسرار طبیعت کند، علوم الهیه کشف اسرار حقیقت نماید. عالم انسانی باید تحصیل هر دو علم کند ؛ اکتفای به یک علم ننماید، زیرا هیچ پرنده‌ای بجناح واحد پرواز نکند. باید به دو بال پرواز نماید. ... مقصود از علم لاهوتی (الهی) کشف اسرار الهی است، ادراک حقایق معنوی است.

تطابق علم و دین

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

ضعف عقل

طبق اعتقادات بهائی عقل انسان با تمام توانائی‌های انکارناپذیرش، نمی‌تواند کاملاً درست تصمیم بگیرد و اگر نتواند مطلبی را که دین می‌گوید ادراک نماید، قصور از دین نیست بلکه از عقل است. و تنها عقل کامل، عقل کلّی الهی است که ماوراء طبیعت است و محیط بر جمیع اشیاء است. این عقل فقط مخصوص مظاهر مقدسه‌است.

علم و دین

شاید اعتقاد آنها باعث شگفتی کسانی شوند که گمان می‌کنند علم و دین دو راه سازش‌ناپذیرند. زندگی معنوی فضانوردان و هزاران دانشمند دیگر، سرّی را فاش می‌کند که در آن دین، کشفیات علمی را تقویت و حمایت می‌کند.

برنامة فضایی در تاریخ خود، فضانوردانی را دیده است که با بی‌باکی و بی‌پروایی اعتقادشان را با خود به فضا برده‌اند و حتی زمانی که آمریکایی‌ها با مسائلی دست و پنجه نرم می‌کردند که علم و دین را از هم جدا می‌کرد – همانند مسائلی در باب آفرینش و تکامل - سازمان‌های بسیاری به وجود آمدند که می‌خواستند پیشه و مهارت‌شان در علم را با اعتقادشان به خداوند درآمیزند.

فرانسیس کالینز، سرپرست مؤسسة ملی تحقیقات ژن انسانی در مصاحبه‌اش با Beliefnet، وب‌سایت مختص موضوعات معنوی می‌گوید: «من دریافته‌ام که باورهای مذهبی‌ام، درک و لذت‌ام را از علم پربارتر کرده است. وقتی چیزی را در ارتباط با ژن‌های انسانی کشف می‌کنم، یک حس شگفتی توأم با ترس دربارة رموز زندگی به من دست می‌دهد. به خودم می‌گویم، فقط خداوند این چیزها را از قبل می‌دانسته. این احساسی شدیداً تکان‌دهنده و زیباست که به من کمک می‌کند خدا را ستایش کنم. افزون بر این علم را برای من ارضاکننده و ارزشمندتر می‌کند.»

در سال 1958 نخستین هفت فضانورد ناسا در یک کنفرانس خبری شرکت کردند. در آنجا جان گلن گفته بود: «من در این پروژه شرکت کردم، چون احتمالاً این پروژه نزدیک‌ترین چیز به بهشت است و من می‌خواستم از آن نهایت استفاده را بکنم.»

در سال 1962، گلن نخستین آمریکایی‌ای بود که دور مدار زمین گشت. در سال 1998، در سن هفتاد و هفت سالگی باز به فضا برگشت و گفت: «این برای من غیرممکن است که به چنین مخلوقی بنگرم در حالی که به خدا ایمان نداشته باشم.»

خدمة «آپولوی 8» اولین شبی را که گرد ماه چرخیدند، جشن گرفتند و در جشن‌شان «سفر تکوین Genesis» - اولین کتاب مقدسی که خلقت را تشریح می‌کند - خواندند. اولین وعدة غذایی بر روی ماه هم عشای ربانی بود که، باز آلدرین (Buzz Aldrin)با خود برده بود. مذهب (دین) در آخرین مأموریت کلمبیا هم در سفینه حاضر بود.

مخلوقی زیبا

هازبند، مهندسی که اولین پرواز فضایی خود را در سال 1999 انجام داد در مصاحبه با شبکه فرسنو بی (Fresno Bee) گفته بود: «من یک مسیحی معتقد و سرسخت هستم. از این پنجره به بیرون نگاه می‌کنم، به این مخلوق زیبایی که خداوند آفریده است.»

تنها عدة اندکی از دانشمندان، فضانورد می‌شوند، اما بسیاری از آنان کارشان را با همان واژه‌های حیرت‌آوری توصیف می‌کنند که فضانوردان به کار می‌برند.

کیتی فرگوسن نویسندة کتاب‌های علمی و نویسندة کتابی دربارة یوهانس کپلر [پروتستان لوتری آلمانی قرن 17 که قوانین حرکت سیاره‌ای را کشف کرد. این قوانین به نام او نامگذاری شده‌اند] می‌گوید: «مطالعة واقعی علم و طبیعت، محقق را به سوی حسی از سرگشتگی و کوچکی انسان در برابر ذهنی بسیار بزرگ‌تر سوق می‌دهد. بسیاری از این محققان خواهند گفت که کمتر می‌توان مثالی چنین باشکوه از نبوغ خداوند در خلقت بیاوریم. مثالی شکوهمندتر از تکامل.»

پایان نامه شبکه ها و تطابق در گراف (word)

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

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

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

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

فهرست مطالب

عنوان

صفحه

مقدمه

فصل 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 مقصد است و ظرفیتها، کنار هر کمان نشان داده شده‌اند. چون ، مقدار کالای حمل شده از a به z نمی‌تواند از 12 بیشتر شود. با توجه به بازهم این مقدار محدودتر می‌شود و نمی‌تواند از 11 تجاوز کند. برای تعیین مقدار ماکسیممی که می‌توان از a به z حمل کرد باید ظرفیتهای همة کمانهای بشکه را درنظر بگیریم.

تعریف 1-2 فرض کنیم یک شبکة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه

الف) به ازای هر کمان و

ب) به ازای هر ، غیر از مبدأ a یا مقصد z ، (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم

مقدار تابع f برای کمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف را قید ظرفیت می‌نامند.

شرط دوم، شرط بقا نامیده می شود و ایجاب می کند که، مقدار کالایی که وارد رأس مانند v می شود با مقدار کالایی که از این رأس خارج می شود برابر باشد. این امر در مورد همة رأسها به استثنای مبدأ و مقصد بر قرار است.

مثال 1-2 در شبکه های شکل 1-2، نشان x,y روی کمانی مانند e به این ترتیب تعیین شده است که y , x=c(e) مقداری است که شارشی مانند f به این کمان نسبت داده است. نشان هر کمان مانند e در صدق می کند. در شکل 1-2 (الف)، شارش، وارد رأس می شود،5 است، ولی شارشی که از آن رأس خارج می شود 4=2+2 است. بنابراین، در این حالت تابع f نمی تواند یک شارش باشد. تابع f برای شکل 1-2 (ب) در هر دو شرط صدق می کند و بنابراین، شارشی برای شبکهء مفروض است.