DSM2 Cv 7
Kostry grafů
Definice kostry grafu: Nechť G = V , E je souvislý graf. Kostrou grafu G nazýváme každý jeho podgraf, který má stejnou množinu vrcholů a je zároveň stromem.
1. Nakreslete všechny kostry následujících grafů: (a)
K 3 , (b) K 2,2 , (c) C5 .
Počty koster některých speciálních grafů: - pro n ≥ 2 graf Dn nemá žádnou kostru, - pro n ≥ 2 je počet koster grafu K n roven n n−2 , - pro n ≥ 3 je počet koster grafu Cn roven n, - pro souvislý graf obsahující jedinou kružnici délky k platí, že počet všech jeho koster roven k, - každý strom má pouze jedinou kostru, - počet všech koster grafu Pn je roven 1, - graf K m ,n má právě m n−1 ⋅ n m−1 koster.
Určení počtu všech koster grafu pomocí Laplaceovy matice: Je dán graf G = V , E
s pevně zvoleným číslováním na množině
vrcholů {v1 , v2 ,⋯, vn } . Laplaceovou maticí grafu G nazýváme matici LG = ( lij ) , kde:
lii = deg G ( vi ) pro i = 1,⋯, n , lij = 1 , jestliže vrcholy vi , v j sousedí v grafu G, lij = 0 , pokud tyto vrcholy nesousedí. Počet všech koster grafu G vypočteme takto: - pro libovolnou dvojici čísel i, j označíme symbolem LG ,i , j submatici matice LG , která vznikne vyškrtnutím i – tého řádku a j – tého sloupce, - číslo det LG ,i , j udává počet všech koster grafu G.
2. Vypočtěte počet všech koster následujících grafů a nakreslete je: (a)
K 2 + D2 , (b) K1,2 □ K 2 .
3. Pomocí Laplaceovy následujících grafů: (a)
matice
určete
počet
všech
koster
P4 , (b) K1,2 + K 2 , (c) K1,2 × K 2 , (d) D1 + K 2 + K 2 ,
(e) K1,2 □ K 2 . 4. Kostrou nesouvislého grafu rozumíme les vzniklý z koster jednotlivých grafů. Kolik koster má graf K 4 + C4 ?
Metody sestavení kostry grafu: Postup 1 (ubírání hran): (1) Pokud graf neobsahuje kružnici, máme hledanou kostru a postup končí. Jinak postoupíme na bod (2). (2) Vybereme libovolnou hranu, která leží na kružnici a tu z grafu ubereme (její vrcholy ale ne). Se změněným grafem postoupíme na bod (1).
Postup 2 (přidávání hran): Vycházíme z toho, že na množině V je zadán souvislý graf s n vrcholy, jehož hrany jsou očíslovány jako e1 , e2 ,⋯, em . Začneme s diskrétním grafem na množině V. Postupně přidáváme hrany podle jejich očíslování. Pokud po přidání nějaké hrany vznikne v grafu kružnice, vrátíme se o krok zpět a přidáme další hranu v pořadí. Postup opakujeme, pokud nevyčerpáme všechny hrany grafu. Postup samozřejmě ukončíme, pokud počet hran dosáhne hodnoty n - 1.
Ohodnocené grafy
Definice ohodnoceného grafu: Jedná se o dvojici
( G, w ) ,
kde
G = V , E je graf a w : E → R je zobrazení množiny všech hran do množiny reálných čísel. Zobrazení w se nazývá váhová funkce a pro každé e ∈ E se hodnota w ( e ) nazývá váha hrany e. Váhou grafu, případně váhou podgrafu rozumíme součet vah všech jeho hran.
Minimální (maximální) kostra grafu: Pokud
( G, w )
je souvislý
ohodnocený graf, nazýváme jeho minimální (maximální) kostrou tu jeho kostru, která má minimální (maximální) váhu. V každém ohodnoceném souvislém grafu existuje minimální a maximální kostra. Metoda pro nalezení minimální kostry - Hladový (Kruskalův) algoritmus: V ohodnoceném souvislém grafu s n vrcholy očíslujeme hrany e1 , e2 ,⋯, em tak, aby jejich váhy tvořily neklesající posloupnost, tedy w ( e1 ) ≤ w ( e2 ) ≤ ⋯ ≤ w ( em ) . Minimální kostru
vytváříme tak, že začneme s hranou e1 a dále přidáváme hrany tak, jak jsou v seřazeny v neklesající posloupnosti. Jakmile po přidání hrany vznikne kružnice, hranu škrtneme a přejdeme k další hraně. Postup ukončíme, když počet hran v kostře dosáhne hodnoty n − 1. Váha minimální kostry je součtem vah hran, které ji tvoří. 5. V grafu H jsou hranám přiděleny ceny (váhy). Matice cen je zadána tak, že její řádky a sloupce odpovídají po řadě vrcholům 1, …, 9. Když hrana v grafu neexistuje, je na jejím místě 0 1 3 − 1 2 2 − 1 0 2 1 2 − − − − 0 1 3 − − − 3 0 1 − − − 2 v matici pomlčka: 0 2 1 3 2 (matice je 0 1 1 − 0 2 2 0 1 0 symetrická, uvádíme tedy jen její naddiagonální část). Pomocí hladového algoritmu najděte aspoň dvě nejlevnější (maximální) kostry a zakódujte je Prüferovým kódem.
6. Na následujícím grafu jsou uvedeny náklady na měsíční pronájem počítačové linky mezi různými městy. Chceme-li mít zajištěno spojení každých dvou měst, musíme si pronajmout kostru tohoto grafu. (a) Pomocí Laplaceovy matice určete, kolik má tento graf koster, (b) najděte nejlevnější a nejdražší kostru a zakódujte je Prüferovým kódem, (c) najděte střed tohoto grafu, (d) jak byste pro ohodnocený graf změnili definici poloměru a průměru? Určete tyto hodnoty.
7. Je dána matice cen grafu:
0 1 − − 0 3 − 0 2 0
− 1 2 1 3 2 . 2 − 0 3 0
Hladovým algoritmem určete cenu minimální a maximální kostry. Kolik minimálních koster má graf? Nějakou minimální a maximální kostru zakódujte Prüferovým kódem.
