Matematyka.pl

Udowdnić, że liczba wspólnych krawędzi cyklu i rozcięcia w grafie spójnym jest parzysta.

Warto wspomnieć co to jest rozcięcie grafu spójnego, a mianowicie zabranie takiej ilości krawędzi po którym graf staje się niespójny.
Warto jeszcze nadmienić, że zabieramy krawędzie a zostawiamy wierzchołki...

Jeżeli wszystkie podzbiory zbioru krawędzi grafu \(\displaystyle{ K(G)}\) z działaniemna wektorach: \(\displaystyle{ X, Y \in K(G) }\) jako suma symetryczna.
Będzie to przestrzeń liniowa nad ciałem \(\displaystyle{ \ZZ_{2}}\).

Bazowymi wektorami mogą być wektory reprezentujące kolumny w macierzy incydencji tego grafu...

Co ciekawe to to, że przestrzeń ta rozkłada się na sumę prostą podprzestrzeni:

\(\displaystyle{ K(G)=V_{1} \oplus V_{2}}\)

gdzie \(\displaystyle{ V_{1} }\) to podprzestrzeń złożona z rozcięć grafu, a \(\displaystyle{ V_{2}}\) to podprzestrzeń złożona z z cykli grafu...

Bazą przestrzeni rozcięć to rozcięcia minimalne czyli takie w których jeżeli weźmiemy o jedną krawędź mniej to rozcięcia nie będzie...

Bazą przestrzeni cykli są te cykle, które powstają przez dołożenie jednej krawędzi do drzewa rozpinającego...

Macierz incydencji składa się z parzystej liczby jedynek...

Każda kolumna w tej macierzy zawiera parzystą liczbę jedynek...

Oczywiście podprzestrzeń \(\displaystyle{ V_{1}}\) z oczywistych powodów też zawiera parzystą liczbę jedynek.

W związku z tym część wspólna \(\displaystyle{ v_{1} \in V_{1} }\) oraz \(\displaystyle{ v_{2} \in V_{2} }\) musi wynosić:

\(\displaystyle{ v_{1} \cap v_{2}=\emptyset \vee \left\{ \underbrace{1,1,...\ldots,1}_{2n}\right\} }\)

Nie mylić części wspólnej \(\displaystyle{ v_{1}, v_{2}}\) potraktowanych jako zbiorów kolumn a nie jako wektorów...