X
تبلیغات
وبلاگ ریاضی ورودی 86 دانشگاه شیراز - Graph Teory(نظريه گراف)
 سلام

برای دانلود کتاب نظریه گراف لینک زیر را کلیک کنید

دانلود کتاب نظریه گراف باندی و مورتی 2007

+ نوشته شده توسط حسین اسماعیلیان در شنبه 1389/07/10 و ساعت 4:59 بعد از ظهر |

سؤال. يك گراف ساده ي nیالی(nعددی طبیعی است)جادويي نامند  اگر بتوان يالهايش را با اعداد n‚...21

به گونهاي برچسبگذاري نمود كه:

الف) هر يك از اعداد n‚...21دقيقا يك بار استفاده شود،

ب) مجموع برچسبهاي يالها در هر راس مساوي باشد.

 آيا يك گراف جادويي با 2010 مؤلفه وجود دارد؟

توجه:

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

اگر گراف ما ناهمبند باشد گوییم گراف ما mمولفه ای است(mتعداد گرافهای همبندی است که گراف ناهمبند را تشکیل داده اند)

+ نوشته شده توسط حسین اسماعیلیان در یکشنبه 1389/03/16 و ساعت 4:52 بعد از ظهر |
گراف مور

طول کوتاه ترین دور در یک گراف، کمر گراف نامیده می شود که با نماد (γ(G نشان داده می شود. به عنوان مثال مکعب کمر به طول ۴ دارد. برای گراف های kمنظم و با طول کمر ثابت معمولا ویژگی های جالبی دارند. به عنوان مثال گراف G را یک گراف k منتظم با طول کمر ۴ چهار باشد اگرهر کدام از راس های u گراف G را درنظر بگیریم k راس با فاصله یک از آن راس وجود دارد. از آنجا که گراف G هیچ مثلثی ندارد حداقل k-۱ راس با فاصله دو از u وجود دارند.


Moore graph Pic1.jpg


بنابراین داریم، G|≥۱+k+(k-۱)=۲k| و (|G| برابر با تعداد رئوس گراف است) فقط یک گراف با ویژگی G|=۲k| وجود دارد و این و این همان گراف کامل دو بخشی Kk,k است.و حال اگر G گراف k منتظم با کمر پنج باشد و u هر یک از رئوس گراف باشد، k راس با فاصله یک از u وجود دارد به طوری که؛ G|≥۱+k+k(k-۱)=K۲|


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

گرافی است k منتظم با طول کمر پنج، به طوری که G|=K۲+۱| . فرض کنیم |n = |G . یک گراف ۱ منتظم نمی تواند کمر به طول ۵ داشته باشد. پس باید k≥۲ . اگر k =۲ پس n=۲۲+۱ = ۵. G یک دور به طول پنج دارد پس این تنها گراف مور با درجه ۲.

اگر k=۳ پس n=۳۲+۱=۱۰.

پس ۳ راس با فاصله یک از هر راس u وجود دارد و ۶ راس با فاصله ۲ وجود دارد که در شکل زیر نشان داده شده است.


Moore graph Pic2.jpg


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

به بیان دیگر گراف مور، یک گراف با درجه k و قطر d است که تعداد رئوس آن با حد بالای

1+d\sum_{i=0}^{k-1}(d-1)^i .

برابر باشد.


قضیه‎های در مورد گراف مور

گراف پترسون

گراف پترسون تنها گراف مور با درجه ۳ است.


 قضیه هافمن-سینگلتون

یک گراف مور فقط با درجه k=۲, ۳, ۷ , ۵۷ است.


اثبات : در مرجع ۱


لازم به توضیح است که گراف مور با درجه ۳ همان گراف پترسون است و گراف با درجه ۷ همان گراف هافمن-سینگلتون (Hoffman-Singleton Graph) است. البته وجود گراف مور با درجه ۵ با قضیه ثابت نشده است و حدس هایی در مورد وجود آن زده است. در هر حال پیدا کردن گراف مور با درجه ۵ و ۵۷ از مسائل حل نشده نظریه گراف است. محدود کردن تعداد رئوس با درجه و قطر: فرض کنیم گراف G و فرض کنیم درجه آن k و قطر آن d و درخت جستجوی نخستین پهنا (BFS Breadth First Search)آن را در نظر می گیریم که از هر کدام از رئوس دلخواه v آن را آغاز می کنیم . این درخت یک راس با درجه ۰ (راس آغازی شروع گراف) دارد و حداکثر k راس با درجه ۱ دارد (رئوس مجاور راس مبدا). در سطح بعد حداکثر (k(k-۱ راس داریم. هر راس مجاور v از یکی از همسایه های v برای اتصال به v استفاده می کنند بنا براین حداکثر k-۱ همسایه در سطح ۲ داریم. در کل برای هر سطح i بین ۱ تا k حداکثر k(k-۱)i راس وجود دارد. پس تعداد کل رئوس در کل

1+d\sum_{i=0}^{k-1}(d-1)^i.

است.


 استفاده از گراف مور به عنوان قفس(ادامه مطلب رو ببینید )


ادامه مطلب
+ نوشته شده توسط حسین اسماعیلیان در پنجشنبه 1389/03/13 و ساعت 10:34 بعد از ظهر |
گراف هی وود

گراف پترسن

گراف کنزر(Kneser)

گراف‌های n- بعدی

Sephirot

ماز همپتون

توضیحات این گرافها رو در ادامه مطلب بخونین


ادامه مطلب
+ نوشته شده توسط حسین اسماعیلیان در پنجشنبه 1389/03/13 و ساعت 10:31 بعد از ظهر |
حدس اردوس-فابر-لوواز (به انگلیسی: Erdős–Faber–Lovász conjecture) یک مسئله بسیار عمیق و مهم در بحث رنگ آمیزی گراف‌ها در نظریه گراف‌ها است.

این نظریه بیان می‌کند که: اجتماع k کپی از k دسته که هر ۲ دستهٔ متمایز دلخواه حداکثر در یک راس اشتراک دارند دارای عدد رنگی k است. حداد و تاردیف در سال ۲۰۰۴ این نظریه را به بیان دیگری و با مطرح کردن یک مثال از کمیته‌های موجود در دانشگاه ارایه کردند : فرض کنید در یک دانشکدهٔ دانشگاه k کمیـته وجود دارد و هر کـدام هم شامـل k نفر از اعضای هیئت علمی هستند و قرار است که همهٔ کمیته‌ها در یک اتاق با هم جلسه داشته باشند که در اتــاق k صندلی وجود دارد. همچنین فرض کنید که اشــتراک هر ۲ کمــیتهٔ متمایز دلخواه شامل ۱ نفر می‌شود. آیا ممکن است که اعضای کمیته‌ها را به صندلی‌هایی نسبت دهیم به طوری که هـر عضو در همه کمیته‌هایی که عضو آنها است روی صندلی ثابتی بنشیند؟ پاول اردوس ابتداً مبلغ ۵۰ دلار (دلار آمریکا) برای اثبات این حدس به عنوان جایزه قرار داده بود ولی بعداً آنرا به مبلغ ۵۰۰ دلار افزایش داد. بهترین نتیجهٔ یافته شده تا به امروز ایناست که عدد رنگی این مسئله حداکثر k + o(k) است. اگر مسئله را راحتتر و با شرایط کمتری در نظر بگیریم، بدین صورت که اجازه ئهیم دسته‌ها در هر چند راسی که می‌خواهند، اشتراک داشته باشند؛ آنگاه عدد رنگی این نوع گرافها حداکثر 1 + k \sqrt{k - 1} خواهد شد.


ادامه مطلب
+ نوشته شده توسط حسین اسماعیلیان در پنجشنبه 1389/03/13 و ساعت 10:20 بعد از ظهر |
مجارستان ؛ زادگاه پال اردوش ؛ مهد نابغه های ریاضی

مجارستان ؛ زادگاه پال اردوش ؛ مهد نابغه های ریاضی

 

تقدیم به دکتر رجالی به مناسبت دریافت جایزه جهانی اردوش 2006

  پال اردوش در سال 1913 میلادی در مجارستان متولد شد و در سال 1996 در همانجا در گذشت . اردوش جوینده ای خستگی ناپذیر بود و مسائل پیکار جوی بسیاری را در ریاضیات پیش روی پژوهشگران بسیاری از کشورهای جهان قرار داد . اردوش 1500 مقاله و کتاب را به تنهایی یا با همکاری دیگران به رشته تحریر در آورده است و از این رو بیشتر از هر کسی در تاریخ ریاضیات با ریاضیدانان دیگر همکاری داشته است .

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

 از اوان نوجوانی پژوهش ریاضی را آغاز کرد .نخستین مقاله اش را در 18 سالگی نوشت و در آن اثباتی جدید برای یکی از قضیه های چبیشف ارائه داد .

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

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

 لواس ، پلیکان وماته از  دیگر نابغه های خردسال مجاری هستند که پال اردوش به آنها اشاره می کند . هر چند با این سه ، ارتباط کمتری داشت .

 وی می گوید :

 مایلم در باره ی علت این که این قدر نابغه خردسال در مجارستان زیاد است حدسهای خودم را بیان کنم :

 بیش از هر چیزئ ، این که انتشار نشریه های ریاضی ادواری ویژه ی دانش آموزان دبیرستانی دست کم حدود 80 سال قدمت دارد .

 (( اردوش این را 36 سال قبل گفته ))

 از این گذشته مسابقه های ریاضی بسیاری نظیر مسابقه اتووش _ کورشاک در مجارستان برگزار می شو دکه سابقه آن به سال 1895 بر می گردد. و همینطور سایر مسابقات معتبر ریاضی دبیرستانی که درمجارستان برگزار می شود مانند مسابقه شوتیز که بعد از جنگ جهانی دوم به راه افتاد .رسانه های عمومی مجارستان نیز توجه ویژه ای به این مقوله دارند و عده ی زیادی از مردم مجار با علاقه زیاد این مسابقات را پی می گیرند .

 

ریاضیدان مجاری ؛ ازنوشیدن قهوه تا تولید قضیه !

 پال می گوید :

 در مجارستان بسیاری از ریاضیدانان قهوه ی غلیظ می نوشند در حقیقت می توان گفت :  

« ریاضیدان ماشینی است که قهوه را به قضیه ها تبدیل می کند .»

 

در مؤسسه ریاضی قهوه ی خوبی درست می کنند ووقتی پوشا هنوز چهار ده سالش تمام نشده بود به او کمی قهوه غلیظ تعارف کردم 

  که  او با مقدار فراوانی شکر آن را نوشید . مادرم خیلی عصبانی شد که من به پسری در آن سن قهوه غلیظ داده ام . برای آرام کردن اوگفتم : پوشا می توانست بگوید «خانم ، من کار ریاضیدانها را انجام می دهم و نوشیدنی آنها را هم می نوشم . »

+ نوشته شده توسط حسین اسماعیلیان در شنبه 1388/10/26 و ساعت 5:28 بعد از ظهر |
قضیه رمزی(ramsey)

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

مثال

برای مثال

(r(x,۲)=x  r(۱,x)=۱  ۱=r(x,۱

 r(۴٬۵)=۲۵ r(۵٬۳)=۱۴ r(۴٬۴)=۱۸ r(۳٬۴)=۹ r(۳٬۳)=۶ عدد رمزی آخر در سال ۱۹۹۳ با استفاده از کامپیوتر بدست آمده.

تاریخچه

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

قضیه کران بالا

در این جا میخواهیم کران بالایی برای اعداد رمزی (r(k,l بیان کنیم: اگر k>۱ , l>۱ آنگاه:

           (r(k,l) >=  r(k,l-۱)  +  r(k-۱,l 

برهان:

فرض کنید g گرافی با (r(k,l-۱) + r(k-۱,l راس باشد. راس v را در نظر بگیرید صبق اصل لانه کبوتری v یا به (r(k-۱,l راس وصل است ویا به (r(k,l-۱ راس وصل نیست.

در صورتی که حالت اول بر قرار شود در این تعداد راس یا l راس مستقل اند ویا ۱-k راس خوشه‌اند واز آنجا که همه این رئوس به v وصل اند k-۱ راس به همراه k , v راس خوشه را تشکیل می‌دهند حکم مساله ثابت می‌شود.

و اگر حالت دوم بر قرار شود یا k راس خوشه پیدا می‌شود و یا l-۱ راس مستقل. واز آنجا که v به این رئوس وصا نیست l-۱ راس و l,v راس مستقل را تشکیل می‌دهد. و حکم ثابت می‌شود.

بیان مساله به صورت دیگر(حالت کلی):

اگر q1,q2,...,qn اعداد صحیح بزرگتر از 2 باشند آنگاه عددی مانند (r(q1,q2,...,qn وجود دارد به طوری که اگر p بزرگتر از (r(q1,q2,...,qn باشد و یال های گراف را با n رنگ (رنگ های 1 تا n) رنگ کنیم ,به ازای حداقل یک رنگ مانند i زیر گراف کامل qi راسی وجود دارد که یال هایش هم رنگ رنگ i ام است.

برای مثال r(3,3,3) = 17

+ نوشته شده توسط حسین اسماعیلیان در شنبه 1388/10/26 و ساعت 5:15 بعد از ظهر |

داستان پل هاي كونيگسبرگ را منشأ تولد نظريه گراف دانسته اند.

+ نوشته شده توسط حسین اسماعیلیان در پنجشنبه 1388/10/24 و ساعت 6:2 بعد از ظهر |
سیری در نظریه گراف
مقدمه:
اندک زمانی است که واژه گراف در ادبیات ریاضی وارد شده است، گرچه شروع آن را می توان از زمان لئناردو اویلر ریاضیدان سوئیسی (1707-1783) دانست. اما علاقه ی شدید و مداوم به نظریه ی گراف ، بعنوان شاخه ای از ریاضیات ، از سال 1930 به بعد، آشکار گردید و امروزه این نظریه یکی از پربارترین و محبوب ترین شاخه های ریاضیات و علوم کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در بسیاری از مسائل گسترده ی جامعه مدرن امروزی است.هنگامی که مساله ای به زبان گراف فرمول بندی شد، درک آن بسیار آسان تر خواهد شد. امروزه نظریه ی گراف یکی از موضوعات مهم دئر ریاضیات گسسته است. گرافها، مدل های راضی برای یک مجموعه گسسته هستند، که اعضای آن به طریقی با هم مرتبط می باشند. اعضای این مجموعه می توانند انسان ها یا رابطه ی خویشاوندی ، یا دوستی و باشد. اعضای این مجوعه می توانند، محل اتصالهای سیم های یک شبکه ی برق و رابطه ی آنها، سیم های واصل بین دو مقطه باشد و یا عناصر مجوعه می توانند اتم های یک مولکول و ارتباط آن ها، اتصالهای شیمیایی باشد. نظریه گراف ریشه در بازیها و معما ها نیز دارد، اما امروزه این نظریه نه تنها در ریاضیات بلکه در سایر علوم مانندا اقتصاد، روانشناسی،ژنتیک و باستان شناسی کاربرد فراوانی دارد.
مفهوم گراف:
واژه گراف، نه تنها در ریاضیات، بلکه در سایر علوم و حتی در زندگی روزانه به نام های گوناگون مانند طرح دیاگرام، نگاره، نقشه، ماز و بکار می رود. مثلا ممکن است به بهانه های مختلف شکلی رسم کنیم که از نقطه هایی تشکیل شده باشد و اگر چند نقطه، رابطه هایی با هم داشته باشند این روابط را با کشیدن خط بین آن ها نشان دهیم. نیز می توانیم تیم های ورزشی را در نظر بگیریم و آن ها را با نقاط A,B,C,… روی صفحه رسم کنیم و خطوط را با این شرط وصل کنیم که آن تیم ها با هم بازی داشته باشند، در ابتدا که بازی صورت نگرفته فقط چند نقطه داریم، ولی وقتی تیم ها باهم بازی کردند، بین تمام نقاط خط هایی وصل کنیم، بدین ترتیب یک گراف ساخته ایم، که با یک نگاه، راحت متوجه رابطه بین نقاط می شویم. بدیهی است که در انتخاب مکان نقاط در صفحه و طرز رسم کردن خطوط آزاد بوده ایم. اگر هیچ تیمی بازی نکرده باشد، هیچ خطی وصل نمی شود و در این صورت گراف، گراف صفحه نخواهد بود و اگر با هم بازی کنند، گراف کامل بوجود می آید.
قابل ذکر است که اگر نقاط را رئوس گراف و خطوط را یال بنامیم داریم: G(V.E) که آن را گراف G با رئوس V. و یال های E می نامیم.
اکنون به معرفی چند نوع گراف می پردازیم:
1) گراف های یکریخت: اگر در دو گراف، تعداد راس ها برابر بوده، بطوریکه هر دو راس متناظر، با یک حرف نام گذاری شده باشد، آن گاه وقتی دو راس بوسیله ی یالی بهم مربوط باشند، راس های هم نام آن ها در گراف دوم نیز بوسیله ی یالی بهم مربوط شوند.
2) گراف همبند و ناهمبند: اگر از هر دو راس دلخواه گراف، بتوان با حرکت روی یال ها، به راس دلخواه دیگر رسید، چنین گرافی همبند و در غیر این صورت ناهمبند است، یعنی گراف همبند از یک قطعه و ناهمبند از چند قطعه تشکیل می شود.
مرتبه، اندازه و درجه گراف:
به تعداد رئوس هر گراف مرتبه و به تعداد یالهای آن، اندازه و تعداد یال های منتهی به یک راس را درجه ی آن گراف گوییم.
بدیهی است که در گراف صفر درجه، هر راس برابر صفر است و در گراف کامل با n راس درجه، هر راس برابر با n-1 خواهد بود. راس هایی که درجه زوج دارند راس های زوج و راس هایی که درجه فرد دارند راس های فرد، نامیده می شوند. مساله حایز اهمیت این است که در هر گراف، تعداد رئوس فرد، زوج هستند، یعنی نمی توان گرافی رسم کرد که مثلا: 3 تا راس فرد داشته باشد. بعنوان مثال نمی توان گرافی رسم کرد که درجه راس های آن 5،0،2،2،5،8،7،6 باشد زیرا تعداد رئوس فرد 3 تا هستند یعنی(5،7،5)!
Boye_Gan2m is offline  
+ نوشته شده توسط حسین اسماعیلیان در شنبه 1388/07/04 و ساعت 1:19 بعد از ظهر |
اکثر ما تا حدودی با هندسه فراکتالی آشنا هستیم و آنها را شکلهای خود متشابه می دانیم. اما شاید بدانید که تعریف دقیق ریاضی آن چیز دیگری است و مطالب چندان ساده ای نیستند.

جالب است بدانید که نظریه گراف هم ارتباطاتی با هندسه فراکتال دارد !!و این  یکی از موضوعات مورد علاقه و تحقیقی من می باشد. به عنوان مثال فراکتال زیر مربوط به گراف ساده مسیر با ۳ راس P3 می باشد که من توانسته ام آنرا با نرم افزار ریاضی تولید کنم!

                fractal of p3  

توجه کنید که به راحتی می توان ثابت کرد که همه  فراکتال های گرافها فشرده هستند. و این موضوع هنوز در مورد همبندی کامل پاسخ داده نشده است!   

+ نوشته شده توسط حسین اسماعیلیان در دوشنبه 1388/05/19 و ساعت 8:33 بعد از ظهر |
ریاضیات گسسته و نظریه گراف

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


ادامه مطلب
+ نوشته شده توسط حسین اسماعیلیان در دوشنبه 1388/05/19 و ساعت 8:31 بعد از ظهر |
مفهوم شهودی:
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟
برای حل چنین مسئله ای که به مسئله ی تخصیص موسوم است، با استفاده از گراف می توان وضعیت های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه ای به نام Y قرار می دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال ها وصل می نماید.
به عبارت دیگر گراف بوجود امدی دارای یالهای xy است که مر متقاضی x را از مجموعه X به شغلهای مناسب y از مجموعه Y متصل می نماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X(متفاضیان) یا هیچ دو راس متعلق به مجموعه Y(مشاغل) توسط هیچ یالی به هم متصل نمی باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می گویند.


برای اطلاعات بیشتر به ادامه مطلب رجوع کنید


ادامه مطلب
+ نوشته شده توسط حسین اسماعیلیان در سه شنبه 1388/01/25 و ساعت 10:51 قبل از ظهر |
تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط شده‌اند.

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

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

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

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

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

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

+ نوشته شده توسط حسین اسماعیلیان در سه شنبه 1388/01/25 و ساعت 10:46 قبل از ظهر |
یک پستچی در راستای شغلش ، نامه‌ها را از پستخانه تحویل می‌گیرد. آنها را به صاحبان نامه تحویل می‌دهد و سپس یه پستخانه بر می‌گردد. البته ، او باید در ناحیه‌اش هر خیابان را حداقل یک بار بپیماید. با توجه به این شرط ، او مایل است مسیرش را به طریقی انتخاب کند که کمترین راه ممکن را طی کند. این مسئله به مسئله پستچی چینی معروف است. زیرا اولین بار  کوان ، ریاضیدان چینی (1962) آن را بررسی کرد. برای حل این مسئله بدیهی است که مسئله به یافتن مسیری با Min وزن در یک گراف همبند وزن دار با وزنهای نامنفی شباهت دارد. به این ترتیب که اگر گراف G را یک گراف اویلری در نظر بگیریم هر مسیری یک مسیر اپتیمال است، زیرا یک مسیر اویلری ، مسیری است که هر یال دقیقا یکبار طی می‌شود. مسئله پستچی به راحتی در این حالت حل می‌شود.

+ نوشته شده توسط حسین اسماعیلیان در سه شنبه 1388/01/25 و ساعت 10:29 قبل از ظهر |
فرض کنید به هر یال e ی گراف G عددی نسبت داده شده باشد، در این صورت عدد نسبت داده شده وزن هر سال و چنین گرافی را گراف وزن دار می‌نامیم. این اعداد تعبیرهای مختلفی در کاربردهای متفاوت می‌توانند داشته باشند، مثلا می‌تواند مقدار هزینه سفر از نقطه‌ای به نقطه دیگر یا معرفی مخارج ساختن یا نگهداری خطهای ارتباطی مختلف یا حتی بیانگر شدت دوستی بین دو فرد باشد. به عنوان مثال شبکه راه آهنی را تصور کنید شهرهای مختلف را به هم وصل می‌کند، هدف ما پیدا کردن مسیری با Min وزنی است که دو رأس را به هم وصل می کند که در اینجا وزنها معرف فاصله‌ها می‌باشند. الگوریتمی که به حل این مسئله می‌پردازد اولین بار توسط دیکسترا (1959) و بطور مستقل وایتینگ و هیلیه (1960) کشف کردند. این الگوریتم نه تنها کوتاهترین مسیر را می‌یابد بلکه کوتاهترین مسیر از به همه رأسهای گرا ف G را نیز پیدا می‌کند.

+ نوشته شده توسط حسین اسماعیلیان در سه شنبه 1388/01/25 و ساعت 10:25 قبل از ظهر |
درخت مولد گراف مانند G بزرگترین گراف درختی مانند T در G است که با افزودن یک یال از درخت بودن خارج می شود و واضح است اگر یک گراف n راس و m یال داشته باشد آن گاه درخت مولد n-1 یال داشته و باید m >= n-1 باشد.
تعداد درخت های مولد متمایز برای گراف کامل با n راس برابر است. این قضیه به قضیه کایلی معروف است.
تعداد درخت هایی که با n راس با درجات می توان ساخت برابر مقدار زیر است:

+ نوشته شده توسط حسین اسماعیلیان در سه شنبه 1388/01/25 و ساعت 10:22 قبل از ظهر |

گراف ها و درخت ها موضوعاتی ساده و در عین حال بسیار کاربردی در ریاضیات هستند. اینگونه که پیشرفت علوم نشان داده , این مباحث هنوز هم جا برای کار دارند و می توان کاربردهای جدیدی را برایشان تعریف کرد. با هم به نمونه های زیر توجه می کنیم.

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

در اين پست مطالب بيشتري را ذكر مي كنيم.

مشتاق نظرات سودمند شما هستيم 

+ نوشته شده توسط حسین اسماعیلیان در سه شنبه 1388/01/25 و ساعت 10:16 قبل از ظهر |