zad. 1
Pokazać, że jeżeli każda krawędź grafu \(\displaystyle{ K _{(r-1) ^{2}+1 }}\) jest pokolorowana na czerwono lub zielono, to albo każde drzewo na r wierzchołkach jest czerwone, albo każde drzewo na r wierzchołkach jest zielone.
zad. 2
Które z podanych grafów są izomorficzne?
zadania na grafach
-
dabros
- Użytkownik
- Posty: 1117
- Rejestracja: 2 cze 2006, o 21:41
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 48 razy
- Pomógł: 4 razy
zadania na grafach
grafy izomorficzne mają identyczne stopnie wierzchołków i identyczne połączenia krawędzi z wierzchołkami - teraz wystarczy po prostu przeanalizować dokładnie wszystkie rysunki
wtedy dochodzimy do wniosku, że izomorficzne są grafy:
1, 2 i 7 oraz 5 i 6 (ale lepiej upewnić się samemu, bo człowiek jest z natury omylny)
wtedy dochodzimy do wniosku, że izomorficzne są grafy:
1, 2 i 7 oraz 5 i 6 (ale lepiej upewnić się samemu, bo człowiek jest z natury omylny)
-
saker
- Użytkownik
- Posty: 6
- Rejestracja: 29 sie 2005, o 11:01
- Płeć: Mężczyzna
- Lokalizacja: Świebodzin
- Pomógł: 1 raz
zadania na grafach
Odnośnie zadania 1:
Rozważmy graf \(\displaystyle{ K_5}\) z krawędziami pokolorowanymi na zielono i czerwono tak, aby istniała krawędź w kolorze czerwonym i krawędź w kolorze zielonym. Wtedy istnieje wierzchołek \(\displaystyle{ v}\) taki, z którego wychodzi krawędź czerwona i zielona. Niech \(\displaystyle{ vu}\) będzie krawędzią czerwoną, a \(\displaystyle{ vw}\) krawędzią zieloną. Wtedy drzewo rozpięte na wierzchołkach \(\displaystyle{ u,v,w}\) z krawędziami \(\displaystyle{ uv,vw}\) nie jest monochromatyczne.
Nie powinno być przypadkiem, że w grafie \(\displaystyle{ K_{(r-1)^2 + 1}}\) istnieje monochromatyczne drzewo na \(\displaystyle{ r}\) wierzchołkach?
[edit]W tym drugim przypadku dowód nie jest trudny. Każdy wierzchołek w \(\displaystyle{ K_{(r-1)^2 + 1}}\) ma \(\displaystyle{ (r-1)^2}\) sąsiadów. Z zasady szufladkowej wynika, że istnieje wierzchołek, z którego wychodzi co najmniej \(\displaystyle{ \frac{(r-1)^2}{2}}\) krawędzi w kolorze czerwonym. Te krawędzi dadzą ci monochromatyczne drzewo na \(\displaystyle{ r}\) wierzchołkach, jeśli \(\displaystyle{ \frac{(r-1)^2}{2} q r-1}\).
Rozważmy graf \(\displaystyle{ K_5}\) z krawędziami pokolorowanymi na zielono i czerwono tak, aby istniała krawędź w kolorze czerwonym i krawędź w kolorze zielonym. Wtedy istnieje wierzchołek \(\displaystyle{ v}\) taki, z którego wychodzi krawędź czerwona i zielona. Niech \(\displaystyle{ vu}\) będzie krawędzią czerwoną, a \(\displaystyle{ vw}\) krawędzią zieloną. Wtedy drzewo rozpięte na wierzchołkach \(\displaystyle{ u,v,w}\) z krawędziami \(\displaystyle{ uv,vw}\) nie jest monochromatyczne.
Nie powinno być przypadkiem, że w grafie \(\displaystyle{ K_{(r-1)^2 + 1}}\) istnieje monochromatyczne drzewo na \(\displaystyle{ r}\) wierzchołkach?
[edit]W tym drugim przypadku dowód nie jest trudny. Każdy wierzchołek w \(\displaystyle{ K_{(r-1)^2 + 1}}\) ma \(\displaystyle{ (r-1)^2}\) sąsiadów. Z zasady szufladkowej wynika, że istnieje wierzchołek, z którego wychodzi co najmniej \(\displaystyle{ \frac{(r-1)^2}{2}}\) krawędzi w kolorze czerwonym. Te krawędzi dadzą ci monochromatyczne drzewo na \(\displaystyle{ r}\) wierzchołkach, jeśli \(\displaystyle{ \frac{(r-1)^2}{2} q r-1}\).