без вложений

Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления. Плоское вложение — вложение, при котором любой цикл является границей топологического круга, внутренность которого не зацеплена с графом. Вложимый без зацеплений граф — граф, имеющий незацепленное или плоское вложение. Эти графы образуют трёхмерный аналог планарным графам. В противоположность, существенно зацепленный граф — это граф, не имеющий незацепленного вложения.
Плоские вложения автоматически не имеют зацеплений, но не наоборот. Полный граф




K

6




{\displaystyle K_{6}}
, граф Петерсена и другие пять графов из петерсенова семейства графов не имеют незацепленных вложений. Допускающие незацепленное вложение графы замкнуты по минорам графа и преобразованиям Y-Δ. Эти графы имеют графы петерсенова семейства в качестве запрещённых миноров и включают планарные графы и вершинные графы. Графы могут быть распознаны (а плоское вложение может быть построено) за линейное время.

View More On Wikipedia.org