szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 lip 2015, o 11:02 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
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 G i oznaczmy go 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 V(T) \neq V(G) to istnieje v \in V(T) sąsiadujący z pewnym u \in V(G)-V(T). u istnieje bo jeśli V(G) \neq V(T)  \wedge  V(T) \subset V(G) to istnieje taki zbiór V(G)-V(T), że udo niego należy.

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

4. T' jest podgrafem G bo V(T') \subset V(G) i E(T') \subset E(G)). T'jest właściwym podgrafem - sprzeczność z założeniem, że Tbył 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 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 K_{n} o wierzchołkach v_{1},v_{2}, ... v_{n} z funkcją kosztu
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) \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 2) w następujący sposób:
n-1 \rightarrow 1 \\
 n-2 \rightarrow 2
.
.
n-k \rightarrow k
W przypadku,gdy n jest nieparzyste należy połączyć je dodatkowo z wierzchołkiem o nr 1.

d)
Tutaj dowolna konstrukcja drzewa rozpinającego da nam wagę n-1??

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

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


Możesz wyjaśnić te oznaczenia? Bo nie wydaje mi się żeby były w miarę standardowe.
Góra
Mężczyzna Offline
PostNapisane: 28 lip 2015, o 13:27 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Posta właśnie edytowałem bo nie zauważyłem błędu. Więc tak:
K to spójność wierzchołkowa
K' to spójność krawędziowa
< to oznaczenie, że jeden graf jest podgrafem drugiego
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 dziwne zadanie z matematyki dyskretnej  mkarwin  1
 takze dziwne zadanie z matematyki dyskretnej  mkarwin  5
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl