#
1) grafy, representace, algoritmy

   definice, graf, hrany, vrcholy, orientovaný, ohodnocený

   representace
      - matice sousednosti
        - matice vzdálenosti
      - matice incidence
      - seznam následníků/předchůdců

   (!) Q: jak representovat data => jaké operace potřebujeme provádět

   sled, tah, cesta, kružnice

   problémy:
      souvislost
      - hledaní cesty odevšud všude
      - union-find

         1 2 3 4 5 6 7 8
         ---------------
         1 2 3 4 5 6 7 8
         1 2 3 1 5 6 7 8
         1 2 3 1 5 6 7 7
         1 2 3 1 2 6 7 7
         1 2 2 1 2 6 7 7
         1 2 2 1 2 6 1 1
         1 1 1 1 1 6 1 1

         ^     ^

            - zjistit, jestli jsou vrcholy ve stejné komponentě: O(1)
            - sjednotit komponenty souvislosti: O(N)

                       8
         1-4   *       7
         7-8   *       6
         2-5   *       5
         5-3   *       4
         1-7   *       3
         1-3   *       2
         1-5

                   O(V*V)

      strom
      - souvislý a bez kružnic
      - bez kružnic a obsahuje právě jednu komponentu souvislosti
      - souvislý a má právě N-1 hran

      nejkratší cesta
      - Dijstrův algoritmus
      - Bellman-Fordův algoritmus
      - Floyd-Warshallův algoritmus

      minimální kostra
      - Kruskalův
      - Borůvkův
      - Jarníkův/Primův

      nejdelší/maximální kostra

      maximální cesta
      - umíme v DAG

      topologické uspořádání
      - algoritmus

         1->4     5
         7->8     2
         2->5     3
         5->3     1
         1->7     1
         1->3     15
         1->5     2
         4->5     3
         7->3     8


         1  -
         2  -
         3  5 1 7
         4  1
         5  2 1 4
         6  -
         7  1
         8  7
         -----------------------------
         1  7  4  2  5  3  6  8
         0  1  5  -  8 15  -  3

         O(|V|*|V|)
         O(|V|+|E|)



2) optimální vyhledávací strom

         10
    5          15
  1   99

  známe ČETNOSTI jednotlivých hodnot


   a  b  c

      b
   a     c    = dokonale vyvážený strom


   a  b  c
   2  5  10


      b
   a     c        2x2 + 5x1 + 10x2 = 29 porovnání



         c        2x2 + 5x3 + 10x1 = 29
   a
      b

         c        2x3 + 5x2 + 10x1 = 26
      b
   a

   Strom, ve kterém vyhledání všech prvků s jejich četnostmi
   bude vyžadovat nejmenší počet porovnání.


   Nejlepší (optimální) strom:
     - jeho levý podstrom je také optimální
     - jeho pravý podstrom je také optimální


   funkce NajdiNejlepší(Pod)Strom(int prvni, poslední)    1..N,1..N

   Co budeme procházet:
      Který prvek bude kořenem (pod)stromu

                                           k
   optimální podstrom pro prvni..(k-1)         optimální podstrom pro (k+1)..posledni
   ------------------------------------------

            A   B   C   D   E
           25  12   1  18   7


            A     B     C     D     E
        1  25    12     1    18     7
        2  49A   14B   20D   32D    -
        3  52A   45D   34D
        4
        5



       A                            B
         B = 25x1 + 12*2 = 49     A    = 25x2 + 12*1 = 62

      BC: 12*1 + 1*2 = 14
      CD: 18*1 + 1*2 = 20
      DE: 18*1+7*2 = 32

      ABC:   A                 B                      C
              BC              A C                   AB
            (25+12+1) + 14    25*2 + 12*1 + 1*2     (25+12+1) +49
                              (25+12+1) + 14 + 1

     (25+12+1) +  14             ... +(25+1)         ... +49
            =>  52A
      BCD:   (12+1+18)
             B: +CD = 20        C: +B+D = +12+18   D: BC = +14

      CDE:  (1+18+7)   C: 32  D: +1+7=8   E: +20


            A     B     C     D     E
        1  25    12     1    18     7
        2  49A   14B   20D   32D    -
        3  52A   45D   34D
        4 101A/B
        5

  ABCD: (25    12     1    18) = 56
        A:  +45  B: +25+20  C: +49+18  D: 52

  BCDE:
---------------------------
06.05.2020 15:53:51