Nie chciałem tworzyć 3 wątków (tylu ilu zadań) dlatego daję je tutaj razem. Wszystkie są związane z teorią grafów: ich kolorowaniem i spójnością. Muszę je rozwiązać żeby się przygotować do zaliczania Matematyki dyskretnej II. ;/
Bardzo proszę o pomoc w ich rozwiązaniu. Jakby ktoś miał pomysł na którekolwiek z nich to piszcie.
==================== ==================== ====================
1. Udowodnić, że dla dowolnego grafu \(\displaystyle{ G}\) o przynajmniej \(\displaystyle{ 3}\) wierzchołkach zachodzi \(\displaystyle{ e(G)\ge\binom{\chi(G)}{2}}\)
2. Jeśli \(\displaystyle{ G}\) jest grafem dwudzielnym o \(\displaystyle{ n\ge 4}\) wierzchołkach i \(\displaystyle{ \delta (G)\ge\frac{n+1}{4}}\) to \(\displaystyle{ G}\) jest dwuspójny.
Wskazówka: ile może być najwięcej krawędzi w grafie dwudzielnym?
3. Udowodnić, że dla dowolnego grafu \(\displaystyle{ G}\) zachodzi \(\displaystyle{ \chi (G)=\max\{\chi (H):\hbox{H jest blokiem w G}\}}\). Blok jest to maksymalny podgraf dwuspójny.
==================== ==================== ====================
Gdzie:
\(\displaystyle{ \chi(G)}\) - najlepsze pokolorowanie wierzchołkowe grafu \(\displaystyle{ G}\)
\(\displaystyle{ \delta (G)}\) - najmniejszy stopień wierzchołka w \(\displaystyle{ G}\)
-- 17 lutego 2012, 17:15 --
Podejmijcie się pomocy, bo muszę to garnąć a sam nie daję rady.
Sukcesywnie będę dopisywał co mi się udało wypracować w każdym zadaniu.
1. Przekształciłem tę nierówność tak, że mamy \(\displaystyle{ 2\cdot e(G)\ge\chi(G)\cdot (\chi (G) - 1)}\). A wiemy, że \(\displaystyle{ 2\cdot e(G)=\sum_{v\in G} \deg_{G}(v)}\). Co z tego?...
-- 17 lutego 2012, 17:25 --
Dodam tylko, że \(\displaystyle{ e(G)}\) oznaczam ilość krawędzi w grafie \(\displaystyle{ G}\).
-- 17 lutego 2012, 19:43 --
Wiem jeszcze, że dla każdego \(\displaystyle{ G}\) zachodzi \(\displaystyle{ \chi (G) \le \Delta (G) + 1}\) (łatwe do pokazania/zobaczenia/zauważenia).
Zauważyłem też, że: \(\displaystyle{ 2\cdot e(G)=\sum_{v\in G} \deg_{G}(v)\le n\cdot\Delta (G)\underbrace{\le}_{\Delta (G)+1\le n}\Delta (G)\cdot (\Delta (G) + 1)}\)
oraz
\(\displaystyle{ (\chi (G) - 1)\chi (G)\le (\Delta (G) +1)\cdot \Delta (G)}\)
Ale chyba takie oszacowania niewiele wnoszą.