# Programování II pro matematiky ## Teoretické cvičení 10 **5. 5. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Příklady - Řešení příkladů --- ### Opakování - graf - Matice sousednosti - Je vhodná pro malé grafy s velkým množstvím hran
--- ### Opakování - graf - Seznam následníků
--- ### Opakování - graf - Seznam hran
--- ### Opakování - graf - Matice incidence - (vhodné pro grafy, které mají více hran než vrcholů)
--- ### Opakování - BFS vs DFS
--- ### Příklady (1) Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě. **Rekurze:** 1. Nalezněte všechny různé rozklady čísla $N$. 2. Nalezněte všechny různé rozklady čísla $N$, které jsou tvořený přesně $K$ celočíselnými sčítanci. --- ### Příklady (2) Zapište následující graf pomocí všech reprezentací:
Určete pro všechny reprezentace prostorovou složitost pro uložení $N$ vrcholů a $M$ hran. Určete časovou složitost pro následující operace: - Je mezi `x` a `y` hrana? - Vypsání všech následovníků vrcholu `x`. - Přidání hrany nebo vrcholu do grafu. --- ## Příklady (3) Máme načtený graf, který má $N$ vrcholů a $M$ hran. Najděte algoritmus a určete jeho časovou a prostorovou složitost. Promyslete, jak se algoritmus bude lišit pokud bude reprezentován pomocí matice sousednosti a seznamu následníků. 1. Nalezněte vrchol, který má nejvíce následovníků. 2. Určete kolik má daný graf komponent souvislosti. 3. Určete jestli daný graf obsahuje cyklus. 4. Jaký je vztah mezi počtem vrcholů a počtem hran? 5. Je-li $A$ matice sousednosti grafu, co popisuje matice $A^2$? A co $A^k$? (Mocniny matic definujeme takto: $A^1=A$, $A^{k+1}=A^kA$.) 6. Upravte BFS tak, aby pro každý dosažitelný vrchol zjistilo, kolik do něj vede nejkratších cest z počátečního vrcholu. Zachovejte lineární časovou složitost. 7. Jakou časovou složitost by DFS mělo, pokud bychom graf reprezentovali maticí sousednosti? --- ### Řešení (1) Nalezněte všechny různé rozklady čísla $N$. viz přednáška https://ksvi.mff.cuni.cz/~topfer/ppt/A7%20BVS%20a%20rekurzivni%20generovani.pdf --- ### Řešení (2) Nalezněte všechny různé rozklady čísla $N$, které jsou tvořený přesně $K$ celočíselnými sčítanci. 8 = (1 + 1 + 1 + 1) + (1 + 1) + (1 + 1) -- **Algoritmus:** ```python def _rozklad(N, K, index, c): """ N - kolik zbývá rozložit index - kolikátý sčítanec vytváříme """ if N == 0: # rozklad je hotov print(pole[1:index]) else: # přidáme do pole[index] index-tý člen rozkladu for i in range(1, min(N, pole[index-1], N-(K-index)) + 1): pole[index] = i rozklad(N-i, K, index+1, pole) def rozklad(N, K): _rozklad(N, K, 1, [N] * (K+1)) ``` -- Časová složitost $\mathcal{O}({N - 1 \choose K-1}/K!)$, paměťová složitost $\mathcal{O}(K)$