Zadania z matematyki dyskretnej do sprawdzenia #4

[gardner]

4.1. Udowodnić, że każdy graf spójny ma drzewo rozpinające zaczynając od zdania „Weźmy
maksymalny acykliczny podgraf rozpinający w \(\displaystyle{ G}\) i oznaczmy go \(\displaystyle{ T}\)”.

1. Takowy istnieje,bo każdy graf spójny ma drzewo rozpinające - czyli podgraf acykliczny. Co z jego maksymalnością? To taki, że dodanie kolejnej krawędzi spowoduje pojawienie się cyklu.

2. Jeśli \(\displaystyle{ V(T) \neq V(G)}\) to istnieje \(\displaystyle{ v \in V(T)}\) sąsiadujący z pewnym \(\displaystyle{ u \in V(G)-V(T)}\). \(\displaystyle{ u}\) istnieje bo jeśli \(\displaystyle{ V(G) \neq V(T) \wedge V(T) \subset V(G)}\) to istnieje taki zbiór \(\displaystyle{ V(G)-V(T)}\), że \(\displaystyle{ u}\)do niego należy.

3. Wówczas graf \(\displaystyle{ T'=(V(T) \cup \left\{ u\right\},E(T) \cup \left\{ uv\right\}}\)
jest drzewem ponieważ dodajemy do drzewa \(\displaystyle{ T}\) jeden wierzchołek \(\displaystyle{ u}\) i łączymy krawędzią z \(\displaystyle{ v}\) co nie spowoduje pojawienia się cyklu.

4. \(\displaystyle{ T'}\) jest podgrafem \(\displaystyle{ G}\) bo \(\displaystyle{ V(T') \subset V(G)}\) i \(\displaystyle{ E(T') \subset E(G))}\). \(\displaystyle{ T'}\)jest właściwym podgrafem - sprzeczność z założeniem, że \(\displaystyle{ T}\)był właściwym podgrafem.


4.2. Udowodnić, że każdy graf spójny ma drzewo rozpinające zaczynając od zdania „Weźmy
minimalny spójny podgraf rozpinający w \(\displaystyle{ G}\)”.

Czy jeśli bierzemy minimalny spójny podgraf rozpinający to wychodzimy od razu z założenia,że jest on acykliczny? Nie bardzo widzę różnicę w obydwu zadaniach - jak się ma maksymalny podgraf rozpinający acykliczny do minimalnego rozpinającego?

4.3. Znaleźć najtańsze drzewo rozpinające w \(\displaystyle{ K_{n}}\) o wierzchołkach \(\displaystyle{ v_{1},v_{2}, ... v_{n}}\) z funkcją kosztu
\(\displaystyle{ a. k(v_{i}v_{j})=\left| i-j\right| \\
b. k(v_{i}v_{j})=i+j \\
c. k(v_{i}v_{j})=(i+j) \pmod{n} \\
d. k(v_{i}v_{j})=1 (\mbox{stała})}\)

Tutaj pomijając obliczenia:
a) \(\displaystyle{ \lfloor\frac{n+1}{2} \rfloor}\)
Zaczynamy konstrukcję od wierzchołka o takim numerze ( z uwagi,że to rozpatrujemy graf pełny przechodzimy od niego do pozostałych wierzchołków - zawsze zaczynając od niego)

b) Tutaj należy oznaczyć wierzchołki i zacząć konstrukcję od tego z najmniejszym numerem (konstrukcja j.w)

c)Tutaj należy sparować wierzchołki (połączyć krawędzią dane \(\displaystyle{ 2}\)) w następujący sposób:
\(\displaystyle{ n-1 \rightarrow 1 \\
n-2 \rightarrow 2}\)
.
.
\(\displaystyle{ n-k \rightarrow k}\)
W przypadku,gdy \(\displaystyle{ n}\) jest nieparzyste należy połączyć je dodatkowo z wierzchołkiem o nr \(\displaystyle{ 1}\).

d)
Tutaj dowolna konstrukcja drzewa rozpinającego da nam wagę \(\displaystyle{ n-1}\)??

Teraz seria,która wydaje mi się bardzo oczywista i prosiłbym o jakiś przykład poprawnego rozwiązania.
4.4. \(\displaystyle{ K'(K_{n})=n-1}\)
4.5. \(\displaystyle{ K(G)=|V(G)|-1}\) wtedy i tylko wtedy, gdy \(\displaystyle{ G=K\left| V(G)\right|}\).
4.6.\(\displaystyle{ H < G \Rightarrow K(H) \le K(G)}\)
4.7. \(\displaystyle{ H < G \Rightarrow K(H ) \le K'(G)}\)
4.8. Jeśli \(\displaystyle{ K(G)=k}\) to \(\displaystyle{ G}\) zawiera \(\displaystyle{ k}\)-elementowy zbiór wierzchołków \(\displaystyle{ S}\) taki, że \(\displaystyle{ G-S}\) jest spójny.

[wiedzmac]

Teraz seria,która wydaje mi się bardzo oczywista i prosiłbym o jakiś przykład poprawnego rozwiązania.
4.4. \(\displaystyle{ K^{'}(K_{n})=n-1}\)
4.5. \(\displaystyle{ K(G)=|V(G)|-1}\) wtedylko gdy \(\displaystyle{ G=K\left| V(G)\right|}\).
4.6.\(\displaystyle{ H < G \Rightarrow K(H) ≤ K(G)}\)
4.7. \(\displaystyle{ H < G \Rightarrow K(H ) ≤ K^{'}(G)}\)
4.8. Jeśli \(\displaystyle{ K(G)=k}\) to \(\displaystyle{ G}\) zawiera \(\displaystyle{ k}\)-elementowy zbiór wierzchołków \(\displaystyle{ S}\) taki, że \(\displaystyle{ G-S}\) jest spójny.

Możesz wyjaśnić te oznaczenia? Bo nie wydaje mi się żeby były w miarę standardowe.

[gardner]

Posta właśnie edytowałem bo nie zauważyłem błędu. Więc tak:
\(\displaystyle{ K}\) to spójność wierzchołkowa
\(\displaystyle{ K'}\) to spójność krawędziowa
\(\displaystyle{ <}\) to oznaczenie, że jeden graf jest podgrafem drugiego