Содержание
6 отношения: Путевая ширина, Топологическая теория графов, Теорема Робертсона — Сеймура, Теорема Вагнера, Минор графа, Верхушечный граф.
Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.
Посмотреть Структурная теорема графов и Путевая ширина
Топологическая теория графов
Топологическая теория графов — ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства.
Посмотреть Структурная теорема графов и Топологическая теория графов
Теорема Робертсона — Сеймура
Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа) утверждает, что неориентированные графы, частично упорядоченные отношением минорности, образуют множество.
Посмотреть Структурная теорема графов и Теорема Робертсона — Сеймура
Теорема Вагнера
графа Петерсена (маленькие цветные кружочки и чёрные рёбра). Миноры можно сформировать путём удаления красной вершины и стягивания рёбер в жёлтые круги Кликовая сумма двух планарных графов и графа Вагнера, образующая граф без ''K''5 В теории графов теорема Вагнера — это математическая характеризация запрещёнными графами планарных графов, названная в честь.
Посмотреть Структурная теорема графов и Теорема Вагнера
Минор графа
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягивания рёбер.
Посмотреть Структурная теорема графов и Минор графа
Верхушечный граф
планарным. В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины.