Графичен хомеоморфизъм
Две графи G и G ′хомеоморфни, ако има изоморфизъм на някоиподразделениена графа G и някоиподразделениена графа G ′ [1] . Ако ръбовете на графа се разбират като сегменти, свързващи върхове (както обикновено се рисува на илюстрациите), тогава две графи са хомеоморфни в контекста на теорията на графите, когато са хомеоморфни в топологичен смисъл.
Съдържание
Като цяло,подразделениена графикаG(понякога терминътразширение[2] илиподразделение) е графика, получена чрез разделяне на ребра вG. Разделяне на някакво реброeс крайни върхове u,v> дава график, съдържащ нов връхwи две ребра u,w> и w,v> вместо крайe[1] .
Например ръбeс краища u,v>:
може да се раздели на два ръба,e1 иe2:
Обратната операция,елиминиращавръхwс инцидентни му ребра (e1,e2), заменя двата ребра, съседни на връхw(e1,e2) с ново ребро, свързващо крайните точки на двойката. Трябва да се подчертае, че тази операция е приложима само за върхове, които са инцидентни с точно две ребра.
има връх (с имеw), който може да бъде изключен, което води до:
Определянето дали графHе хомеоморфен на подграфGе NP-пълен проблем [3] .
барицентрични подразделения
Барицентричното подразделение разделя всеки ръб на графиката. Това е специален вид подразделение, което винаги дава двустранна графика. Тази процедура може да се повтори, така чеnтото барицентрично подразделение да бъде барицентричното подразделение наn-1подразделение. Второто такова разделение винаги е проста графика.
Ясно е, че разделениетографиката е планарна. Теоремата на Понтрягин-Куратовски гласи това
краен граф е планарен тогава и само ако не съдържа подграфхомеоморфенK5 (пълен граф с пет върха), илиK3,3 (пълен двустранен граф с шест върха, три от които са свързани с всеки от останалите три).
В следващия пример графите G и H са хомеоморфни.
Ако графиката G' е създадена чрез подразделяне на външните ръбове на графиката G, а графиката H' е създадена чрез подразделяне на вътрешните ръбове на графиката H, тогава G' и H' имат подобни графични представяния:
По този начин има изоморфизъм между графите G' и H', което означава, че G и H са хомеоморфни.