Незачеплене вкладення графа
вкладення неорієнтованого графа в евклідів простір, за якого жодні два цикли графа не мають ненульового коефіцієнта зачеплення / З Вікіпедії, безкоштовно encyclopedia
Незачеплене вкладення графа — вкладення неорієнтованого графа в евклідів простір, за якого жодні два цикли графа не мають ненульового коефіцієнта зачеплення. Плоске вкладення — вкладення, в якому будь-який цикл є межею топологічного круга, внутрішність якого не зачеплена з графом. Граф, що вкладається без зачеплень, — граф, що має незачеплене або плоске вкладення. Ці графи утворюють тривимірний аналог планарних графів[1]. Напроти, суттєво зачеплений граф — це граф, який не має незачепленого вкладення.
Плоскі вкладення автоматично не мають зачеплень, але не навпаки[2]. Повний граф , граф Петерсена та інші п'ять графів із петерсенового сімейства графів не мають незачеплених вкладень[1]. Графи, що допускають незачеплене вкладення, замкнені за мінорами графа[3] і перетвореннями Y-Δ[2]. Вони мають графи петерсенового сімейства забороненими мінорами [4] і включають планарні графи та вершинні графи[2]. Графи можна розпізнати (а плоске вкладення — побудувати) за лінійний час [5].