Luați în considerare un grafic în care este un set de margini astfel încât, în locurile corespunzătoare ale vectorului, există una, a.
Prin definirea ciclului generalizat :.
Vom arăta prin inducție, care poate fi descompusă în mai multe cicluri simple de margine disjuncte. Procedăm prin inducție pe numărul de margini. Baza de inducție este evident satisfăcută. Luați în considerare. există un ciclu, adăugați-l la descompunere, eliminați marginile care aparțin acestuia. Deoarece paritatea gradelor vârfurilor nu sa schimbat, prin ipoteza de inducție, se descompune graficul rămas.
Prin urmare, rezultă că la fiecare ciclu generalizat există margini care formează un set de cicluri simple de margine disjuncte.
Dacă luăm în considerare un set de cicluri simple de disjuncționare a unui grafic și luăm toate marginile care aparțin acestor cicluri, atunci putem asocia un ciclu generalizat cu ele, punându-le în locurile potrivite în toate celelalte.
Dacă este un ciclu generalizat corespunzător unui ciclu simplu al graficului, atunci
Fie un ciclu generalizat de la condiție și un ciclu simplu care îi corespunde.
Apoi, unde este o coloană în matricea de incidență a graficului care corespunde marginii. Deoarece fiecare vertex are grad, este adevărat pentru orice. În acest fel.
Datorită liniarității operatorului și faptului că un ciclu simplu, obținem acest lucru
, unde este numărul maxim de coloane LNZ. Dacă luăm în considerare un ciclu simplu 6, atunci suma coloanelor corespunzătoare acestor margini este egală, deoarece valoarea operatorului pe ciclul generalizat corespunzător este exact egală cu suma acestor coloane. Prin urmare, aceste coloane sunt L3. Prin urmare, rezultă că, dacă orice set de margini care conțin un ciclu corespunde unui set de coloane, atunci acesta va fi un LZ
Dacă subsetul de margini nu conține un ciclu, atunci setul de coloane corespunzătoare LNZ.
Să presupunem că este L3, atunci există o combinație liniară de coloane care este zero, unde nu toți coeficienții sunt zero. Luăm coloane a căror coeficienți nu sunt zero, apoi formele lor combinate liniare și astfel marginile corespondente ale muchiei sunt împărțite în cicluri simple, iar setul original de margini conține un ciclu. Contradicția.
Numărul maxim de marginile pe care le putem selecta de la G și care nu conțin un ciclu este egal (în fiecare componentă conectată, selectăm arborele de spanning).
[edit] Aplicație
Spațiul ciclic al unui grafic ne permite să demonstrăm câteva teoreme din teoria grafurilor și, de asemenea, să descriem condițiile existenței subspecii individuale ale unui grafic. În special, datorită conceptului introdus, este posibil să se demonstreze o condiție necesară și suficientă pentru planaritatea graficului [1].
[edit] Vezi, de asemenea
[edit] Note
[edit] Surse de informare
Articole similare
Trimiteți-le prietenilor: