نظریه ماتروید (تعریف ماتروید)

ماتروید ویژگی بردارهای مستقل را مدل می‌کند.

تعریف مجموعه‌ی مستقل:

یک مجموعه‌ی S و تعدادی از زیرمجموعه‌های آن را انتخاب کنیم که:

۱- هر زیرمجموعه‌ی زیرمجموعه‌ی انتخاب شده را انتخاب کنیم. (ناشی از ترکیب خطی)

۲- اگر دو مجموعه‌ی مستقل داشته باشید که یکی بزرگتر از دیگر است می‌توانید به مجموعه کوچکتر اضافه کنید که بزرگتر شود. (ناشی از نظریه مجموعه‌ها)

مثال:

2^S

طبق تعریف مجموعه‌های مستقل یک ماتروید است.

مثال ۲:

S= {a,b,c}

I = {همه‌ی کمتر مساوی ۲ عضوی‌ها}

هست. {b} و {a,c} را در نظر بگیرید. می‌توانیم a یا c را به b اضافه کنیم و همچنان در جواب هست.

مثال: ستون‌های ماتریس = S

v1 v2 v3 v4 v5

1   1   1   1   0

0   0   0   1   1

0   1   1   1   1

I= بردارهای مستقل خطی = 

{{v1},{v1,v2},...}

گاهی روی ماترویدها مسایل ان‌پی-کامل را می‌توان چندجمله‌ای حل کرد.

همه‌ی تعریف‌های ماتروید معادلند.

* تعریف بر اساس پایه (basis):

پایه = کمترین تعداد بردار که بتوانند بقیه را بسازند. (اما از این تعریف نمی‌توانیم استفاده کنیم چون همه معنی ندارد.)

= بزرگترین مجموعه‌ی مستقل خطی

در تعریف قبلی به همه‌ی مجموعه‌های ماکسیمال پایه می‌گوییم.

در مثال اول: {a,b,c}

در مثال دوم: همه‌ی زیرمجموعه‌های دو عضوی

قضیه: همه‌ی پایه‌ها تعداد اعضایشان  مساوی است.

برهان خلف:

|A| < |B|

پس می‌شود اندازه‌ی A را با اضافه کردن از B\A بزرگ کرد که این با ماکسیمال بودن A تناقض دارد.

*تعریف ماتروید با پایه:

B1) مجموعه‌ی B تهی نباشد.

B2) اگر یک عضو از A را حذف کنیم و به جای آن یک عضو از B را به A اضافه کنیم نتیجه باز هم ماتروید باشد.

اثبات: برهان خلف. اگر |A|<|B| باشد، می‌توانیم انقدر عضوها را یکی یکی اضافه کنیم تا کل B را شامل شود که با ماکسیمال بودن B تناقض دارد.

* اگر همه‌ی زیرمجموعه‌های پایه را اضافه کنیم به تعریف ماتروید با مجموعه‌های مستقل می‌رسیم.

* تعریف با تابع رتبه (Rank Function):

تابعی می‌دهند که از روی آن ماتروید را می‌سازیم.

rank یک مجموعه، بعد فضایی است که می‌سازد. مثلاً ۳ بردار {غیر هم خط} در صفحه rankشان ۲ است.

همان ستون‌های ماتریس v1,...,vn باشند، آنگاه

r{v1,...,vn} = فضایی که آنها می‌سازند چندبعدی است.

رتبه مجموعه تهی صفر است.

رتبه‌ی مجموعه‌ی A ماکسیمم اندازه‌ی مجموعه‌هایی است که هم مجموعه‌ی مستقل باشند و هم زیرمجموعه‌ی A باشند.

اگر A زیرمجموعه‌ی B باشد رتبه‌ی A از B کمتر مساوی است.

تعریف ماتروید با تابع رتبه:

R1) r(A) >= 0

R2) r(A)+r(B) >= r(A u B) + r(A^B)

تبدیل از تعریف با تابع رتبه به تعریف با مجموعه‌های مستقل:

I = {T \subset S: r(T) = |T|}

... (خیلی خسته‌کننده است بعداً بقیه‌اش را شاید نوشتم.)