Матроид

Матроид је уређени пар $M=(S,{\mathcal {I}})$ формиран на следећи начин:

1. Скуп $S$ је коначан.
2. Нека је ${\mathcal {I}}$ непразна фамилија подскупова скупа $S$ (који се називају независним подскуповима) таква да ако је $B\in {\mathcal {I}}$ и $A\subseteq B$, тада је $A\in {\mathcal {I}}$. Ако фамилија ${\mathcal {I}}$ задовољава ову особину тада је називамо наслеђеном (Хередитарy). Приметимо да празан скуп $\varnothing$ обавезно припада фамилији ${\mathcal {I}}$.
3. Ако је $A\in {\mathcal {I}},B\in {\mathcal {I}}$ и $|A|<|B|$, тада постоји елемент $x\in B\setminus A$, такав да је $A\cup \{x\}\in {\mathcal {I}}$. Говоримо да структура $M$ задовољава особину замене.

Термин „матроид“ је увео Витни Хаслер. Он је проучавао матричне матроиде, чији су елементи $S$ редови задате матрице. Скуп редова је независан, ако су они линеарно независни у обичном смислу. Лако се показује да ова структура дефинише матроид.

Као суштину другог примера матроида размотримо матроид графа $M_{G}=(S_{G},{\mathcal {I}}_{G})$, који је дефинисан помоћу појма неоријентисаног графа $G=(V,E)$, где је:

• $S_{G}$ скуп $E$ ивица графа $G$,
• Ако је $A$ подскуп скупа $E$, тада је $A\in {\mathcal {I}}_{G}$ ако и само ако је $A$ нецикличан тј, скуп ивица $A$ је независан ако и само ако подграф $G_{A}=(V,A)$ образује шуму.

Теорема 1

Ако је $G=(V,E)$ неоријентисан коначан граф тада је $M_{G}=(S_{G},{\mathcal {I}}_{G})$ матроид.

Доказ

Очигледно је да је $S_{G}=E$ коначан скуп. Осим тога ${\mathcal {I}}_{G}$ је наследна фамилија јер је подскуп шуме такође шума. Другим речима, одстрањивање ивица из ацикличног скупа ивица графа не може дати цикличан скуп.

На тај начин остаје нам да покажемо да структура $M_{G}$ одговара особини замене. Претпоставимо да су $G_{A}=(V,A)$ и $G_{B}=(V,B)$ шуме графа $G$ и да је $|A|<|B|$ , тј. $A$ и $B$ су ациклични скупови ивица, и да у скупу $B$ има више ивица него у скупу $A$. Из једне од теорема које су раније разматране следи да шума у којој имамо $k$ ивица има тачно $|V|-k$ дрвета. Да то докажемо пођимо од $|V|$ дрвета од којих свако има само један врх и не садржи ни једну ивицу. Тада свако ребро (ивица) које се додаје шуми, за један смањује број дрвета. На тај начин шума $G_{A}$ има $|V|-|A|$ дрвета, а шума $G_{B}$ има $|V|-|B|$ дрвета.

Како шума $G_{B}$ има мање дрвета од шуме $G_{A}$ тада у шуми $G_{B}$ постоји ивица $(u,v)$ таква да се врхови $u$ и $v$ налазе у два различита дрвета шуме $G_{A}$. Пошто ова ивица спаја врхове двају различитих дрвета шуме $G_{A}$ тада је можемо додати у шуму $G_{A}$ не образујући круг на тај начин. На тај начин структура $M_{G}$ задовољава особину замене, чиме се завршава доказ да је $M_{G}$ матроид.

За задати матроид $M=(S,{\mathcal {I}})$ дефинишимо елемент $x\in A$ као проширење скупа $A\in {\mathcal {I}}$, ако је њега могуће додати у $A$ без нарушавања независности тј. $x$ је проширење скупа $A$ ако је $A\cup \{x\}\in {\mathcal {I}}$. Као пример размотримо матроид графа $M_{G}$. Ако је $A$ независан скуп ивица, тада је ивица $e$ проширење скупа $A$ ако и само ако не припада том скупу и ако њено додавање скупу не доводи до стварања циклуса.

Ако је $A$ независан подскуп у матроиду $M$, и ако у њему нема проширења (нису могућа) тада кажемо да је $A$ максималан скуп. На тај начин, скуп $A$ је максималан ако се не садржи ни у једном већем подскупу матроида $M$. Доле дата особина је често врло корисна.

Теорема 2

Сви максимални независни подскупови матроида имају исту величину.

Доказ:

Теорему доказујемо методом свођења на противречност. Претпоставимо да је $A$ максималан независан подскуп матроида $M$ и да постоји други максимални независни подскуп $B$ матроида $M$ чија је величина већа од величине подскупа $A$. Тада из особине замене следи да скуп $A$ можемо проширити до већег независног скупа $A\cup \{x\}$ помоћу неког елемента $x\in B\setminus A$ што је супротно претпоставци о максималности скупа $A$.

Као илустрацију примене ове теореме размотримо примену на матроид графа $M_{G}$ везаног за неоријентисани повезани граф $G$. Сваки максимални независни подскуп матроида $M_{G}$ мора да буде (да представља) слободно дрво које има тачно $|V|-1$ ивица које спајају врхове графа $G$. Такво дрво се зове основно дрво графа $G$.

Кажемо да је матроид $M=(S,{\mathcal {I}})$ тежински, ако је са њим повезана тежинска функција $w$ која сваком елементу $x\in S$ придружује строго позитивну тежину $w(x)$. Тежинска функција $w$ се уопштава на подскупове скупа $S$ путем сумирања:

$w(A)=\sum _{x\in A}w(x)$ за произвољни подскуп $A\subseteq S$.

На пример, ако са $w(e)$ означимо дужину ивице $e$ матроида графа $M_{G}$, тада је $w(A)$ укупна дужина свих ивица које припадају скупу $A$.

Види још

• Теорија графова
• Похлепни алгоритам

Литература

• Брухн, Хеннинг; Диестел, Реинхард; Криеселл, Маттхиас; Wоллан, Паул (2010), Аxиомс фор инфините матроидс .
• Брyант, Вицтор; Перфецт, Хазел (1980). Индепенденце Тхеорy ин Цомбинаторицс. Лондон анд Неw Yорк: Цхапман анд Халл. ИСБН 978-0-412-22430-0. .
• Брyлаwски, Тхомас Х. (1972), „А децомпоситион фор цомбинаториал геометриес”, Трансацтионс оф тхе Америцан Матхематицал Социетy, Америцан Матхематицал Социетy, 171: 235—282, дои:10.2307/1996381 .
• Црапо, Хенрy Х. (1969), „Тхе Тутте полyномиал”, Аеqуатионес Матхематицае, 3 (3): 211—229, дои:10.1007/БФ01817442 .
• Црапо, Хенрy Х.; Рота, Гиан-Царло (1970). Он тхе Фоундатионс оф Цомбинаториал Тхеорy: Цомбинаториал Геометриес. Цамбридге, Масс.: M.I.Т. Пресс. ИСБН 978-0-262-53016-3. МР0290980. .
• Геелен, Јим; Герардс, А. M. Х.; Wхиттле, Геофф (2007), „Тоwардс а матроид-минор струцтуре тхеорy”, Ур.: Гримметт, Геоффреy (ед.), Цомбинаторицс, Цомплеxитy, анд Цханце: А Трибуте то Доминиц Wелсх, Оxфорд Лецтуре Сериес ин Матхематицс анд итс Апплицатионс, 34, Оxфорд: Оxфорд Университy Пресс, стр. 72—82 ЦС1 одржавање: Текст вишка: списак уредника (веза).
• Герардс, А. M. Х. (1989), „А схорт прооф оф Тутте'с цхарацтеризатион оф тоталлy унимодулар матрицес”, Линеар Алгебра анд Апплицатионс, 114/115: 207—212, дои:10.1016/0024-3795(89)90461-8 .
• Кахн, Јефф; Кунг, Јосепх П. С. (1982), „Вариетиес оф цомбинаториал геометриес”, Трансацтионс оф тхе Америцан Матхематицал Социетy, Америцан Матхематицал Социетy, 271 (2): 485—499, дои:10.2307/1998894 .
• Кинган, Роберт; Кинган, Сандра (2005), „А софтwаре сyстем фор матроидс”, Грапхс анд Дисцоверy, ДИМАЦС Сериес ин Дисцрете Матхематицс анд Тхеоретицал Цомпутер Сциенце, стр. 287—296 .
• Кунг, Јосепх П. С., ур. (1986). А Соурце Боок ин Матроид Тхеорy. Бостон: Биркхäусер. ИСБН 978-0-8176-3173-4. МР0890330. .
• Мац Лане, Саундерс (1936), „Соме интерпретатионс оф абстрацт линеар депенденце ин термс оф пројецтиве геометрy”, Америцан Јоурнал оф Матхематицс, Тхе Јохнс Хопкинс Университy Пресс, 58 (1): 236—240, дои:10.2307/2371070 .
• Оxлеy, Јамес (1992). Матроид Тхеорy. Неw Yорк: Оxфорд Университy Пресс. ИСБН 978-0-19-853563-8. МР1207587. .
• Рецски, Андрáс (1989). Матроид Тхеорy анд итс Апплицатионс ин Елецтриц Нетwорк Тхеорy анд ин Статицс. Берлин анд Будапест: Спрингер-Верлаг анд Академиаи Киадо. ИСБН 978-3-540-15285-9. МР1027839. .
• Сеyмоур, Паул D. (1980), „Децомпоситион оф регулар матроидс”, Јоурнал оф Цомбинаториал Тхеорy, Сериес Б, 28 (3): 305—359, дои:10.1016/0095-8956(80)90075-1 .
• Труемпер, Клаус (1992). Матроид Децомпоситион. Бостон: Ацадемиц Пресс. ИСБН 978-0-12-701225-4. МР1170126. .
• Тутте, W. Т. (1959), „Матроидс анд грапхс”, Трансацтионс оф тхе Америцан Матхематицал Социетy, Америцан Матхематицал Социетy, 90 (3), дои:10.2307/1993185, МР0101527 .
• Тутте, W. Т. (1965), „Лецтурес он матроидс.”, Јоурнал оф Ресеарцх оф тхе Натионал Буреау оф Стандардс (У.С.А.), Сецт. Б, 69: 1—47 .
• Тутте, W. Т. (1971), Интродуцтион то тхе Тхеорy оф Матроидс, Неw Yорк: Америцан Елсевиер .
• Вáмос, Петер (1978), „Тхе миссинг аxиом оф матроид тхеорy ис лост форевер”, Јоурнал оф тхе Лондон Матхематицал Социетy, II. Сер., 18: 403—408, дои:10.1112/јлмс/с2-18.3.403 .
• ван дер Wаерден, Б. L. (1937), Модерне Алгебра .
• Wхите, Неил, ур. (1986). Тхеорy оф Матроидс. Енцyцлопедиа оф Матхематицс анд итс Апплицатионс. 26. Цамбридге: Цамбридге Университy Пресс. ИСБН 978-0-521-30937-0. .
• Wхите, Неил, ур. (1992). Матроид Апплицатионс. Енцyцлопедиа оф Матхематицс анд итс Апплицатионс. 40. Цамбридге: Цамбридге Университy Пресс. ИСБН 978-0-521-38165-9. .
• Wхитнеy, Хасслер (1935), „Он тхе абстрацт пропертиес оф линеар депенденце”, Америцан Јоурнал оф Матхематицс, Тхе Јохнс Хопкинс Университy Пресс, 57 (3): 55—79, дои:10.2307/2371182, МР1507091 .
• Wхиттле, Геофф (1995), „А цхарацтеризатион оф тхе матроидс репресентабле овер ГФ(3) анд тхе ратионалс” (ПДФ), Јоурнал оф Цомбинаториал Тхеорy Сериес Б, 65 (2): 222—261, дои:10.1006/јцтб.1995.1052 .