Witam. Mam do rozwiązania następujące zadanie i nie wiem jak je ugryźć.
Niech \(\displaystyle{ G=(V,E)}\) będzie dowolnym grafem prostym 4 - regularnym. Wykaż, że istnieje \(\displaystyle{ f: E \rightarrow \left\{ 0,1,2\right\}}\) taka, że dla każdego wierzchołka \(\displaystyle{ v \in V}\) suma wartości funkcji \(\displaystyle{ f}\) na krawędziach incydentnych z \(\displaystyle{ v}\) jest równa 6.
Z góry dziękuję.
Graf 4-regularny - dziwna funkcja
-
- Użytkownik
- Posty: 6
- Rejestracja: 30 lis 2013, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
-
- Użytkownik
- Posty: 166
- Rejestracja: 11 lip 2007, o 22:59
- Płeć: Mężczyzna
- Lokalizacja: Bytom
- Pomógł: 49 razy
Graf 4-regularny - dziwna funkcja
A takie coś:
Skoro graf jest \(\displaystyle{ 4}\)-regularny, istnieje w nim cykl Eulera - ustalmy zatem jeden. Ustalmy dowolny wierzchołek \(\displaystyle{ v}\) i przyporządkujmy wartości kolejnym krawędziom grafu tak, że jeśli w naszym cyklu odwiedzamy daną krawędź w kroku "nieparzystym" (licząc od naszego pierwszego wierzchołka) to dajemy jej wartość \(\displaystyle{ 1}\), a jeśli w parzystym to \(\displaystyle{ 2}\).
Jest to dobrze okreslona funkcja (ze względu na ustalony cykl i wierzchołek), każda krawędź ma wartość (bo mamy cykl Eulera) i w oczywisty sposób przy każdym wierzchołku suma wartości na krawędziach to \(\displaystyle{ 1+2+1+2=6}\).
Rozumowanie sypie się trochę gdybyśmy rozważali jakieś cuda pokroju grafów nieprzeliczalnych, ale ktoś mądrzejszy ode mnie może byłby je w stanie uratować
Skoro graf jest \(\displaystyle{ 4}\)-regularny, istnieje w nim cykl Eulera - ustalmy zatem jeden. Ustalmy dowolny wierzchołek \(\displaystyle{ v}\) i przyporządkujmy wartości kolejnym krawędziom grafu tak, że jeśli w naszym cyklu odwiedzamy daną krawędź w kroku "nieparzystym" (licząc od naszego pierwszego wierzchołka) to dajemy jej wartość \(\displaystyle{ 1}\), a jeśli w parzystym to \(\displaystyle{ 2}\).
Jest to dobrze okreslona funkcja (ze względu na ustalony cykl i wierzchołek), każda krawędź ma wartość (bo mamy cykl Eulera) i w oczywisty sposób przy każdym wierzchołku suma wartości na krawędziach to \(\displaystyle{ 1+2+1+2=6}\).
Rozumowanie sypie się trochę gdybyśmy rozważali jakieś cuda pokroju grafów nieprzeliczalnych, ale ktoś mądrzejszy ode mnie może byłby je w stanie uratować
-
- Użytkownik
- Posty: 6
- Rejestracja: 30 lis 2013, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
Graf 4-regularny - dziwna funkcja
Tak, myślę że to o to chodziło i to wystarczy Grafów nieprzeliczalnych my raczej nie rozważamy na zajęciach. Dziękuję za pomoc.