پاورپوینت نظریه متروید در گراف (pptx) 56 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 56 اسلاید
قسمتی از متن 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
تعریف شده ، است به طوری که ؛
