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

توضیحات فایل «نظریه متروید در گراف در 57 اسلاید.pptx»

با تشکر از توجه شما به آسانی می توان نشان داد که اگر G یک گراف باشد ، آنگاه متروید مدار M(G) یک متروید دوتایی است . برای این منظور به هر یک از یالهای G ، سطر نظیر در ماتریس وقوع G را به عنوان برداری با مولفه های صفر یا یک نسبت می دهیم . توجه دارید که اگر مجموعه ای از یالهای G یک مدار تشکیل دهند ، مجموع (به پیمانه 2) بردارهای نظیر ، صفر است . یک مثال از متروید دوتایی که نه گرافیکی و نه هم گرافیکی باشد ، متروید فانو است . این متروید در پایان این بخش معرفی می شود . مترویدهای ترنسورسال : مثال بعدی نظریه مترویدها و نظریه ترنسورسال را به هم ارتباط می دهد . اگر E یک مجموعه متناهی ناتهی باشد و = (S 1 ,…, S m ) δ خانواده ای ناتهی از زیر مجموعه های E باشد ، آنگاه مجموعه های مستقل یک متروید روی E را می توان ترنسورسال جزئی δ گرفت . هر ماترویدی که (با انتخاب مناسب E و δ ) بدین ترتیب به دست می آید ، متروید ترنسورسال نامیده می شود ، و آن را به صورت M(S 1 ,…, S m ) نمایش می دهند . مثلا ، متروید گرافیکی M که اخیرا توصیف شد یک متروید ترنسورسال روی مجموعه {1,2,3} است ، زیرا مجموعه های مستقل آن ترنسورسال های جزئی خانواده δ = (S 1 ,S 2 ) هستند که در آن S 1 = {1} و S 1 = {2,3} . رتبه زیر مجموعه A از E برابر اندازه بزرگترین ترنسورسال جزئی است که در A قرار دارد . می توان ثابت کرد که هر متروید ترنسورسال روی بعضی میدانها نمایش پذیر است ، اما دوتایی است اگر و فقط اگر گرافیکی باشد . در بخش 8-3 نتایج بیشتری از متروید های تونسورسال بررسی خواهد شد . تحدید و انقباض : در نظریه گرافها ممکن است با بررسی زیر گرافها و یا گرافی که از انقباض بعضی از یالها به وج [...]