Grafy I. - selftest

Michal Roch
Flashcards by Michal Roch, updated more than 1 year ago
Michal Roch
Created by Michal Roch over 5 years ago
55
0

Description

Selftest k materiálu na grafy

Resource summary

Question Answer
Definuj stupeň uzlu v orientovaném a neorientovaném grafu V neorientovaném -> počet sousedů V orientovaném -> odchozí (-) a příchozí (+) podle počtu hran
Jak lze v definici grafu určit hrany Funkcí incidence nebo množinou dvojic uzlů
Co je to prostý graf Graf bez rovnoběžných hran, tj. množin hran, které mají shodné uzly
Co je to obyčejný graf Prostý graf, který neobsahuje smyčky, tj. hrany které vedou do stejného uzlu
Co je to podgraf Podmnožina uzlů a hran
Co je to faktor Podgraf, který nevynechá žádné uzly
Co je to kostra grafu Minimální podgraf, který neobsahuje cykly a propojuje všechny uzly
Co je to strom Obyčejný graf, který neobsahuje kružnice
Co říká handshaking lemma Suma stupňů uzlu je rovna dvojnásobku jeho hran, tedy že každý graf má sudý počet uzlů, který obsahuje lichý počet hran
Co je to sled a kdy je uzavřený Posloupnost hran a uzlů v neorientovaném grafu. Uzavřený je když počáteční a koncový uzel je stejný
Co je to tah Otevřený sled, kde se neopakují hrany
Co je to ceta Otevřený sled, kde se neopakují hrany ani uzly
Co je to uzavřený tah Uzavřený sled, kde se neopakují hrany
Co je to cyklus Uzavřený sled, kde se neopakují hrany ani uzly
Co je to spojení a co pro něj platí Orientovaný sled. Zrušení orientace zachová sled v neorientovaném grafu
Jak vznikne průnik a sjednocení grafů Průnikem / sjednocení množin jeho hran, uzlů a incidencí
Kdy jsou grafy vzájemně disjunktní Když jejich průnik dá prázdný graf
Jak vznikne rozdíl grafů Odstraněním uzlů a hran odečítaného grafu. Sjednocení odečteného grafu s odečítaným dá graf původní.
Jak vznikne doplněk grafu Odečtením současného grafu od jeho úplné varianty
Co je to bijekce grafu Zobrazení grafu (přejmenování uzlů a hran), které zachová velikost množin uzlů a hran a stupně všech uzlů
Co je to izomorfismus grafu Bijektivní zobrazení, které zachovává strukturu - tj. uzly zůstanou vzájemně stejně propojené i po přejmenování
Co je to úplný graf Graf, kde je každý uzel propojen s každým
Co je to prázdný graf Graf, který neobsahuje žádné uzly ani hrany
Co je to diskrétní graf Graf, který obsahuje pouze izolované uzly (nemá hrany)
Co je to bipartitní graf Graf, který lze rozdělit na dvě části, kde žádné uzly v dané části nejsou propojené hranou a každý uzel z jedné části je propojen s každým uzlem z druhé části
Co je to izolovaný uzel Uzel, který nemá sousedy
Co je to Eulerův tah Uzavřený tah, který projde všechny vrcholy grafu
Kdy je graf souvislý resp. silně souvislý Když mezi libovolnými dvěma uzly existuje tah, resp. spojení
Co je to (silná) komponenta grafu Každý maximálně (silně) souvislý podgraf
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.
Michal Roch
Data Structures & Algorithms
Reuben Caruana
Types and Components of Computer Systems
Jess Peason
Input and Output Devices
Jess Peason
Types and Components of Computer Systems
Michael Sudduth
Data Structures & Algorithms
Martyn Haigh
Input Devices
Jess Peason