Встраивание графа

• Определение и свойства вложения графа

  • Вложение графа G на поверхности Σ — это представление графа, в котором вершины и ребра связаны с точками и дугами поверхности. 
  • Вложение должно удовлетворять условиям непересечения ребер и отсутствия точек, связанных с другими вершинами. 
  • Вложение графа в трехмерное евклидово пространство R3 возможно для любого конечного графа. 

• Род графа и его классификация

  • Род графа — это минимальное целое число n, такое что граф может быть встроен в поверхность рода n. 
  • Плоский граф имеет род 0, а граф, который может быть встроен в тор, называется тороидальным. 
  • Эйлеров род графа — это минимальное целое число n, такое что граф может быть встроен в ориентируемую или неориентируемую поверхность рода n/2. 
  • Ориентируемо простой граф — это граф с эйлеровым родом меньше неориентируемого рода. 
  • Максимальный род графа — это максимальное целое число n, такое что граф может быть вложен в поверхность рода n. 

• Комбинаторное вложение и его эквивалентности

  • Комбинаторное вложение — это вложение с фиксированной системой вращения ребер. 
  • Эквивалентные вложения имеют одинаковую систему вращения ребер. 
  • Существуют другие эквивалентные представления для комбинаторных вложений, включая ленточный граф и карту с кодировкой графа. 

• Вычислительная сложность и примеры

  • Задача определения рода графа является NP-полной. 
  • Существуют алгоритмы для проверки возможности вложения графа в поверхность заданного рода и для нахождения такого вложения. 
  • Примеры вложений включают книжное вложение графа и бессвязное вложение. 

• Встраивание графов в многомерные пространства

  • Любой конечный граф может быть вложен в трехмерное пространство. 
  • Существуют различные способы вложенности графа в трехмерное пространство, включая книжное вложение и бессвязное вложение.