4399771
Description
Flashcards by Michal Roch, updated more than 1 year ago
|
Created by Michal Roch
almost 9 years ago
|
|
| 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 |
Want to create your own Flashcards for free with GoConqr? Learn more.