Grafy I.

Michal Roch
Mind Map by Michal Roch, updated more than 1 year ago
Michal Roch
Created by Michal Roch over 5 years ago
184
0

Description

Teorie grafů a základní pojmy

Resource summary

Grafy I.
  1. Handshaking lemma
    1. Neorientovaný graf
      1. Suma stupňů všech uzlů je rovna dvojnásobku počtu hran grafu
        1. Sudý počet uzlů má lichý stupeň
        2. Orientovaný graf
          1. Suma odchozích a příchozích stupňů všech uzlů je rovna dvojnásobku počtu hran grafu
        3. Úplnost grafu
          1. Kompletní (úplný graf)
            1. Všechny uzly se všemi
              1. Právě V nad 2 hran
                1. Stupeň každého uzlu je V - 1
                  1. Orientovaný grafu kde platí oba směry orientace nazýváme úplný symetricky orientovaný graf
                  2. Prázdný graf
                    1. Žádné uzly ani hrany
                    2. Diskrétní graf
                      1. Pouze izolované uzly bez hran
                      2. Bipartitní graf
                        1. Částečně úplný
                          1. Graf lze rozdělit na dvě části
                            1. Uzly mezi sebou v dané části nemají žádné hrany
                              1. Z každého uzlu v jedné části vede hrana do každého uzlu v druhé části
                          2. Posloupnosti v grafu
                            1. Sled (walk) je posloupnost uzlů a hran s počátečním a koncovým uzlem
                              1. Otevřený
                                1. Hrany ani uzly se nemůžou opakovat
                                  1. Cesta (path)
                                  2. Hrany se nemůžou opakovat
                                    1. Tah (trail, chain)
                                  3. Uzavřený
                                    1. Uzavřený sled je sled, kde počáteční a koncový uzel je stejný
                                      1. Hrany se nemůžou opakovat
                                        1. Uzavřený tah (cycle)

                                          Annotations:

                                          • V češtině se cyklus používá pro označení kružnic.  Uzavřený tah, který projde všechny hrany grafu, je Eulerovský tah
                                        2. Hrany ani uzly se nemůžou opakovat
                                          1. Kružnice, cyklus (circuit)

                                            Annotations:

                                            • Kružnicí označujeme spíše neorientované grafy Cyklus spíše v orientovaném  grafu
                                        3. V orientovaném grafu
                                          1. Nazýváme sled spojení
                                            1. Ve spojení lze propojit pouze uzly ve směru orientace
                                              1. Tah (cesta, cyklus) v orientovaném je také tah v neorientovaném po zrušení orientace
                                          2. Definice a základní vlastnosti
                                            1. Orientace
                                              1. V neorientovaném grafu na pořadí uzlů ve dvojici nezáleží
                                                1. Orientovaný graf má uspořádanou množinu dvojic uzlů
                                                2. G={V,E}
                                                  1. V = uzly (vertices)
                                                    1. Stupeň uzlu je počet jeho sousedů
                                                      1. Orientované grafy rozlišují odchozí(-) a příchozí(+) stupeň
                                                      2. Izolovaný uzel nemá sousedy
                                                      3. E = hrany (edges)
                                                        1. Počet hran je max E nad 2

                                                          Annotations:

                                                          • E nad 2 je počet hran v souvislém grafu, tj. grafu, kde každý uzel je spojen s každým
                                                          1. Lze přidělovat váhu - obvykle funkcí
                                                            1. Smyčka je hrana která vede ze stejného uzlu do kterého přichází
                                                              1. Graf bez rovnoběžných hran a smyček je tzv. obyčejný
                                                              2. Rovnoběžné hrany jsou hrany, které mají shodnou dvojici uzlů
                                                                1. Graf bez rovnoběžných hran je tzv. prostý
                                                                  1. Graf s rovnoběžnými hranami je multigraf
                                                                  2. V grafu určeny funkcí incidence (hranám přiděluje uzly), nebo množinou dvojic uzlů
                                                                2. Podgrafy
                                                                  1. Podmnožina uzlů a hran je podgraf
                                                                    1. Podgraf, který redukuje pouze hrany a nevynechá žádný uzel je faktor
                                                                      1. Faktorizace grafu je rozpad grafu na všechny jeho faktory
                                                                      2. Kostra je minimální podgraf, která spojuje všechny uzly grafu a zároveň neobsahuje cykly
                                                                        1. Vynechávám hrany tak dlouho dokud můžu
                                                                          1. Žádný uzel nesmím izolovat
                                                                            1. Každý uzel má maximálně dva sousedy
                                                                          2. Strom
                                                                            1. Obyčejný graf, který neobsahuje kružnice
                                                                          3. Souvislost
                                                                            1. Komponenta je každý maximálně souvislý podgraf
                                                                              1. Neorientovaný graf = slabá
                                                                                1. Existuje tah mezi libovolnými dvěma uzly
                                                                                2. Orientovaný graf = silná
                                                                                  1. Existuje spojení mezi libovolnými dvěma uzly
                                                                                    1. Každá jeho hrana je obsažena v nějakém cyklu
                                                                                  2. Operace
                                                                                    1. Sjednocení
                                                                                      1. Sjednocení množiny uzlů, hran a incidencí
                                                                                      2. Průnik
                                                                                        1. Průnik množiny uzlů, hran a incidencí
                                                                                          1. Vznikne-li průnikem prázdný graf, grafy jsou vzájemně disjunktní
                                                                                          2. Doplněk
                                                                                            1. Graf, který vznikne odečtením G od úplého grafu nad stejnou množinou uzlů
                                                                                            2. Rozdíl
                                                                                              1. Laicky - z grafu A odstraním uzly a hrany grafu B
                                                                                                1. Formálně - výsledek je graf, jehož sjednocení s odečteným grafem dá graf původní
                                                                                              2. Zobrazení
                                                                                                1. Bijekce
                                                                                                  1. Vzájemně jednoznačné zobrazení
                                                                                                    1. Přejmenuju uzly a hrany, žádnou hranu ani uzel nevynechám a stupně uzlů zůstanou stejné
                                                                                                    2. Izomorfismus
                                                                                                      1. Bijekce která zachovává strukturu
                                                                                                        1. Přejmenované uzly jsou propojeny se stejnými uzly jako předtím, než došlo k přejmenování
                                                                                                        2. Bijekce která není izomorfismus
                                                                                                          1. Mohu uzly a hrany přejmenovat a žádný nevynechat, ale přejmenované uzly budou vzájemně propojené jinak, než předtím
                                                                                                        3. SELFTEST

                                                                                                          Attachments:

                                                                                                          Show full summary Hide full summary

                                                                                                          Similar

                                                                                                          Common Technology Terms
                                                                                                          Julio Aldine Branch-HCPL
                                                                                                          Network Protocols
                                                                                                          Shannon Anderson-Rush
                                                                                                          Introduction to the Internet
                                                                                                          Shannon Anderson-Rush
                                                                                                          Computational Data
                                                                                                          Shannon Anderson-Rush
                                                                                                          Grafy I. - selftest
                                                                                                          Michal Roch
                                                                                                          Maths
                                                                                                          xcathyx99
                                                                                                          Data Structures & Algorithms
                                                                                                          Reuben Caruana
                                                                                                          Maths Revision
                                                                                                          Asmaa Ali
                                                                                                          Types and Components of Computer Systems
                                                                                                          Jess Peason
                                                                                                          Input and Output Devices
                                                                                                          Jess Peason