Základy matematiky a statistiky pro humanitní obory II Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic {pary, xkovar3}@fi.muni.cz část 2 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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ě ... Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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}} Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 5 / 13 Základní pojmy Základní pojmy Isomorfismus – příklad Které z následujících grafů jsou isomorfní? Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 11 / 13 Některá rozšíření pojmu grafu Některá rozšíření pojmu grafu Příklad – orientovaný ohodnocený graf Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 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ů) Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 2 13 / 13