Loading...

پاورپوینت درخت ها در نظریه گراف 42 اسلاید

پاورپوینت درخت ها در نظریه گراف 42 اسلاید (pptx) 42 اسلاید


دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

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

قسمتی از متن PowerPoint (.pptx) :

بسم الله الرحمن الرحیم درخت ها 3-1- درختها و جنگلها گراف همبندی كه فاقد مدار باشد ، درخت نامیده میشود . به طوری كه از این تعریف نتیجه میشود در درخت یالهای چندگانه وجود ندارد و هر دو راس ان را میتوان با مسیر منحصر به فردی به یكدیگر وصل كرد . مولفه های همبند گرافهایی كه فاقد مدار باشند درخت اند : بنابراین طبیعی است كه هر چنان گرافی را جنگل مینامیم . برای ساختن یك درخت راس بخصوصی مثلآ a 0 ،را اختیار كنید از a 0 یالهایی به راسهای مجاور a 1 ، a 2 ،...... رسم كنید : از این راسها چنانكه در شكل 1.3 نشان داده شده است ، یالهایی به راسهای مجاور انها : یعنی a 11 ، a 12 ، ..... a 21 ، a 22 ،.....و غیره ، رسم كنید . راس بخصوص a 0 كه در شكل 1.3 انتخاب كرده ایم ، به ریشه درخت مربوطه مرسوم است : توجه كنید كه هر راسی را میتوانستیم به عنوان ریشه انتخاب كنیم . چون درخت فاقد مدار است ، مسیرها (یا شاخه ها) ی متفاوتی كه از a 0 منشعب شده اند ، راس مشترك دیگری ندارند ، یعنی مانند شاخه های درختان معمولی از هم جدا هستند . هر شاخه درخت یالی پایانی ، منتهی به رأسی پایانی ، كه از آن یال دیگری منشعب نمی شود ، دارد . شکل 3-1 با توجه به این نكته ، میتوان درخت را با اویزان كردن مبوالی یالها به راسها ساخت . بنابراین میتوان تعداد یالهای درخت را تعیین كرد . ساده ترین درخت درختی است كه فقط یك راس داشته باشد : چنین درختی فاقد یال است . هر بار كه یالی به انتهای شاخه ای افزوده شود ، راسی نیز به درخت افزوده میشود .بنابراین نتیجه میگیریم : قضیه 1.3 هر درخت با n راس دارای n-1 یال است . به جای درخت می توانستیم جنگلی با مولفه همبند را، كه همگی درخت هستند ، در نظر بگیریم ( شكل 3-2 ) . تعداد یالها در هر درخت مؤلفه یكی از تعداد راسها است بنابراین داریم : شکل 3-2 قضیه 3. 2 جنگلی كه n راس و k مولفه داشته باشد ، دارای n-k یال است . درختها كاربردهای زیادی در زمینه های گوناگون دارند ، از شیمی گرفته تا زبان شناسی و محاسبات كامپیوتری .در اینجا فقط به ذكر این نكته اكتفا می كنیم كه هر فرایند مرتب سازی یا جدا سازی را می توان به صورت درخت نشان داد .به عنوان مثال ، شكل 3. 1 را می توان تصویر یك جدا سازی پستی به حساب آورد .ابتدا توده ای از نامه ها در . a قرارداده می شود .نامه های داخلی را می توان در a 1 قرار داد ، نامه های ویژه اروپا رادر a 2 ، نامه های ویژه خاور را در ‌ a 3 و الی آخر .سپس نامه های داخلی در a 1 را می توان به سه دسته ی نامه های خاوری ، باختری و مركزی تفكیك كرد نامه های ویژه اروپا در a 2 را می توان ر حسب كشورها تفكیك كرد ، و الی آخر . طبقه بندی كتابها به روش دهدهی دیوئی را ( كه در كتابخانه ها به كار می رود )می توان به كمك گراف نشان داد ، ‌ با این تفاوت كه در اینجا گراف مربوطه شكلی تقریباٌ ‌ منتظم به خود می گیرد .وقتی كتابها را برحسب 10طبقه ی اصلی (علوم محض ، علوم كاربردی ، ...) جدا كنیم ، 10امكان دارد ، a 1 a o ، a 9 . . . به ازای هر یك از اینها نیز 10امكان دیگر ، مثلاٌ a 00 ، a 01 ، . . . ، a 9 وجود دارد ؛ و الی آخر ( به شكل 3. 3نگاه كنید ) .كل این فرایند را می توان تفكیك عددهای از 0تا 999بر حسب رقمهای اول ، دوم و غیره به حساب آورد. در واقع ، هر درختی را می توان نوعی دستگاه عددی بسیار كلی دانست . شکل 3-3 3 - 2 - مدارها و درختها اجازه دهید مسأله بعدی خود را به زبان كشاورزی عنوان كنیم .در شكل 3. 4 نقشه ای از مزرعه های كشاورزی را رسم كرده ایم .این نقشه را به عنوان نقشه ی تعدادی مزرعه ی برنج در یك جزیره در نظر می گیریم ؛این مزرعه با پشته هایی خاكی محصور شده اند و این پشته ها نیز در آبهای دریاچه ای محصورند . چنانكه در كشت برنج معمول است می خواهیم با باز كردن آبراهه هایی در برخی از پشته ها همه مزرعه را آبیاری كنیم .بدیهی است ، برای اینكه همه ی مزرعه آبیاری شوند ، بایستی در هر مدارنقشه ی فوق حداقل یك پشته را باز كرد ، یعنی آبراهه ای در آن ایجاد كرد .به این ترتیب پشته های باز نشده ی باقیمانده بایستی تشكیل گرافی بدون مدار دهند .حال پرسش این است : چه تعداد از پشته ها بایستی باز شوند ؟ از این پرسش به مسأله ای عمومی در مورد گرافها می رسیم :برای اینكه در گراف هم ب ندی مداری باقی نماند ، حداقل تعداد یالهایی كه باید حذف كرد چقدر است ؟ شکل 3-4 فرض كنید كه نخست یالی مثلاٌ ‌ e=ab ، متعلق به مداری از گراف ، ‌ را حذف كنیم در این صورت گراف باقیمانده باز همبند است .زیرا ، به جای رفتن از a به b در طول e می توانیم از قسمت باقیمانده ی مدار استفاده كنیم اگر پس از حذف e باز هم مداری موجود باشد به همین ترتیب یالی دیگر را حذف می كنیم .با تكرار این عمل بالاخره بایستی به گراف همبند بدون مداری ؛ ‌ درختی مانند T ، برسیم. (توجه كنید كه با حذف یالهای متفاوت معمولاٌ درختهای متفاوتی به دست می آید .

نظرات کاربران

نظرتان را ارسال کنید

captcha

فایل های دیگر این دسته