پاورپوینت کامل و جامع با عنوان نظریه گراف (Graph Theory) در 84 اسلاید

اختصاصی از فی دوو پاورپوینت کامل و جامع با عنوان نظریه گراف (Graph Theory) در 84 اسلاید دانلود با لینک مستقیم و پر سرعت .

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

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

تاریخچه

برخلاف شاخه‌های دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن مسئلهٔ هفت پل کونیگسبرگ است که در سال ۱۷۳۶ توسط لئونارد اویلر حل شد. در سال ۱۷۵۲ قضیهٔ اویلر برایگراف‌های مسطح ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.

در سال ۱۸۴۷، گوستاو کیرشهف نوع خاصی از گراف‌ها به نام درخت را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم قوانین اهم برای جریان الکتریکی در کاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد، آرتور کیلی همین نوع گراف را برای شمارش ایزومرهای متمایز هیدروکربن‌های اشباع‌شدهٔ C_nH_2n+2 به‌ کار برد.

در همین دوران شاهد حضور دو ایدهٔ مهم دیگر در صحنه هستیم. ایدهٔ اول حدس چهار رنگ بود که نخستین بار توسط فرانسیس گوثری در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط کنث ایپل و ولفگانگ هیکن و با استفاده از یک تحلیل رایانه‌ای پیچیده حل شد.

ایدهٔ مهم دوم، دور همیلتونی بود. این دور به افتخار سر ویلیام روآن همیلتون نامگذاری شده است. او این ایده را در سال ۱۸۵۹ برای حل معمای جالبی حاوی یال‌های یک دوازده وجهی منتظم به‌کار گرفت. یافتن جوابی برای این معما چندان دشوار نیست، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که گراف‌های بیسوی حاوی مسیر یا دورهای همیلتونی را مشخص کنند.

پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئلهٔ مشخص کردن گراف‌های مسطح را کازیمیر کوراتوفسکی، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین کتاب دربارهٔ نظریهٔ گراف در سال ۱۹۳۶ منتشر شد. این کتاب را ریاضیدان مجار، دنش کونیگ، که خود محقق برجسته‌ای در این زمینه بود، نوشت. از آن پس فعالیت‌های بسیاری در این زمینه صورت گرفته و رایانه نیز در چهار دههٔ اخیر به یاری این فعالیت‌ها آمده است.

تعریف

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

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

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.

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

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

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و... است.

روابط میان راس‌های یک گراف را می‌توان با کمک ماتریس بیان کرد.

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

فهرست مطالب:

مثال های ملموس از گراف

نقطه بازی

سنگ بنای نطریه گراف

پل کونیگسبرگ

معمای ضیافت 6 نفره

مسئله 8 دایره

تعریف گراف

نکته

گراف جهتدار

مرتبه گراف

اندازه گراف

حلقه

راس منفرد

گراف بدون جهت

گراف ساده

مثال

گراف های معروف

زیرگراف ها

زیرگراف سره

زیرگراف فراگیر

زیرگراف القایی

معمای جنون آنی

گراف تهی

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

مسیرها و دورها

تعریف مسیر

تعریف دور

گشت ها

گذرها

طول دور

گراف دوبخشی

درجه راس ها

دنباله درجات رئوس

دنباله گرافیکی

تشخیص گرافیکی بودن

گراف کامل

گراف منتظم

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

همبندی گراف

نمایش گراف در کامپیوتر

ماتریس مجاورت

ماتریس وقوع

لیست مجاورت

این فایل همچنین حاوی مثال های حل شده متعددی نیز می باشد.

ترجمه مقاله Parallel Processing of large graphs

اختصاصی از فی دوو ترجمه مقاله Parallel Processing of large graphs دانلود با لینک مستقیم و پر سرعت .

عنوان انگلیسی :  Parallel Processing of large graphs

 عنوان فارسی : پردازش موازی گراف های بزرگ

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

09358978227 - خانم زمانی

Abstract

More and more large data collections are gathered worldwide in various IT systems. Many of them possess a networked nature and need to be processed and analysed as graph structures. Due to their size they very often require the usage of a parallel paradigm for efficient computation. Three parallel techniques have been compared in the paper: MapReduce, its map-side join extension and Bulk Synchronous Parallel (BSP). They are implemented for two different graph problems: calculation of single source shortest paths (SSSP) and collective classification of graph nodes by means of relational influence propagation (RIP). The methods and algorithms are applied to several network datasets differing in size and structural profile, originating from three domains: telecommunication, multimedia and microblog. The results revealed that iterative graph processing with the BSP implementation always and significantly, even up to 10 times outperforms MapReduce, especially for algorithms with many iterations and sparse communication. The extension of MapReduce based on map-side join is usually characterized by better efficiency compared to its origin, although not as much as BSP. Nevertheless, MapReduce still remains a good alternative for enormous networks, whose data structures do not fit in local memories

 تعداد صفحات انگلیسی : 14 صفحه

 

 

چکیده

امروزه مجموعه داده‌های بزرگ و بزرگتری در سیستم‌های IT مختلف سرتاسرجهان جمع آوری می‌شود. بسیاری از آنها، یک ذات شبکه بندی شدی را پردازش کرده و نیاز به پردازش و تحلیل به عنوان ساختارهای گراف دارند. به دلیل اندازه آنها، اغلب استفاده از طرجی موازی برای محاسبه کارآمد مورد نیاز است. سه تکنیک موازی سازی در این مقاله مقایسه شده‌اند:MapReduce، گسترش آن در اتصال سمت نگاشت و موازی سازی همگام انبوه (BSP). این تکنیک‌ها برای دومسئله گراف مختلف پیاده سازی شده‌اند: محاسبه کوتاهترین مسیرها از یک مبدا (SSSP) و دسته بندی انبوه گره‌های گراف با استفاده از انتشار تاثیر نسبی (RIP). روش‌ها و الگوریتم‌ها به داده‌های شبکه متعددی با اندازه و پروفایل ساختاری مختلف اعمال شده‌اند که از سه دامنه نشأت می‌گیرند: ارتباط راه دور، رسانه و میکرووبلاگ. نتایج نشان داده‌اند که پردازش تکرارشونده گراف با پیاده سازی BSP همیشه و به طور قابل توجهی حتی تا 10 برابر و به خصوص برای الگوریتم‌هایی با تکرار زیاد و ارتباطات تنک، بهتر ازMapReduce است. گسترش MapReduce برپایه اتصال سمت نگاشت معمولا کارآیی بهتری در مقایسه با الگوریتم اصلی دارد، اگرچه به‌اندازه BSP نمی‌باشد. با این حال، MapReduce همچنان برای شبکه‌های حجیم که ساختارداده آنها در حافظه محلی جای نمی‌گیرد، جایگزینی مناسب است.

1-مقدمه

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

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

تعداد صفحات ترجمه فارسی : 40 صفحه

تاثیر عوامل تاثیرگذار بر تحلیل پایداری شیبهای خاکی بر مبنای تئوری گراف

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

عنوان مقاله :  تاثیر عوامل تاثیرگذار بر تحلیل پایداری شیبهای خاکی بر مبنای تئوری گراف

 محل انتشار:نهمین کنگره ملی مهندسی عمران مشهد

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

نوع فایل : pdf

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

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

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

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

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

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

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

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

شامل 70 صفحه فایل word

مقاله ترکیبیات و نظریة گراف

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

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

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

تعداد صفحه:26

 فهرست مطالب

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

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

1-ترکیبات :

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

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

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

                                                                

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

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

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

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

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

                                                                

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

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

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

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

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

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

 

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

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

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

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

1) حکم را برای یک پایة دلخواه(که معمولاً کوچک باشد) ثابت کنیم.

2) حکم را برای یک k دلخواه فرض می‌گیریم.

3) به کمک قسمت 2 حکم را برای  ثابت می‌کنیم.