مقاله در مورد گراف

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

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

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

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

به نام ایزد منان

گراف

(گراف همیلتنی)

استاد مربوطه :

جناب آقای غلامی

گرداورنده :

زکیه صدقی

بهار87

گراف و طبقه بندی آن

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

تعریفی که ما از گراف برایتان ارائه می‌دهیم، یک تعریف تقریبا شهودی می‌باشد:

یک گراف شامل نقاطی است که راس نامیده می‌شود و این راسها به وسیله خطوطی (که لازم نیست خط راست باشند) به هم وصل می‌شوند. این خطوط را یال می‌گوئیم.در بعضی از کتابها از کلمات گره و نقطه هم به جای راس استفاده می‌شود.

ریشه لغوی :

«گراف » از کلمه «Graph» از زبان انگلیسی گرفته شده است که به معنای نمودار و طرح هندسی می‌باشد.

دید کلی

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

تاریخچه

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

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

نقش و تاثیر زندگی

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

طبقه بندی‌های مشهور در تئوری گراف

گراف همبند و ناهمبند

یک گراف همبند است اگر بین هر دو راس دلخواه آن مسیری وجود داشته باشد. در غیر این صورت گراف را ناهمبند گوئیم.

گراف اویلری و نااویلری

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

گراف همیلتنی و ناهمیلتنی

یک گراف همبند همیلتنی است اگر دوری وجود داشته باشد که شامل همه رئوس آن باشد. در غیر این صورت ناهمیلتنی است.

گراف مسطح و غیرمسطح

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

درخت :گراف فاقد دور و بدون حلقه را درخت می‌نامیم.

گرافهای دو بخشی ، کامل ، n _ منتظم

گراف دو بخشی گرافی است که راسهای آن را بتوان به دو بخش A و B چنان تقسیم کرد که هر یال در گراف یک راسش در A باشد و راس دیگرش در B. گرافی که بین هر دو راس آن یالی باشد، گراف کامل می‌گوئیم. یک گراف ،_ n منتظم است اگر درجه همه راسهایش n باشد.

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

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

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

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

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

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

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

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

پاورپوینت گراف

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

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

 فرمت فایل: powerpoint (قابل ویرایش و آماده پرینت)

 تعداد اسلاید:16

تعاریف

مجموعه ای غیر تهی از راس

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

انواع گراف

گراف بدون جهت Undirected graph

گراف جهت دار Directed graph

گراف چند یالیMulti-graph

گراف کاملComplete Graph

گراف ساده Simple graph

 

تحقیق در مورد حل مسئله با جست وجو

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

بسم الله الرحمن الرحیم – فرمت فایل :word ( با قابلیت ویرا یش ) – تعداد صفحه : 7 صفحه -

1. تعریف مفاهیم زیر؟

حالت:یک حالت شرایطی ست که یک عامل می تواند خودش را در آن بیابد.ما دو نوع حالت را می توانیم تشخیص دهیم:وضعیت های جهان (شرایط پیوسته ای واقعی در جهان واقعی) وضعیت های نمایشی(عامل ها بعد از تعمق در کاری که انجام می دهند شرح انتزاعی از جهان واقعی ارائه می دهند )

فضای حالت:یک گراف است که نودهای آن همه حالت ها را نشان می دهند،و اتصالات آن فعالیتهایی هستند که برای انتقال از یک حالت به حات دیگراتفاق می اقتند.

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

نود جستجو:یک نود در درخت جستجوست

هدف:مجموعه ای از حالت های دنیا در نظر می گیریم.وظیفه عامل یافتندنباله ای است از فعالیتها آن را به حالت هدف می رساند.

فعالیت:چیزی است که عامل می تواند آنرا برای انجام انتخاب کند.

تابع جانشین:خصوصیات عامل ها را شرح می دهد:یک مجموعه حالت برمی گرداند،جفت(حالت،فعالیت)،جاهایی که هرحالت یک حالت قابل دسترس به وسیله فعالیتی است که انجام می دهد.

Branch Factor: در درخت جستجو تعداد فعالیت های در دسترس یک عامل.

1. چرافرموله بندی مسئله باید از فرموله کردن هدف پیروی کند؟

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

ترکیبات و نظریه‌ی گراف

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

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

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

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

در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .

این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری می‌باشند حائز اهمیت فراوان می باشند .

1-ترکیبات :

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

ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم .

سوال : یک اتاقی مشبک شده به طول 8 و عرض 8 داریم که خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست‌ آن حذف شده است (مانند شکل زیر)

حال ما دو نوع موزاییک داریم . یکی 2*1 ( ) و دیگری 1×2 ( ) سوال این است که آیا می توان این اتاق را با این دو نوع موزائیک فرش کرد .

احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید «آری» و سعی می کند با کوشش و

خطا اتاق را فرش کند ولی این کار شدنی نیست ؟! و اثبات جالبی نیز دارد .

اثبات : جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر :

حال با کمی دقت متوجه می شویم که هر موزائیک یک خانه از خانه های سیاه و یک خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد که بتوان با استفاده از این موزائیک ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر 32 و تعداد خانه های سیاه برابر 30 می باشد . در نتیجه این کار امکان امکان پذیر نیست .

این مسأله مربوط به مسائل رنگ آمیزی در ترکیبات بوده که دارای دامنه‌ی وسیعی از مسائل دشوار و پیچیده می باشد در زیر چند نمونه از مسائل آسان و سخت را بیان می کنیم .

1-ثابت‌کنید هیچ جدولی را نمی توان به موزائیک هایی به شکل و پوشاند .

(راهنمایی: ثابت کنید حتی سطر اول جدول را هم نمی توان پوشاند)

2-ثابت کنید یک مهره‌ی اسب نمی تواند از یک خانه‌ی دلخواه صفحه‌ی n*4 شروع به حرکت کند و تمام خانه ها را طی کند .

3-یک شبکه‌ی n*m از نقاط داریم یک مسیر فراگیر مسیری است که از خانه‌ی بالا سمت چپ

شروع به حرکت کرده و از همه‌ی خانه هر کدام دقیقاً یک بار عبور کند و به خانه‌ی سمت راست پایین برود ثابت کنید شرط لازم و کافی برای وجود یک مسیر فراگیر در شبکه‌ی n*m آن است که لااقل یکی از m یا n فرد باشد (مرحله‌ی دوم المپیاد کامپیوتر ایران) در شکل زیر یک مسیر فراگیر را برای جدول 5*4 می بینیم .

B

4-ثابت کنید شرط لازم کافی برای پوشش جدول n*m با موزائیک های 2*1 یا 1*2 آن است که یا m یا n زوج باشند .

حال می‌خواهیم یک مبحث مهم از ترکیبات به نام استقراء را معرفی کنیم.

استقراء بعنی رسیدن ازجزء به کل و هم ارز است با اصل خوشترتیبی زیر مجموعه‌ها( اصل خوشتربینی بیان می‌کند که هر مجموعه متناهی از اعداد عضوی به نام کوچکترین عضو دارد).

برای اثبات حکمی به کمک استقراء لازم است: