1) Pokazać, że każdy graf o n wierzchołkach i więcej niż \(\displaystyle{ \frac{(n-1)(n-2)}{2}}\) krawędziach jest spójny.
2) Niech w grafie pełnym \(\displaystyle{ K_{n}}\) waga każdej krawędzi będzie równa 1
a) znaleźć optymalny (o minimalnej wadze) obchód w grafach \(\displaystyle{ K_{5}}\) oraz \(\displaystyle{ K_{6}}\)
b) znaleźć wagę optymalnego obchodu w \(\displaystyle{ K_{n}}\) (dla dowolnego \(\displaystyle{ n \ge 3}\))
3) Pokazać, że nie istnieje 4-regularny graf dwudzielny, który jest planarny.
4) Pokazać, że jeśli G jest grafem hamiltonowskim 3-regularnym, to indeks chromatyczny X'(G) = 3. Czy prawdą jest również wtedy, że liczba chromatyczna x(G) = 3?
Grafy 4 zadania
-
miodzio1988
Grafy 4 zadania
4)
Niech \(\displaystyle{ (V _{1} , V _{2} , E)}\) będzie grafem dwudzielnym o największym stopniu wierzcholka rownym \(\displaystyle{ d}\). Wowczas \(\displaystyle{ \chi ' (G)=d}\)
Dowod to indukcja względem \(\displaystyle{ \left| E \right|}\)
3) wzor Eulera pomoże.
2)Zdefiniuj "obchod"
1) skladowe Ci pomogą ;] Dowod nie jest trudny -- 17 września 2009, 01:03 --4) to oczywiscie jest bzdura jaka napisalem. Szkoda, że nikt na to mi nie zwrocil uwagi. Cos się jutro wymysli
Niech \(\displaystyle{ (V _{1} , V _{2} , E)}\) będzie grafem dwudzielnym o największym stopniu wierzcholka rownym \(\displaystyle{ d}\). Wowczas \(\displaystyle{ \chi ' (G)=d}\)
Dowod to indukcja względem \(\displaystyle{ \left| E \right|}\)
3) wzor Eulera pomoże.
2)Zdefiniuj "obchod"
1) skladowe Ci pomogą ;] Dowod nie jest trudny -- 17 września 2009, 01:03 --4) to oczywiscie jest bzdura jaka napisalem. Szkoda, że nikt na to mi nie zwrocil uwagi. Cos się jutro wymysli