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

Гусеница (теория графов)

Индекс Гусеница (теория графов)

Гусеница Гусеница или гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии 1 от центрального пути.

Содержание

  1. 22 отношения: NP-полная задача, Клика (теория графов), Путь (теория графов), Путевая ширина, Параллельно-последовательный граф, Полициклические ароматические углеводороды, Перечисление графов, Аппроксимационный алгоритм, Рёберный граф, Равенство классов P и NP, Углеводороды, Харари, Фрэнк, Интервальный граф, Визуализация графов, Внешнепланарный граф, Вершинный сепаратор (теория графов), Граф Халина, Граф без треугольников, Граф-звезда, Гамильтонов граф, Древесная ширина (теория графов), Дерево (теория графов).

  2. Деревья (графы)
  3. Математическая химия

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

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

Посмотреть Гусеница (теория графов) и NP-полная задача

Клика (теория графов)

Граф с 23 кликами, содержащими 1 вершину (вершины графа), 42 кликами, состоящими из 2 вершин (рёбра графа), 19 кликами, состоящими из 3 вершин (закрашенные треугольники) и двумя кликами, состоящими из 4 вершин (тёмно-синие области).Шесть рёбер не входят ни в один треугольник и 11 светло-голубых треугольников образуют максимальные клики.Две тёмно-синие 4-клики являются как наибольшими, так и максимальными, и кликовое число графа равно 4.

Посмотреть Гусеница (теория графов) и Клика (теория графов)

Путь (теория графов)

Граф-путь с 6 вершинами Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Посмотреть Гусеница (теория графов) и Путь (теория графов)

Путевая ширина

В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.

Посмотреть Гусеница (теория графов) и Путевая ширина

Параллельно-последовательный граф

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

Посмотреть Гусеница (теория графов) и Параллельно-последовательный граф

Полициклические ароматические углеводороды

Полиароматические углеводороды (ПАУ) — органические соединения, для которых характерно наличие в химической структуре двух и более конденсированных бензольных колец.

Посмотреть Гусеница (теория графов) и Полициклические ароматические углеводороды

Перечисление графов

Полный список всех деревьев с 2,3 и 4 помеченными вершинами: 2^2-2.

Посмотреть Гусеница (теория графов) и Перечисление графов

Аппроксимационный алгоритм

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

Посмотреть Гусеница (теория графов) и Аппроксимационный алгоритм

Рёберный граф

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G. Понятие рёберного графа для данного графа настолько естественно, что независимо было введено многими авторами.

Посмотреть Гусеница (теория графов) и Рёберный граф

Равенство классов P и NP

Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.

Посмотреть Гусеница (теория графов) и Равенство классов P и NP

Углеводороды

Углеводоро́ды — органические соединения, состоящие из атомов углерода и водорода.

Посмотреть Гусеница (теория графов) и Углеводороды

Харари, Фрэнк

Фрэнк Харари и Клаус Вагнер, 1972 Фрэнк Харари (Frank Harary; 11 марта 1921, Нью-Йорк — 4 января 2005, Лас-Крусес) — американский математик, специализировавшийся в теории графов.

Посмотреть Гусеница (теория графов) и Харари, Фрэнк

Интервальный граф

Семь интервалов на прямой и соответствующий интервальный граф с семью вершинами. Интервальный граф — граф пересечений мультимножества интервалов на прямой.

Посмотреть Гусеница (теория графов) и Интервальный граф

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

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

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

Внешнепланарный граф

Максимальный внешнепланарный граф и его 3-раскраска. Полный граф K4 является наименьшим планарным графом, не являющимся внешнепланарным. В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.

Посмотреть Гусеница (теория графов) и Внешнепланарный граф

Вершинный сепаратор (теория графов)

В теории графов подмножество вершин S \subset V называется вершинным сепаратором для несмежных вершин a и b, если удаление S из графа разделяет a и b в две компоненты связности.

Посмотреть Гусеница (теория графов) и Вершинный сепаратор (теория графов)

Граф Халина

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

Посмотреть Гусеница (теория графов) и Граф Халина

Граф без треугольников

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

Посмотреть Гусеница (теория графов) и Граф без треугольников

Граф-звезда

Граф-звезда ''S7'' В теории графов граф-звезда Sk — это полный двудольный граф K1,k.

Посмотреть Гусеница (теория графов) и Граф-звезда

Гамильтонов граф

Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа. Гамильто́нов граф — математический объект теории графов.

Посмотреть Гусеница (теория графов) и Гамильтонов граф

Древесная ширина (теория графов)

В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом.

Посмотреть Гусеница (теория графов) и Древесная ширина (теория графов)

Дерево (теория графов)

Дерево — это связный ациклический граф.

Посмотреть Гусеница (теория графов) и Дерево (теория графов)

См. также

Деревья (графы)

Математическая химия