Průvodce IB000 Matematické základy informatiky

Cvičení 7: Pojem grafu, základní vlastnosti

Rámcová náplň cvičení

Definice grafu

Na látku využívající grafické zobrazení binárních relací a funkcí přímo navazuje abstraktní pojem grafu, který vlastně není ničím jiným než binární ireflexivní symetrickou relací, ale na druhou stranu nabízí mnohem širší možnosti použití.

  • Formální definice grafu, její vztah k názornému nakreslení obrázkem a k běžným způsobům reprezentace grafu v počítači (maticí sousednosti nebo seznamy sousedů). Rozdíl mezi jednoduchým grafem a multigrafem.
  • Pojmy hran, stupňů vrcholů, kružnic a cest, podgrafů a podobně. Vše k procvičení především na názorných obrázcích. Triviální důkaz toho, že součet stupňů je sudý.

Isomorfismus

  • Isomorfismus grafů, jeho poznání a taky zdůvodnění neisomorfismu v různých příkladech. Důležitost "pěkného" obrázku grafu.
  • Při zdůvodňování různosti grafů je potřeba pochopit, že na to není "univerzální recept", ale řešení se hledají ad hoc podle aktuální situace - třeba nesouhlasící stupně, nesouhlasící jednoduché podgrafy, atd.

Stromy

Druhá část se pak (stručně) soustředí na jeden speciální druh grafů - stromy.

  • Definice jako souvislý graf bez kružnic. Běžné vlastnosti, převážně odvozené ze základního faktu, že strom obsahuje vrchol stupně 1, pokud má více než vrchol. Počet hran stromu na n vrcholech je n-1.
  • Strom coby minimální souvislý (pod)graf na daných vrcholech. Les coby graf bez kružnic. Použití stromů v datových strukturách apod.

A pamatujme, pro správné pochopení a zvládnutí grafů je třeba si kreslit a kreslit a kreslit obrázky grafů...

Možné příklady k procvičení základů grafů

  • Zakreslete si "malé" kružnice, cesty, úplné grafy. Pro které parametry m,n je úplný bipartitní graf na m,n vrcholech zároveň cestou nebo kružnicí nebo stromem?
  • Proč má každý jednoduchý graf s více než jedním vrcholem alespoň dva vrcholy stejného stupně?
  • Libovolná ukázka souvislého a nesouvislého grafu obrázkem...
  • Určete stupně vrcholů a nalezněte všechny trojúhelníky v následujících grafech:
               
    Není lepší si některé z těchto grafů nejprve "překreslit" a pak teprve hledat trojúhelníky?
  • Nalezněte všechny podgrafy isomorfní kružnici délky 4 ("čtyřúhelníky") v následujících grafech:
               
  • Nakreslete jednoduchý graf na 5 vrcholech s největším možným počtem hran takový, že neobsahuje trojúhelník.

Možné příklady k procvičení isomorfismu

  • Vyhledejte isomorfní dvojice v následujících čtveřicích grafů daných svými obrázky a zdůvodňujte, proč zbylé dvojice isomorfní nejsou. (Hledejte také "hezčí" obrázky uvedených grafů...)
    •  graf ma hrany {ab,ac,gf,gc,hi,hb,ij,jd,ef,ed,dc,bc}    graf ma hrany {bc,ba,cj,fe,fg,ed,ji,ag,gh,di,dh,ih}   graf ma hrany {hi,hg,ij,cb,cd,ba,jf,gd,de,af,ae,fe}    graf ma hrany {ba,bc,aj,ef,ed,cd,fg,hg,hi,gi,dj,ij}
    • graf ma hrany {ia,ij,cb,cd,ah,bf,de,jg,hg,he,gf,ef}    graf ma hrany {ab,ah,gj,gh,cd,ci,fe,fd,eb,ji,dh,ih}   graf ma hrany {bf,ba,cd,ca,ji,je,hg,hi,gf,de,ia,ea}    graf ma hrany {ab,ah,gi,gh,fe,fj,dc,de,cb,ij,eh,jh}
    • graf ma hrany {gf,gb,gh,fa,fe,ba,bc,he,hc,da,de,dc}    graf ma hrany {dc,de,df,ca,cb,ef,eh,fg,ab,ah,bg,hg}   graf ma hrany {ef,ed,eg,fc,fa,dc,dh,ga,gh,bc,ba,bh}    graf ma hrany {gf,gd,gh,fe,fa,de,dc,ha,hc,be,ba,bc}
  • Rozhodněte, zda existují dva neisomorfní jednoduché grafy na 5 vrcholech se všemi stupni 2. Uvažujte stejnou otázku pro multigrafy na 5 vrcholech a pro jednoduché grafy na 6 vrcholech.
Předchozí
Následující
Operace
Prohlédnout vše