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

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


در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .
این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری می‌باشند حائز اهمیت فراوان می باشند .
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 زوج باشند .
حال می‌خواهیم یک مبحث مهم از ترکیبات به نام استقراء را معرفی کنیم.
استقراء بعنی رسیدن ازجزء به کل و هم ارز است با اصل خوشترتیبی زیر مجموعه‌ها( اصل خوشتربینی بیان می‌کند که هر مجموعه متناهی از اعداد عضوی به نام کوچکترین عضو دارد).
برای اثبات حکمی به کمک استقراء لازم است:
1) حکم را برای یک پایة دلخواه(که معمولاً کوچک باشد) ثابت کنیم.
2) حکم را برای یک k دلخواه فرض می‌گیریم.
3) به کمک قسمت 2 حکم را برای ثابت می‌کنیم.
بسیاری از گزاره‌ها به کمک این استقراء که در ظاهر ساده است ثابت می‌شود:
یک مثال ساده:
ثابت کنید: .
برای که داریم و حکم برقرار است:
فرض کنیم برای درست باشد حکم را برای ثابت می‌کنیم داریم:

که این قسمت طبق فرض بردار می‌باشد
و برای نیز حکم مسأله برقرار است.
یک مثال سخت:
این سئوال در المپیاد کامپیوتر امسال مطرح شده و ما فقط یک قسمت آنرا بطور خلاصه بیان می‌کنیم.
سئوال: در روز A دارای تعداد مجموعه می‌باشد بطوریکه هیچ مجموعه‌‌ای زیرمجموعة دیگری نیست یعنی اکر )
حل شایان در روز B می‌آید از روی مجموعه‌های A تمام مجموعه‌هایی را نمی‌سازیم که دارای دو شرط زیر می‌باشند:
1- هر مجموعه‌ای دلخواه در روز B با تمام مجموعه‌ها در روز A اشتراک دارد.
2-اگر از یک مجموعة دلخواه در روز B یک عضو را حذف کنیم آنگاه دیگر شرط 1 برقرار نباشد( که به این شرط، شرط مینیمالی می‌گوئیم:
حال فراز در روز C از روی مجموعه‌های B تمام مجموعه‌هایی با دو شرط بالا را می‌سازد ثابت کنید ( یعنی تمام مجموعه‌های روز اول در روز سوم نیز تولید شده‌اند)
اثبات: ابتدا لم زیر را ثابت می‌کنیم:
لم: به ازای هر مجموعة دلخواه در روز A مثل در روز B n تتا مجموعه وجود دارند بطوریکه هر کدام از آنها دقیقاً یکی از اعضای را دارند( ممکن است اعضای دیگری نیز داشته باشند ولی هر کدام دقیقاً یکی از را دارند.)
اثبات لم: با استقراء روی تعداد مجموعه‌های روز اول حکم را ثابت می‌کنیم. برای یک مجموعه در روز A وضعیت مجموعه‌ها در روزهای C,B,A مشخص شده‌اند:

خرید فایل

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

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


شبکه ها
1-1 شارش ها
شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.
تعریف 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 تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف را قید ظرفیت می‌نامند.
شرط دوم، شرط بقا نامیده می شود و ایجاب می کند که، مقدار کالایی که وارد رأس مانند v می شود با مقدار کالایی که از این رأس خارج می شود برابر باشد. این امر در مورد همة رأسها به استثنای مبدأ و مقصد بر قرار است.
مثال 1-2 در شبکه های شکل 1-2، نشان x,y روی کمانی مانند e به این ترتیب تعیین شده است که y , x=c(e) مقداری است که شارشی مانند f به این کمان نسبت داده است. نشان هر کمان مانند e در صدق می کند. در شکل 1-2 (الف)، شارش، وارد رأس می شود،5 است، ولی شارشی که از آن رأس خارج می شود 4=2+2 است. بنابراین، در این حالت تابع f نمی تواند یک شارش باشد. تابع f برای شکل 1-2 (ب) در هر دو شرط صدق می کند و بنابراین، شارشی برای شبکهء مفروض است.

فهرست مطالب
مقدمه
فصل 1
شبکه ها
1-1 شارش ها
1-2 برش ها
1-3 قضیه شارش ماکزیمم – برش مینیمم
1-4 قضیه منجر

فصل 2
تطابق ها
2-1 انطباق ها
2-2 تطابق ها و پوشش ها در گراف های دو بخش
2-3 تطابق کامل
2-4 مسأله تخصیص شغل

منابع

خرید فایل

تحقیق نظریه گراف و کاربردهای آن

              فرمت فایل : WORD + PPTتعداد صفحات:53 فهرست مطالب: عنوان ...........................................................صفحهفصل اول .............................................................................. 6مقدمه    7آشنایی با گراف ............................................................................................8یک ریختی گراف ها    9ماتریس وقوع . مجاورت    10زیر گراف ها    10درجه راس ها    12مسیرها    12دور ها    13مساله کوتاه ترین مسیر    15فصل دوم  .............................................................................................20درخت ها     21یال های برشی  و باندها.....&n ...

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

              فرمت فایل : WORD (قابل ویرایش)تعداد صفحات:48 فهرست مطالب: عنوان    صفحهمقدمه    فصل 1    شبکه ها    1-1 شارش ها    1-2 برش ها    1-3 قضیه شارش ماکزیمم – برش مینیمم    1-4 قضیه منجر        فصل 2    تطابق ها    2-1 انطباق ها    2-2 تطابق ها و پوشش ها در گراف های دو بخش    2-3 تطابق کامل    2-4 مسأله تخصبص شغل        منابع       شبکه ها1-1    شارش هاشبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان ب ...

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

              فرمت فایل : WORD (قابل ویرایش)تعداد صفحات:25 چکیده: در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم . این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری می‌باشند حائز اهمیت فراوان می باشند . 1-ترکیبات : شاید در نگاه اول ترکیبات یک بخش معماگونه و سطحی از ریاضیات به نظر برسد که دارای کاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می کند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد . ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم . سوال : یک اتاقی مشبک شده به طول 8 و عرض 8 داریم که خانه‌ی بالا سمت چپ و خانه‌ی پ ...

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

• رساله دکتری مهندسی عمران با عنوان: تحلیل خطی و غیرخطی سازه های پرعضو با استفاده از مفاهیم نظریه گراف ها، پردازش موازی و شبکه های عصبی مصنوعی • دانشگاه علم و صنعت ایران • استاد راهنما: پروفسور علی کاوه • پژوهشگر: علی داوران • سال انتشار: شهریور 1376 • فرمت فایل: PDF و شامل 236 صفحه چکیــــده: در این پایان نامه با بکارگیری مفاهیمی از نظریه گراف‌ها، پردازش موازی و شبکه‌های عصبی مصنوعی، روش‌هایی بر ...

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

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

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

• مقاله با عنوان: تاثیر عوامل تاثیرگذار بر تحلیل پایداری شیب های خاکی بر مبنای تئوری گراف   • نویسندگان: سعید غفارپور جهرمی ، فاطمه بداغی   • محل انتشار: نهمین کنگره ملی مهندسی عمران - دانشگاه فردوسی مشهد - 21 تا 22 اردیبهشت 95   • فرمت فایل: PDF و شامل 8 صفحه می باشد.       چکیــــده: روش تعادل محدود LEM و روش کاهش مقاومت SRM روش های پرکاربردی برای آنالیز پایداری شیب می باشد. اگرچه این نکته قابل توجه است که هردوی آن ها دارای محدودیت کاربرد عملی می باشند. روش تعادل محدود نمی تواند شامل مدل های ترکیبی باشد و فرض های بسیاری میان گره های خاک / سنگ نیاز می باشد. روش کاهش مقاومت به محاسبات مکرر نیاز دارد و سطح لغزش را مستقیما نمی دهد. روش آنالیز پایداری شیب برمبنای تئوری گراف اخیرا به محاسبه مستقیم حداقل ضریب ایمنی و سطح لغزش بحرانی بالق ...

تحقیق در مورد تحلیل مساله کوتاهترین مسیر در گراف جهت دار

لینک پرداخت و دانلود *پایین مطلب *   فرمت فایل :Word ( قابل ویرایش و آماده پرینت )    تعداد صفحه10   فهرست مطالب     تحلیل مساله کوتاهترین مسیر در گراف جهت دار یک ایده برنامه نویسی پویا : ضمایم: بهینه سازیهای مهم الگوریتم اگر G دورهای منفی نداشته باشد؛‍‍‍ پس کوتاهترین مسیر ساده از S به t وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1 یال دارد. اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P از s به t با بیشترین تعداد از یالها هیچ راس v را مرور نمی کند. اگر P ؛ راس v را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد. اجازه دهید OPT(i,v) را برای تفکیک کمترین هزینه یک مسیر v-t با استفاده از بی ...

اموزشگاه رانندگی گراف

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