Czy ktos potrafi podac dowód do zadania:
Czy graf moze miec nieparzysta ilosc wierzchołków nieparzystego stopnia?
Narazie doszedłem do tego, ze nie, bo:
Pomijajac petle bo nie maja one wpływu na parzystosc/nieparzystosc mozna zauwazyc, ze kazda krawedź łaczy 2 wierchołki, a z tego wynika... i na tym niestety koniec mojego rozumowania
graf-nieparzysta ilosc wierzchołków nieparzystego stopnia
-
- Użytkownik
- Posty: 185
- Rejestracja: 6 maja 2006, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 32 razy
graf-nieparzysta ilosc wierzchołków nieparzystego stopnia
suma stopni wierzcholkow jest liczba parzysta (poniewaz jest rowna 2*liczba krawedzi), a sumujac nieparzyscie wiele liczb nieparzystych dostajemy liczbe nieparzytsta wiec sprzecznosc. bardziej formalny dowod znajdziesz w kazdej ksiazce z zakresu teorii grafow.