Ние потвърди, че независимостта на аксиоми:
- В празното множество е ацикличен, а оттам и част от.
- Очевидно е, че който и да е подграф гора е и горите, и затова са включени в благодарение на ациклични.
- В колоната от най-малко два компонента на свързаност, или ще представлява обхваща дърво, и няма да има ациклени агрегати с по-голяма мощност. Нека в, няма ръб, свързващ две различни компоненти на свързаност, това означава, че който и да е компонент на свързаност на целия връх-част на който и да е компонент на. Помислете за някоя от съставките на свързаност, тя върхове и ръбове. А сега да разгледаме всички компоненти на свързаност, връх-влизане в, нека си парчета, а общият брой на ръбове на едно и също, че не превишава (на броя на ръбовете в). Ние обобщим неравенството за всички компоненти на свързаност, и ние откриваме, че противоречи на хипотезата. Така че предположението не е вярно, и има желания край на връзката различни компоненти.
[Член] Матрицата matroid
Да - вектор пространство над тялото, дори ако набор от носители на пространството е носител. Множество независими елементи Matroid са линейно независими набор от вектори в комплекта. След това матрицата се нарича matroid (Eng. Vector matroid)
Ние конструиране на матрицата честота на графиката. Редици от тази матрица съответстват на върховете на графиката и колоните - ребра.
- Ако -s ребро е инцидент линия до ия връх, след това.
- Ако Star -та връх е инцидент до ръба, а след това
- в противен случай
Трябва да се докаже, че ако вземем набор от ръбове, набор от колони на матрицата на честота, съответстващи на избрания ръб, линейно независими, и обратно, ако вземем линейно независими набор от колони, на съответния набор от ръбове, няма да образуват цикъл. Ние докаже еквивалентно твърдение: колоните са линейно зависими единствено и само ако съответните ръбове на графиката съдържа цикъл.
Да приемем, че колоните са линейно зависими, ние докаже, че съответните краища на графиката съдържа цикъл.
Ако някои от колоните на матрицата са линейно зависими, сред тях са колони с нулева сума. Има два варианта:
- Чета избрани колони е нула, тогава съответния набор от ребра има контур, т.е. цикъл.
- В момента има колона, която е сбор от другите колони. Тази колона съответства на ръба. Да започнем от върха, за да превключите на други краища на (всеки ръб се пресича само веднъж), ние най-накрая пристигат в горната част, така и за останалите върхове ние непременно четен брой излиза от краищата им, защото в противен случай при тази първа позиция в колоната беше към устройството (единица при нас само позициите и). Така ние показахме, че има два начина между върховете и (това, което ние са изградени и пътя по ръба), след това избран набор от ръбове има цикъл.
Нека множеството от ребрата имат контур-линейна зависимост докаже съответните колони.
Ако, сред множеството от ребрата е цикъл, след съответната колона ще бъде нула (според конструкцията честота матрица), и осигурява линейна зависимост целия набор от вектори.
Ако веригата не е, по-добре колоните, съответстващи на краищата на един прост цикъл. Всеки ред на матрицата съдържа следните колони точно 2 единици. Следователно, по модул сумата споменатата колона е колона нула, че е линейна зависимост от първоначалния набор от колони.
[Редактиране] Други Matroids
Свързани статии