В теории графов, два графов и являются гомеоморфно, если существует изоморфизм графов из некоторого разбиения по некоторому подразделению из. Если ребра графа представить себе как линии, проведенные от одной вершины к другой (как они обычно изображаются на иллюстрациях), то два графа гомеоморфны друг другу в теоретико-графовом смысле именно в том случае, если они гомеоморфны в смысле этот термин используется в топологии.
В общем случае, подразделение графа G (иногда известный как расширение) представляет собой график, полученный от деления ребер в G. Подразделение некоторого ребра e с концами { u, v } дает граф, содержащий одну новую вершину w и набор ребер, заменяющий e двумя новыми ребрами, { u, w } и { w, v }.
Например, ребро e с концами { u, v }:
можно разделить на два ребра, e 1 и e 2, соединяющихся с новой вершиной w:
Обратная операция, сглаживание или сглаживание вершины w относительно пары ребер ( e 1, e 2), инцидентных на w, удаляет оба ребра, содержащие w, и заменяет ( e 1, e 2) новым ребром, соединяющим другие конечные точки пары. Здесь подчеркивается, что только вершины степени два (т. Е. 2-валентные) могут быть сглажены.
Например, простой связный граф с двумя ребрами, e 1 { u, w } и e 2 { w, v }:
имеет вершину (а именно w), которую можно сгладить, в результате чего:
Определение, является ли для графов G и H, H гомеоморфно подграфа G, является NP-полной задачей.
Барицентрическое подразделение подразделяет каждое ребро графа. Это особое подразделение, так как оно всегда приводит к двудольному графу. Эту процедуру можно повторить, так что n- е барицентрическое подразделение является барицентрическим подразделением n -1- го барицентрического подразделения графа. Второе такое подразделение всегда представляет собой простой граф.
Очевидно, что разбиение графа сохраняет планарность. Теорема Куратовского утверждает, что
Фактически, граф, гомеоморфный K 5 или K 3,3, называется подграфом Куратовского.
Обобщение, следующее из теоремы Робертсона – Сеймура, утверждает, что для каждого целого числа g существует конечное множество препятствий для графов, такое что граф H вложим на поверхность рода g тогда и только тогда, когда H не содержит гомеоморфной копии любого из. Например, состоит из подграфов Куратовского.
В следующем примере граф G и граф H гомеоморфны.
График G График HЕсли G ' - это граф, созданный путем подразделения внешних ребер G, а H' - это граф, созданный путем подразделения внутреннего ребра H, тогда G ' и H' имеют аналогичный рисунок графа:
График G ', H'Следовательно, существует изоморфизм между G ' и H', что означает, что G и H гомеоморфны.
возникает потому, что имя и являются гомеоморфны как графы тогда и только тогда, когда они гомеоморфны как топологические пространства
Определение 20. Если некоторые новые вершины степени 2 добавляются некоторые из ребер графа G, полученный граф Н называется расширением из G.