Podgraf
Termín podgraf se v teorii grafů používá jako jistá obdoba pojmu podmnožina.
Graf H je podgraf grafu G, jestliže
a 
Jinými slovy, podgraf vznikne vymazáním některých vrcholů původního grafu, všech hran do těchto vrcholů zasahujících a případně některých dalších hran.
Obsah |
Indukovaný podgraf [editovat]
Graf H je indukovaný podgraf (též plný podgraf) grafu G, jestliže
a 
Indukovaný podgraf vznikne vymazáním některých vrcholů a pouze těch hran, které do vymazaných vrcholů zasahují.
Faktor [editovat]
Podgraf H je faktor grafu G, jestliže množina vrcholů grafu H je totožná s množinou vrcholů grafu G, V(H) = V(G).
Kostra [editovat]
Kostra grafu G je takový jeho faktor, který neobsahuje kružnice. Ovšem musí být zachovány existence cest v grafu. Tzn. musí být zachován počet komponent grafu (počet souvislých částí grafu).
Klika [editovat]
Klikou grafu nazýváme takový podgraf, který je úplný. Nalezení kliky dané velikosti je známým NP-úplným problémem.