grafy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Sigman
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 11 mar 2017, o 17:37
Płeć: Mężczyzna
Lokalizacja: 10 wymiar
Podziękował: 6 razy

grafy

Post autor: Sigman » 14 lip 2020, o 19:25

Cześć. Mam problem z ćwiczeniem 3.8 z "Kombinatoryki" Neugebauera.
Treść:
Na każdej z 2011 krawędzi pewnego wielościanu napisano jedną z liczb \(\displaystyle{ +1}\) albo \(\displaystyle{ -1}\). Uzasadnić, że istnieje taki wierzchołek tego wielościanu, że iloczyn liczb napisanych na wszystkich wychodzących z tego wierzchołka krawędziach jest równy \(\displaystyle{ +1}\).

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7793
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3060 razy

Re: grafy

Post autor: kerajs » 14 lip 2020, o 23:36

Przypuszczam, że błędnie przepisana jest treść zadania.
Przy powyższej można wskazać wielościany nie spełniające powyższej tezy.
Np:
W 1004-boku numeruję kolejno wierzchołki od 1 do 1004, a jego kolejnym bokom przypisuję przemiennie wartości 1,-1,1,-1,.. . Nad nim wybieram dwa wierzchołki o numerach 1005 i 1006 połączone krawędzią o wartości -1. Wierzchołki od 1 do 503 łączę krawędziami z wierzchołkiem 1005, a wierzchołki od 503 do 1004 oraz 1 łączę z wierzchołkiem 1006. Tym krawędziom przypisuję wartość 1. Jak łatwo sprawdzić, ten wielościan ma 2011 krawędzi, a w każdym wierzchołku iloczyn wychodzących z niego krawędzi wynosi -1.

Sigman
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 11 mar 2017, o 17:37
Płeć: Mężczyzna
Lokalizacja: 10 wymiar
Podziękował: 6 razy

Re: grafy

Post autor: Sigman » 15 lip 2020, o 08:24

kerajs pisze:
14 lip 2020, o 23:36
Przypuszczam, że błędnie przepisana jest treść zadania.
Sprawdziłem, teza jest prawidłowo przepisana. Jest to ćwiczenie do twierdzenia o uściskach dłoni.

W tezie powinno być wielościanu w \(\displaystyle{ \RR^2 }\), prawda?

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7793
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3060 razy

Re: grafy

Post autor: kerajs » 15 lip 2020, o 11:34

Sigman pisze:
15 lip 2020, o 08:24
Sprawdziłem, teza jest prawidłowo przepisana.
Więc jest błędna. Do jej obalenia wystarczy jeden kontrprzykład, a ten wskazałem powyżej.
Sigman pisze:
15 lip 2020, o 08:24
W tezie powinno być wielościanu w \(\displaystyle{ \RR^2 }\), prawda?
Strasznie płaskie są wielościany w \(\displaystyle{ \RR^2 }\).

ODPOWIEDZ