ЧАСТИНИ ГРАФА

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

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

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

• ⇐ Назад
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 363738
• 39
• 40
• 41
• Далее ⇒