Zastanawia mnie czy następujące twierdzenie jest prawdziwe:
Jeśli graf \(\displaystyle{ G}\) ma \(\displaystyle{ k}\) wierzchołków stopni nieparzystych to zbiór krawędzi grafu \(\displaystyle{ G}\) jest suma \(\displaystyle{ \frac{k}{2}}\) parami rozłącznych zbiorów, z których każdy jest zbiorem krawędzi pewnej drogi.
Waham się czy jest prawdziwa, bo np. taki graf o macierzy incydencji \(\displaystyle{ \left[\begin{array}{cccc}0&0&0&1\\0&0&0&1\\0&0&0&1\\1&1&1&0\end{array}\right]}\) chyba nie da się tak podzielić na takie zbiory, albo nie rozumiem kiedy zbiory są rozłączne. Zapisuje graf macierzą, bo nie wiem czy się da w LaTeX narysować graf.
Dziwne twierdzenie z teorii grafów
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Dziwne twierdzenie z teorii grafów
dodajmy dodatkowy wierzcholek i polaczmy go z wierzchołkami nieparzystego stopnia.wtedy wszystkie wierzcholki są parzystego stopnia wiec w grafie istnieje cykl Eulera. wywalajac z niego wszystkie wystapienia wczesniej dodanego wierzcholka dostajemy podzial na k/2 rozlacznych sciezkek.
-
- Użytkownik
- Posty: 520
- Rejestracja: 28 sty 2009, o 19:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 14 razy
- Pomógł: 86 razy
Dziwne twierdzenie z teorii grafów
Mógłbyś innaczej sformułować innaczej tą część "wywalajac z niego wszystkie wystapienia wczesniej dodanego wierzcholka ", bo nie do końca rozumiem.
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Dziwne twierdzenie z teorii grafów
na początku dodatliśmy wierzchołek X
mamy potem cykl Eulera przykładowo:
X-1-2-3-1-X-2-5-6-7-X-3-4-5-
wywalamy X i mamy sciezki:
1-2-3-1-
2-5-6-7
3-4-5
mamy potem cykl Eulera przykładowo:
X-1-2-3-1-X-2-5-6-7-X-3-4-5-
wywalamy X i mamy sciezki:
1-2-3-1-
2-5-6-7
3-4-5