Мы работаем над восстановлением приложения Unionpedia в Google Play Store
ИсходящиеВходящий
🌟Мы упростили наш дизайн для улучшения навигации!
Instagram Facebook X LinkedIn

Вложение графа

Индекс Вложение графа

Вложение графа — изучаемое в рамках топологической теории графов представление графа G на заданной поверхности \Sigma, в котором точки \Sigma ассоциируются с вершинами и простые дуги (гомеоморфные образы) ассоциируются с рёбрами таким образом, что.

Содержание

  1. 24 отношения: NP-полная задача, Кривая моментов, Книжное вложение, Компактное пространство, Планарный граф, Плоскость, Полупространство, Петерсеново семейство графов, Общее положение, Незацепленное вложение графа, Род поверхности, Связное пространство, Топологическая теория графов, Теория графов, Теорема Фари, Циклический порядок, Миллер, Гари, Минор графа, Временная сложность алгоритма, Визуализация графов, Граф (математика), Гомеоморфизм, 1979 год в науке, 1999 год в науке.

  2. Алгоритмы на графах
  3. Топологическая теория графов

NP-полная задача

NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).

Посмотреть Вложение графа и NP-полная задача

Кривая моментов

Кривая моментов — это алгебраическая кривая в d-мерном евклидовом пространстве, заданная множеством точек с декартовыми координатами На евклидовой плоскости кривая моментов — это парабола, а в трёхмерном пространстве —.

Посмотреть Вложение графа и Кривая моментов

Книжное вложение

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

Посмотреть Вложение графа и Книжное вложение

Компактное пространство

Компа́ктное простра́нство — определённый тип топологических пространств, обобщающий свойства ограниченности и замкнутости в евклидовых пространствах на произвольные топологические пространства.

Посмотреть Вложение графа и Компактное пространство

Планарный граф

Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер.

Посмотреть Вложение графа и Планарный граф

Плоскость

Две пересекающиеся плоскости Пло́скость — одно из основных понятий геометрии.

Посмотреть Вложение графа и Плоскость

Полупространство

Красная плоскость определяет синее полупространство Полупростра́нство, ограниченное гиперплоскостью α, — это геометрическая фигура в пространстве, для которой выполняется следующее.

Посмотреть Вложение графа и Полупространство

Петерсеново семейство графов

Петерсеново семейство. ''K''6 вверху рисунка и граф Петерсена внизу. Синие связи показывают Δ-Y или Y-Δ преобразования графов семейства. В теории графов петерсеново семейство графов — это набор из семи неориентированных графов, включающий граф Петерсена и полный граф K6.

Посмотреть Вложение графа и Петерсеново семейство графов

Общее положение

Общее положение — словосочетание, употребляющееся в оборотах типа: «объекты находящиеся в общем положении имеют свойство S», «S есть свойство общего положения», «приведение объекта в общее положение», точный смысл которых зависит от контекста.

Посмотреть Вложение графа и Общее положение

Незацепленное вложение графа

Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления.

Посмотреть Вложение графа и Незацепленное вложение графа

Род поверхности

Поверхность рода 0 Поверхность рода 1 Поверхность рода 2 Поверхность рода 3 Род поверхности — топологическая характеристика замкнутой ориентируемой поверхности \Sigma, такое число g, что данная поверхность гомеоморфна сфере с g ручками.

Посмотреть Вложение графа и Род поверхности

Связное пространство

Множество ''A'' связно, а множество ''B'' несвязно. Связное пространство — непустое топологическое пространство, которое невозможно разбить на два непустых непересекающихся замкнутых подмножества.

Посмотреть Вложение графа и Связное пространство

Топологическая теория графов

Топологическая теория графов — ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства.

Посмотреть Вложение графа и Топологическая теория графов

Теория графов

Граф с шестью вершинами и семью рёбрами Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов.

Посмотреть Вложение графа и Теория графов

Теорема Фари

Теорема Фа́ри — это теорема теории графов, названная в честь венгерского математика.

Посмотреть Вложение графа и Теорема Фари

Циклический порядок

right Циклический порядок — это способ расположения множества объектов на окружности.

Посмотреть Вложение графа и Циклический порядок

Миллер, Гари

Гари Ли Миллер — американский, профессор информатики университета Карнеги — Меллона.

Посмотреть Вложение графа и Миллер, Гари

Минор графа

В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягивания рёбер.

Посмотреть Вложение графа и Минор графа

Временная сложность алгоритма

В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные.

Посмотреть Вложение графа и Временная сложность алгоритма

Визуализация графов

Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа.

Посмотреть Вложение графа и Визуализация графов

Граф (математика)

Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Посмотреть Вложение графа и Граф (математика)

Гомеоморфизм

тор топологически эквивалентны Гомеоморфи́зм (ὅμοιος — похожий, μορφή — форма) — взаимно однозначное и взаимно непрерывное отображение топологических пространств.

Посмотреть Вложение графа и Гомеоморфизм

1979 год в науке

В 1979 году были различные научные и технологические события, некоторые из которых представлены ниже.

Посмотреть Вложение графа и 1979 год в науке

1999 год в науке

В '''1999''' году были различные научные и технологические события, некоторые из которых представлены ниже.

Посмотреть Вложение графа и 1999 год в науке

См. также

Алгоритмы на графах

Топологическая теория графов