پاورپوینت نظریه متروید در گراف در 57 اسلاید

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

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

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

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

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

بسم الله الرحمن الرحیم نظریه متروید بعضی از نتایج در نظریه گرافها با احکام نظیر خود در نظریه ترنسورسال شباهت غیر منتظره ای دارند ، برای انجام این کار مناسب است که ابتدا مفهوم متروید که اولین بار در سال 1935 توسط وتینی مطرح شد ، معرفی شود . یک متروید اساسا یک مجموعه همراه با یک ساختار مستقل روی آن است به طوری که مفهوم استقلال ، هم استقلال در گرافها و هم استقلال در فضاهای برداری را تعمیم می دهد . در بخش 8-3 دوگان به گونه ای تعریف می شود که شباهت بین خواص مدارها و مجموعه های برش در گرافها را تشریح می کند . در این صورت دوگان مجرد یک گراف ، که در بخش 5-4به صورت نسبتا غیر شهودی تعریف شد ، نتیجه طبیعی دوگان ماترویدهاست . در بخش پایانی ، به کمک ماتروید ها ، اثباتهای ساده بعضی از احکام در نظریه ترنسورسال ارائه می شود ، و در پایان دو نتیجه اساسی در نظریه گرافها را با روش ماترویدها ثابت می کنیم . در این فصل بعضی از احکام را بدون برهان ارائه می کنیم . این برهانها در ولش وجود دارد . درآمدی بر مترویدها در بخش 4-1 درخت فراگیر را در یک گراف همبند ، به صورت زیر گرافی از G تعریف کردیم که مدار ندارد و از تمام رئوس می گذرد . روشن است که هیچ درخت فراگیری نمی تواند زیر گراف حقیقی درخت فراگیر دیگری باشد . همچنین می توان نشان داد که اگر B 1 و B 2 درختهای فراگیر G و e یالی از B 1 باشند ، می توان یال f را در B 2 پیدا کرد به طوری که { f } U ( { e }- B 1 ) (یعنی ، گرافی که از B 1 ، با تعویض e با f به دست می آید) نیز یک درخت فراگیر G باشد . احکام مشابهی در نظریه فضاهای برداری و نظریه ترنسورسال وجود دارد . اگر V یک فضای برداری و B 1 و B 2 پایه های V باشند ، آنگاه به ازای هر عضو e از B 1 ، عنصری مانند f از B 2 وجود دارد به طوری که { f } U ( { e }- B 1 ) نیز پایه V است . متروید M عبارت است از زوج ( β (E , ، که در آن E یک مجموعه متناهی ناتهی است و β خانواده ای ناتهی از زیر مجموعه های E (به نام پایه) است که دارای خواص زیر است : (1 β ) هیچ پایه ای زیر مجموعه حقیقی پایه دیگری نیست ؛ (2 β ) اگر B 1 و B 2 دو پایه باشند ، و e عنصری از B 1 ، آنگاه عنصری مانند f در B 2 هست به طوری که { f } U ( { e }- B 1 ) نیز یک پایه است . با استفاده مکرر از خاصیت ( β 2 ) ، به عنوان تمرینی سز راست ، می توان نشان داد که تعداد عناصر هر دو پایه متروید M ، برابر هستند ، این تعداد را رتبه M می نامند . به طور طبیعی ، به هر زیر گراف G می توان یک متروید نسبت داد ، E را مجموعه یالهای G و پایه ها را یالهای جنگلهای فراگیر G می گیریم ؛ این متروید را متروید مدار G می گویند و با M(G) نشان می دهند . به همین نحو ، اگر E ، یک مجموعه متناهی از بردارها در یک فضای برداری V باشد ، می توان روی E یک متروید تعریف کرد ، مترویدی که پایه های آن تمام زیر مجموعه های مستقل E ، که E را تولید می کنند ، هستند ؛ مترویدی را که بدین ترتیب به دست می آید یک متروید بردار می گویند . هر زیر مجموعه ای از E را که بخشی از یک پایه M باشد ، مستقل می گویند . بنابراین پایه های M به طور دقیق مجموعه های مستقل ماکسیمال هستند (یعنی ، مجموعه های مستقلی که جزء مجموعه مستقل دیگری نیستند) . بنابراین هر مترویدی ، به صورت منحصر به فرد ، توسط مجموعه های مستقل خود معین می شود . در یک متروید بردار ، زیر مجموعه ای از E را مستقل گویند ، اگر و فقط اگر ، به عنوان بردارهای فضای برداری ، مستقل خطی باشند . به همین نحو ، اگر G یک گراف باشد ، زیر مجموعه های مستقل M(G) ، مجموعه هایی از یالهای G هستند که مدار ندارند – به عبارت دیگر مجموعه – یالهای جنگلهایی که بخشی از G هستند . چون هر متروید را می توان با فهرست مجموعه های مستقل آن ، به طور دقیق مشخص کرد ، این سوال پیش می آید که آیا می شود متروید را برحسب مجموعه های مستقل ، به صورت ساده ای تعریف کرد . چنین تعریفی اکنون ارائه می شود ؛ اثبات معادل بودن این تعریف با تعریف فوق در ولش آمده است . متروید M عبارت است از زوج (E , ) ، که در آن E یک مجموعه متناهی ناتهی است ، و *** خانواده ی ناتهی از زیر مجموعه های E (مجموعه مستقل) است که دارای خواص زیر است ؛ (1 ) هر زیر مجموعه از یک مجموعه مستقل ، مستقل است ؛ (2 ) اگر I و J مجموعه های مستقلی باشند بطوری که | J | > | I | ، آنگاه عنصری مانند e از J وجود دارد که در I نیست ، و { e } U I مستقل است . (توجه دارید که با این تعریف ، یک پایه عبارت است از یک مجموعه مستقل ماکسیمال . با استفاده مکرر از خاصیت (2 ) می توان نشان داد که هر مجموعه مستقل را می توان به یک پایه توسعه داد .) اگر متروید M = ( E , ) بر حسب مجموعه های مستقل تعریف شده باشد ، هرزیر مجموعه از E را که مستقل نباشد ، وابسته می گویند ؛ در این صورت هرمجموعه وابسته می نیمال یک مدار است . توجه دارید که اگر M(G) متروید مدار گراف G باشد ، آنگاه مدارهای M(G) ، دقیقا ، مدارهای G هستند . چون هر زیر مجموعه ای از E مستقل است اگر و فقط اگر شامل مدار نباشد ، هر متروید را می توان بر حسب مدارهایش تعریف کرد . قبل از این که مثالهایی از متروید ها ارائه شود ، مناسب است که تعریف دیگری برای متروید داده شود . این تعریف که برحسب تابع رتبه ρ است ، در کار حقیقی با ارزش ویتنی در سال 1935 طرح شد . اگر متروید M={E , } برحسب مجموعه های مستقل تعریف شده باشد ، و اگر A زیر مجموعه ای از E باشد ، آنگاه اندازه بزرگترین مجموعه مستقلی را که در A وجود دارد ، رتبه A می گویند و آن را با (A) ρ نشان می دهند . توجه دارید که در این صورت تعریف قبلی رتبه M ، برابر (E) ρ است . از آنجا که زیر مجموعه A از E مستقل است اگر و فقط اگر A)=| A | ) ρ ، می توان متروید را برحسب تابع رتبه تعریف کرد . قضیه (8-1-الف) هر متروید را می توان به صورت زوج E , ρ ) ) تعریف کرد ، که در آن E یک مجموعه متناهی ناتهی است ، و ρ یک تابع با مقادیر صحیح است که روی زیر مجموعه های E تعریف شده ، است به طوری که ؛