Definice: Prostý graf je takový orientovaný nebo neorientovaný graf, v němž je násobnost každé hrany nejvýše rovna jedné. (Hrany a nazveme násobné, jestliže ).

Příklad grafu, který obsahuje násobné hrany (vlevo) a příklad prostého grafu (vpravo):

Definice: Jednoduchý graf je takový orientovaný nebo neorientovaný graf, který neobsahuje smyčky.

Obrázek vlevo znázorňuje graf, který není jednoduchý, neboť obsahuje smyčky u vrcholů a a b. Graf vpravo již jednoduchý je:

Definice: Úplný graf je takový orientovaný nebo neorientovaný graf, ve kterém mezi každými dvěma uzly existuje právě jedna hrana.

Příklady úplných grafů na 1 až 4 vrcholech:

Definice: Neorientovaný graf je takový graf, ve kterém platí, že ke každé hraně pro níž platí existuje hrana taková, že V opačném případě se jedná o orientovaný graf.

Orientovaný graf můžeme znázornit obrázkem, kde vrcholy znázorníme jako kolečka a hrany jako šipky vedoucí mezi těmito kolečky. Příklad takového grafu je na následujícím obrázku, kde je znázorněn graf kde a

Neorientovaný graf se znázorňuje podobně jako orientovaný, na konci čar, které představují hrany však nekreslíme šipky. Příklad neorientovaného grafu je uveden na následujícím obrázku. Jedná se o graf kde a

Poznámka: U orientovaného grafu říkáme, že hrana vychází z vrcholu a vstupuje do vrcholu U neorientovaného grafu říkáme, že hrana je incidentní s vrcholy a

Definice: Stupeň vrcholu v neorientovaném grafu je počet hran, které jsou s tímto vrcholem incidentní. V orientovaném grafu je vstupní stupeň vrcholu počet hran, které do daného vrcholu vstupují, výstupní stupeň vrcholu počet hran, které z daného vrcholy vystupují a stupeň vrcholu je součet jeho vstupního a výstupního stupně.

Definice: Graf, kde jsou hrany, respektive vrcholy, zobrazeny do nějaké předem dané množiny, ze které se vybírá ohodnocení, se nazývá hranově ohodnocený graf (resp. vrcholově ohodnocený graf). Příslušné zobrazení se nazývá ohodnocení.

Definice: Graf je podgrafem grafu jestliže a Pro danou množinu je podgraf grafu indukovaný množinou vrcholů deﬁnován jako graf kde

Definice: Sled délky k v grafu

z vrcholu do vrcholu je konečná posloupnost kde ve které se vždy střídají vrcholy a hrany a pro každé platí, že hrana spojuje vrchol s vrcholem

Definice: Tah v grafuje sled, v němž se neopakují hrany.

Definice: Cesta v grafu je sled, v němž se neopakují vrcholy.

Definice: Cyklus je tah kde a všechny vrcholy kromě a jsou navzájem různé.

Definice: V případě neorientovaného grafu se cyklu též říká kružnice.

Definice: Vrchol je dostupný z vrcholu jestliže existuje sled kde a

Definice: Graf se nazývá souvislým, jestliže pro každé dva vrcholy a existuje v grafu cesta začínající ve vrcholu a končící ve vrcholu

Definice: Graf bez kružnic se nazývá les.

Definice: Souvislý les se pak nazývá strom.

Strom je tedy minimální souvislý graf bez kružnic. Odebráním libovolné hrany se stane nesouvislým a přidáním libovolné hrany vznikne kružnice. Níže je příklad stromu:

Definice: Binární strom je strom, který má pro každý uzel nejvýše dva následníky.

Definice: Kořenový strom je orientovaný graf, ve kterém je vyznačen jeden vrchol nazvaný kořen.

Do kořene nevede žádná (orientovaná) hrana, má tedy vstupní stupeň 0, do každého dalšího vrcholu vede právě jedna hrana (má tedy vstupní stupeň 1) a všechny vrcholy jsou z kořene orientovaně dostupné. V kořenových stromech se užívá pro vrcholy přirozeným způsobem definovaných pojmů otec nebo rodič, synnebo dítě, předek, potomek. List v kořenovém stromu je vrchol výstupního stupně 0, který tedy již nemá žádné syny. Kořenový strom se dá kreslit velmi názorně.

vytvořil Institut biostatistiky a analýz Lékařské fakulty Masarykovy univerzity