Poznámky: Teorie z předmětu Teorie grafů a její aplikace v dopravě

1. Definice základních pojmů (graf, vrchol, hrana, stupeň vrcholu, incidence)
• Neorientovaný graf - uspořádaná trojice G = (V,X,p) {Vrcholy, X hrany, p incidence}
• Incidence - Přiřazení množiny hran na množinu všech neuspořádaných dvojic V
• Stupeň vrcholu - Počet hran incidujících s vrcholem
• Multigraf - připouští existenci násobných hran.
• Prostý graf - Nepřipouští existenci násobných hran
• Obyčejný - Nepřipouští existenci násobných hran a smyček
• Triviální - Pouze 1 V
• Prázdný - V = ; X =
• Diskrétní - Množina hran je
• Kompletní - Mezi každou dvojicí V X
• Acyklický graf - Takový, který neobsahuje jako svůj podgraf kružnici.
• Pravidelný graf - k-tého stupně, Pokud jeho všechny vrcholy mají stupeň k
• Vrcholově/Hranově ohodnocený - jestliže existuje funkce o(v)/o(h) která přiřadí každému vrcholu/hraně kladné číslo...

2. Podgrafy, různé typy podgrafů
• Pod(nad)grafem - G=(V,X,p) rozumíme: `G=(`V,`X,`p) pro kt.: `VV, `XX a pro hranu h`X platí `p(h)=p(h)
• Indukované podgrafy - množinou hran nebo vrcholů, nebo vypuštěním množiny hran a vrcholů