Zadania z grafów

[Student_matmy]

Witam

Prosiłbym o pomoc z dwoma zadaniami z grafów.

Zadanie 1. Niech G będzie spójnym grafem o n wierzchołkach. Pokazać, że dla dowolnego \(\displaystyle{ k \in \left\{ 1,2,...,n\right\}}\) G zawiera spójny podgraf o k wierzchołkach.

Zadanie 2. Niech G=(V,E) będzie grafem i niech \(\displaystyle{ Aut\left( G\right):=\left\{ f:V \rightarrow V | f}\) jest izomorfizmem\(\displaystyle{ \right\}}\). Pokazać, że
a) Aut(G) wraz ze składaniem odwzorowań jest grupą
b) Jeśli \(\displaystyle{ G_{1}}\) jest izomorficzny z \(\displaystyle{ G_{2}}\), to grupa \(\displaystyle{ Aut\left( G_{1} \right)}\) jest izomorficzna z grupą \(\displaystyle{ Aut\left( G_{2} \right)}\)

[Kartezjusz]

ZAD1
Graf jest spójny czyli można ponumerować tak wierzchołki liczbami od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), że z wiechołka \(\displaystyle{ 1}\) do wierzchołka \(\displaystyle{ n}\) dojdziemy po krawędziach grafu "zaliczając" po kolei numerki. Jak naszą "podróż" zakończymy na \(\displaystyle{ k}\)-tym wierzchołku to dostaniemy podgraf spójny,

ZAD2
a) wszystko z definicji izomorfizmu grafów. Zapisz sobie

b) Niech \(\displaystyle{ g}\) będzie izomorfizmem grafów. \(\displaystyle{ F(f_{1}) = : g \circ f_{1}}\) określa izormorfizm jednej grupy automorfizmów w grugą.

[Student_matmy]

Dzięki za pomoc

[norwimaj]

ZAD1
Graf jest spójny czyli można ponumerować tak wierzchołki liczbami od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), że z wiechołka \(\displaystyle{ 1}\) do wierzchołka \(\displaystyle{ n}\) dojdziemy po krawędziach grafu "zaliczając" po kolei numerki.

Chcesz powiedzieć, że w każdym grafie spójnym istnieje ścieżka Hamiltona? Obawiam się, że to zbyt mocne twierdzenie, żebyśmy mogli je tu użyć, chyba że podasz dowód.

Ukryta treść:    

\(\displaystyle{ \begin{picture}(0,0)
\put(-30,30).
\put(30,-20).
\multiput(-10,0)(10,0){3}{\circle*4}
\put(0,10){\circle*4}
\put(-10,0){\line(1,0){20}}
\put(0,0){\line(0,1){10}}
\end{picture}}\)

Proponuję rozwiązywać zadanie 1. elementarnie, indukcją względem \(\displaystyle{ k}\).

Dla \(\displaystyle{ k=0}\) teza jest oczywista. Dla \(\displaystyle{ k=1}\) też.

Załóżmy, że teza zachodzi dla pewnego \(\displaystyle{ k}\), takiego że \(\displaystyle{ 1\le k <n}\). Z założenia wiemy, że istnieje \(\displaystyle{ k}\)-wierzchołkowy podgraf spójny \(\displaystyle{ S}\) grafu \(\displaystyle{ G}\). Z nierówności \(\displaystyle{ 1\le k <n}\) wynika, że istnieje wierzchołek \(\displaystyle{ w_i\in V(S)}\) oraz \(\displaystyle{ w_f\in V(G)\setminus V(S)}\). Ze spójności \(\displaystyle{ G}\) wiemy, że istnieje ciąg \(\displaystyle{ (v_1,v_2,\ldots,v_l)}\) wierzchołków \(\displaystyle{ G}\) taki, że \(\displaystyle{ v_1=w_i}\), \(\displaystyle{ v_l=w_f}\) i każde dwa kolejne są połączone krawędzią w \(\displaystyle{ G}\). Niech \(\displaystyle{ m=\min\{i\in\{1,\ldots,l\}: v_i\not\in V(S)\}}\). Napisany zbiór jest skończony i niepusty (bo \(\displaystyle{ l}\) doń należy), zatem branie minimum tego zbioru jest dobrze określone. Podgraf grafu \(\displaystyle{ G}\) o zbiorze wierzchołków \(\displaystyle{ V(S)\cup\{v_m\}}\) jest spójny i ma \(\displaystyle{ k+1}\) wierzchołków, co można łatwo sprawdzić.

[Kartezjusz]

ZAD1
Graf jest spójny czyli można ponumerować tak wierzchołki liczbami od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), że z wiechołka \(\displaystyle{ 1}\) do wierzchołka \(\displaystyle{ n}\) dojdziemy po krawędziach grafu "zaliczając" po kolei numerki.

Chcesz powiedzieć, że w każdym grafie spójnym istnieje ścieżka Hamiltona? Obawiam się, że to zbyt mocne twierdzenie, żebyśmy mogli je tu użyć, chyba że podasz dowód.

Ukryta treść:    

\(\displaystyle{ \begin{picture}(0,0)
\put(-30,30).
\put(30,-20).
\multiput(-10,0)(10,0){3}{\circle*4}
\put(0,10){\circle*4}
\put(-10,0){\line(1,0){20}}
\put(0,0){\line(0,1){10}}
\end{picture}}\)

Nie jest powiedziane,że nie bedzie trzeba zawracać i powtarzac punktow kontrolnych ale ze spójności wiemy,że kazdy z nich musimy " zaliczyć" conajmniej raz. Ponumerujmy wierzchołki, kiedy odwiedzamy je po raz pierwszy. Kiedy użyjemy liczby \(\displaystyle{ k}\), to mamy koniec.

[norwimaj]

Aha, to w porządku, chociaż to bardzo pobieżny szkic dowodu.