Частини графа

Граф є частиною графа , якщо і , тобто граф містить усі вершини і ребра будь-якої його частини. Частина, що, поряд із деякою підмножиною ребер графа, містить і всі інцидентні їм вершини, називається підграфом. Частина, що поряд із деякою підмножиною ребер графа, містить усі вершини графа ( ), називається суграфом. Розглянуті графи показані на мал. 3.5.

Мал. 3.5. Граф і його частини: а- граф; б- частина графа, в- підграф; г- суграф.

Вихідний граф стосовно його підграфу називають надграфом, а стосовно суграфа - сверхграфом. Сукупність усіх ребер графа, що не належать його підграфу (разом із інцидентними вершинами), утворює доповнення підграфа. Говорять, що підграфи і розділені ребрами, якщо вони не мають спільних ребер і розділені вершинами, якщо в них немає спільних вершин .