Să verificăm îndeplinirea axiomelor de independență:
- Un set gol este aciclic și, prin urmare, intră.
- Evident, orice subgraf al unei păduri este, de asemenea, o pădure și, prin urmare, intră datorită aciclicității sale.
- Într-un grafic există cel puțin două componente de conectivitate, în caz contrar ar fi un copac spanning și nu ar exista un set aciclic cu o putere mai mare. Să presupunem că nu există o margine care unește două componente diferite ale conexiunii, astfel încât orice componentă a conexiunii întregului vârf - intră într-o componentă a lui. Considerăm orice componentă a legăturii, a vârfurilor și a muchiilor sale. Acum, ia în considerare toate componentele de conectivitate, vârf-a intra in, lasa piesele lor, în timp ce numărul total de muchii ale aceluiași, care nu depășește (numărul de muchii din). Sintetim inegalitatea pentru toate componentele conectate din și obține, ceea ce contrazice ipoteza. Aceasta înseamnă că presupunerea nu este adevărată și că există o margine necesară de la diferitele componente conectate.
[edit] Matrix Matroid
Fie ca un spațiu vectorial să fie solid, permiteți setului de vectori din spațiu să fie un suport. Elementele setului independent al unui anumit matroid sunt seturi de vectori liniar independenți din colecție. Apoi, numit matrice matrice (matrice vector engleză)
Formăm matricea de incidență pentru grafic. Rândurile acestei matrice corespund vârfurilor graficului, iar coloanele de margini.
- Dacă marginea-a este o bucla incidentă la cel de-al vârfului, atunci.
- Dacă vârful-a intră în marginea-a, atunci
- altfel
Noi trebuie să facă dovada că, dacă luăm setul de margini, setul de coloane din matricea de incidență corespunzătoare laturii selectate, liniar independente, și vice-versa, dacă luăm set liniar independent de coloane, setul corespunzător de margini, nu va forma un ciclu. Se dovedește o afirmație echivalentă: coloanele sunt dependente liniar dacă și numai dacă marginile corespunzătoare ale graficului conțin un ciclu.
Lăsați coloanele să fie dependente liniar, dovedim că marginile corespunzătoare ale graficului conțin un ciclu.
Dacă unele coloane ale matricei sunt dependente liniar, atunci dintre ele se pot selecta coloane cu suma zero. Există două opțiuni:
- Printre coloanele selectate este zero, apoi în setul corespunzător de margini există o buclă, adică un ciclu.
- Avem o coloană care este suma celorlalte coloane. Această margine corespunde unei muchii. Să începem din partea de sus pentru a comuta pe celelalte margini ale (fiecare muchie este deplasată doar o singură dată), vom ajunge în cele din urmă la partea de sus, astfel încât pentru nodurile rămase noi în mod necesar un număr par de emergente din marginile lor, deoarece în caz contrar în această poziție de top în coloana a fost la unitatea (o unitate cu noi numai pe pozițiile și). Astfel, am arătat că există două căi între nodurile și (ceea ce am construit și calea de-a lungul marginii), atunci setul selectat de muchii are un ciclu.
Să presupunem că există un ciclu pe setul de muchii și vom dovedi dependența liniară a coloanelor corespunzătoare.
Dacă există o buclă între setul de muchii dat, atunci coloana corespunzătoare va fi zero (prin construirea matricei de incidență) și asigură dependența liniară a întregului set de vectori.
Dacă nu există nicio buclă, luați în considerare coloanele corespunzătoare marginilor unui ciclu simplu. Orice rând al matricei conține exact 2 unități în aceste coloane. Prin urmare, suma modulo a coloanelor indicate este egală cu coloana zero, ceea ce înseamnă dependența liniară a setului original de coloane.
[edit] Alte matroizi
Articole similare
Trimiteți-le prietenilor: