دانلود کتاب آشنایی با نظریه گراف | 20 میشم

 

فایل مورد نظردر قالب pdf  با حجم 4.6 مگابایت می باشد. دوستان گرامی و دانشجویان ارجمند و عزیز در صورت تمایل می توانید این فایل بسیار با ارزش را به صورت مستقیم از سایت بیست میشم تهیه بفرمائید.

 

 

 

دانلود کتاب آشنایی با نظریه گراف | 20 میشم

 

درباره نظریه گراف

دانلود کتاب آشنایی با نظریه گراف | 20 میشم بیان دارد نظریه گراف (Graph theory) شاخه‌ای از ریاضیات است که دربارهٔ گراف‌ها بحث می‌کند.

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

در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضای آن به طریقی به هم مرتبط هستند.

اعضای این مجموعه می‌توانند انسان باشند و ارتباط آن‌ها با هم دست دادن باشد.

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

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

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

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

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

شیمی، زیست‌شناسی، علوم اجتماعی و سایر زمینه‌ها گردیده است.

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

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

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

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

مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست.

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

از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود.

باتوجه به دانلود کتاب آشنایی با نظریه گراف | 20 میشم ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش در آورد. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد.

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

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

مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست.

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

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

 

 

دانلود کتاب آشنایی با نظریه گراف | 20 میشم

 

 

اندازه گراف

درجه راس‌ها

کاربردها

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

در واقع انواع یال‌هایی که یک گراف دارد، یکی از بزرگ‌ترین و بدیهی‌ترین تفاوت‌های بین یک گراف با گراف دیگر است.

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

در یک یال جهت‌دار، دو گره به روشی بسیار خاص به هم متصل می‌شوند.

در اغلب موارد گره آغاز جهت را به نام مبدأ و گره انتهای یال را گره مقصد می‌نامند. در یک یال جهت‌دار تنها می‌توان از گره مبدأ به مقصد حرکت کرد و پیمایش مسیر معکوس هرگز ممکن نیست.

با این وجود، یال‌های غیر جهت‌دار روش کاملاً متفاوتی دارند. در یک یال غیر جهت‌دار، مسیر بین دو گره دوطرفه است.

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

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

گراف را یک گراف جهت‌دار (برخی اوقات digraph) می‌نامیم. اگر همه یال‌ها در یک گراف غیر جهت‌دار باشند، این گراف را همان طور که احتمالاً حدس می‌زنید یک گراف غیر جهت‌دار می‌نامیم.

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

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

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

زمانی که دانشمندان رایانه از نظریه گراف در کدهای خود استفاده کردند و در نهایت آن را به صورت یک ساختمان داده پیاده‌سازی کردند، چیزهای زیادی را تغییر ندادند.

بنابراین اصطلاح‌های زیادی که امروزه برای توصیف و پیاده‌سازی گراف‌ها استفاده می‌کنیم، دقیقاً اصطلاح‌هایی هستند که ریاضیدان‌ها برای اشاره به نظریه گراف مورد استفاده قرار می‌دهند.

برای نمونه بر اساس اصطلاح‌های ریاضیاتی، گراف را به صورت زوج‌های مرتب توصیف می‌کنیم.

اگر از جبر دبیرستانی به خاطر داشته باشید، زوج‌های مرتب را هنگام یادگیری مختصات زوج مرتب (x,y) یاد گرفته‌ایم.

در این جا نیز مفهوم مشابهی استفاده می‌شود و تنها یک تفاوت وجود دارد و آن این است در گراف به جای x و y از v برای رأس‌ها و از e برای یال‌ها استفاده می‌شود.

تعریف رسمی ریاضیاتی یک گراف چنین است: (G = (V, E

لحظه‌ای صبر کنید. چه می‌شود اگر گراف‌های ما بیش از یک گره و بیش از یک یال داشته باشند.

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

 

 

 

دانلود کتاب آشنایی با نظریه گراف | 20 میشم

 

 

گراف‌های کاملاً اجتماعی

در دانلود کتاب آشنایی با نظریه گراف | 20 میشم مطالعه میشود که گراف‌ها همه جا در پیرامون ما حضور دارند؛ اما ممکن است در اکثر موارد نتوانیم آن‌ها را ببینیم.

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

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

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

برخی اوقات نیز یال‌های گراف ما جهت‌دار هستند، یعنی تنها از صفحه وب A می‌توانیم به صفحه وب B برویم و نمی‌توانیم به عقب بازگردیم.

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

فیسبوک به عنوان یک شبکه عظیم اجتماعی، نوعی گراف است.

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

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

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

 

 

دانلود کتاب آشنایی با نظریه گراف | 20 میشم

 

 

آیا می‌توانید حدس بزنید فیسبوک چه نوع گرافی را پیاده‌سازی کرده است؟

دانلود کتاب آشنایی با نظریه گراف | 20 میشم اذعان دارد روابط در فیسبوک دوطرفه هستند و اگر روابط دوستی را در فیسبوک به صورت یک گراف تعریف کنیم، یال‌های آن همگی به صورت زوج‌های نامرتب هستند. از سوی دیگر طرز کار توییتر کاملاً از فیسبوک متفاوت است. در توییتر فردی می‌تواند فرد دیگر را فالو کند؛ اما فرد دوم می‌تواند وی را فالو نکند.

توییتر را می‌توان به صوت یک گراف جهت‌دار نمایش داد. هر یال که ایجاد می‌شود یک رابطه یک‌طرفه را نمایش می‌دهد.

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

 

 

 

دانلود کتاب آشنایی با نظریه گراف | 20 میشم

 

 

اصل لانه کبوتری

بنابر تعریف دانلود کتاب آشنایی با نظریه گراف | 20 میشم اصلی ساده در ترکیبات است که بسیاری از مسائل با آن حل می‌شوند و صورت آن به شرح زیر است:

اصل لانه کبوتری: اگر مروارید را در داخل k جعبه بگذاریم حتماً‌ جعبه‌ای وجود دارد که حداقل عدد مروارید در آن می‌باشد.
یکی از مثالهای ساده و زیبای این اصل سئوال زیر است:
در جمعی n نفر حضور دارند بعضی از اشخاص این جمع با هم دست می‌دهند ثابت کنید این جمع دو نفر وجود دارند که با تعداد برابر دست داده‌اند.

اثبات: هر نفر می‌تواند با ۰ تا n-1 نفر دست دهد حال اگر فردی باشد که با همه دست داده باشد آنگاه فردی نیست که با کسی دست نداده باشد و بالعکس بنابراین در این جمع هیچکاه دو نفر وجود ندارد که یکی با ۰ و دیگری با n-1 نفر دست داده باشد.

حال فرض کنیم هیچ شخصی وجود نداشته باشد که به تعداد برابری دست داده باشند و چون تعداد این دست دادنها از ۰ تا n-1 است
( کلاً n عدد) پس هم باید ۰ بیاید و هم n-1 که این خلاف گفته‌های بالا می‌باشد.

 

4,000 تومان – افزودن به سبد خرید نهایی کردن خرید مورد به سبد خرید اضافه شد