Základy matematiky a statistiky
pro humanitní obory
II
Vojtěch Kovář
Fakulta informatiky, Masarykova univerzita
Botanická 68a, 602 00 Brno, Czech Republic
xkovar3@fi.muni.cz
část 10
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 1 / 13
Obsah přednášky
Obsah přednášky
Graf
Základní pojmy
Typy grafů
Některá rozšíření pojmu grafu
Analogie se známými pojmy
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 2 / 13
Graf Graf
Graf
▶ Graf G je dvojice (V , E)
▶ V = množina vrcholů (též G(V ))
▶ E = množina hran (též G(E))– obsahuje vybrané dvouprvkové
podmnožiny V
▶ Základní model pro mnoho praktických aplikací
▶ mapy – maps.google, mapy.cz
▶ počítačové sítě
▶ modelování procesů
▶ konečné automaty
▶ syntaktické rozbory
▶ sémantické sítě
▶ ...
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 3 / 13
Graf Graf
Příklad grafu
V = {1, 2, 3, 4, 5, 6}
E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 4 / 13
Základní pojmy Základní pojmy
Základní pojmy
▶ Sousední vrcholy
▶ spojené nějakou hranou
▶ Stupeň vrcholu
▶ počet hran, které z daného vrcholu vychází
▶ Podgraf grafu G
▶ obsahuje pouze vybrané vrcholy a hrany z grafu G
▶ hrany musí být pouze mezi vybranými vrcholy (výsledek musí
opět tvořit graf)
▶ Isomorfismus nezi grafy G a G’
▶ bijekce f : V (G) → V (G′) taková, že {u, v} je hrana v G
právě tehdy, když {f (u), f (v)} je hrana v G′
▶ grafy jsou isomorfní (shodné), pokud mezi nimi existuje
isomorfismus
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 5 / 13
Základní pojmy Základní pojmy
Isomorfismus – příklad
Které z následujících grafů jsou isomorfní?
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 6 / 13
Typy grafů Typy grafů (I)
Typy grafů (I)
▶ Kružnice (délky n > 2)
▶ V = {1, 2, 3, ..., n}
▶ E = {{1, 2}, {2, 3}, ..., {n − 1, n}, {n, 1}}
▶ stejný počet vrcholů a hran
▶ všechny vrcholy stupně 2
▶ nákres grafu tvoří kružnici
▶ Cesta (na n vrcholech)
▶ V = {1, 2, 3, ..., n}
▶ E = {{1, 2}, {2, 3}, ..., {n − 1, n}}
▶ kružnice s jednou chybějící hranou
▶ počáteční a koncový vrchol
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 7 / 13
Typy grafů Typy grafů (I)
Typy grafů (II)
▶ Úplný graf (na n vrcholech)
▶ V = {1, 2, 3, ..., n}
▶ E = {{u, v} | u, v ∈ V }
▶ každé dva vrcholy jsou spojeny hranou
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 8 / 13
Typy grafů Podgrafy
Zajímavé podgrafy
▶ Cyklus (kružnice) v grafu
▶ podgraf, který je isomorfní s nějakou kružnicí
▶ Cesta v grafu
▶ podgraf, který je isomorfní s nějakou cestou
▶ Klika v grafu
▶ podgraf, který je isomorfní s nějakým úplným grafem
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 9 / 13
Typy grafů Typy grafů (III)
Typy grafů (III)
▶ Acyklický, resp. „les”
▶ neobsahuje kružnici (cyklus) jako podgraf
▶ Souvislý
▶ mezi každými dvěma vrcholy existuje cesta
▶ Strom
▶ acyklický souvislý graf
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 10 / 13
Některá rozšíření pojmu grafu Některá rozšíření pojmu grafu
Některá rozšíření pojmu grafu
▶ Orientovaný graf
▶ hrany jsou orientovány
▶ → zdrojový a cílový vrchol
▶ → množina hran je množina uspořádaných dvojic
▶ Ohodnocený graf
▶ hrany jsou ohodnoceny (např. vzdáleností mezi vrcholy)
▶ formálně funkce e : G(E) → R
▶ Multigraf
▶ povoluje více hran mezi dvěma stejnými vrcholy
▶ povoluje hrany začínající a končící ve stejném vrcholu
(„smyčky”)
▶ Výše uvedené pojmy se mohou libovolně kombinovat
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 11 / 13
Některá rozšíření pojmu grafu Některá rozšíření pojmu grafu
Příklad – orientovaný ohodnocený graf
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 12 / 13
Analogie se známými pojmy Analogie se známými pojmy
Analogie se známými pojmy
▶ Graf lze popsat jako relaci na množině vrcholů
▶ množina hran je chápána jako relace
▶ orientovaný graf – nereflexivní relace
▶ neorientovaný graf – nereflexivní symetrická relace
▶ Přechodový graf konečného automatu
▶ orientovaný ohodnocený multigraf
▶ ohodnocení symboly abecedy (nikoli čísly)
▶ (navíc máme vrcholy dvou typů)
Vojtěch Kovář (FI MU Brno) PLIN004 část 10 13 / 13