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

Алмаз (теория графов)

Индекс Алмаз (теория графов)

Алмаз — это планарный неориентированный граф с 4 вершинами и 5 рёбрами.

Содержание

  1. 20 отношения: Кактус (теория графов), Компонента связности графа, Планарный граф, Порождённый подграф, Обхват (теория графов), Окрестность (теория графов), Рёберно k-связный граф, Расстояние (теория графов), Теорема Робертсона — Сеймура, Характеристический многочлен матрицы, Характеризация запрещёнными графами, Циклическая группа, Четверная группа Клейна, Минор графа, Бабочка (теория графов), Вершинно k-связный граф, Граф без треугольников, Граф единичных расстояний, Грациозная разметка, Гамильтонов граф.

  2. Графы, имеющие собственные названия

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

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

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

Компонента связности графа

Несвязный граф с тремя компонентами связности Компонента связности графа G (или просто компонента графа G) — максимальный (по включению) связный подграф графа G.

Посмотреть Алмаз (теория графов) и Компонента связности графа

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

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

Посмотреть Алмаз (теория графов) и Планарный граф

Порождённый подграф

Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.

Посмотреть Алмаз (теория графов) и Порождённый подграф

Обхват (теория графов)

Обхват в теории графов — длина наименьшего цикла, содержащегося в данном графе.

Посмотреть Алмаз (теория графов) и Обхват (теория графов)

Окрестность (теория графов)

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

Посмотреть Алмаз (теория графов) и Окрестность (теория графов)

Рёберно k-связный граф

Рёберно k-связный граф — граф, который остаётся связным после удаления не более чем k-1 рёбер.

Посмотреть Алмаз (теория графов) и Рёберно k-связный граф

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

В теории графов расстоянием между двумя вершинами графа называется число рёбер в кратчайшем пути (также называемым геодезической графа).

Посмотреть Алмаз (теория графов) и Расстояние (теория графов)

Теорема Робертсона — Сеймура

Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа) утверждает, что неориентированные графы, частично упорядоченные отношением минорности, образуют множество.

Посмотреть Алмаз (теория графов) и Теорема Робертсона — Сеймура

Характеристический многочлен матрицы

Характеристический многочлен матрицы — многочлен, определяющий её собственные значения.

Посмотреть Алмаз (теория графов) и Характеристический многочлен матрицы

Характеризация запрещёнными графами

Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.

Посмотреть Алмаз (теория графов) и Характеризация запрещёнными графами

Циклическая группа

Циклическая группа — группа (G, \cdot), которая может быть порождена одним элементом, то есть все её элементы являются степенями (или, если использовать аддитивную терминологию, представимы в виде, где  — целое число).

Посмотреть Алмаз (теория графов) и Циклическая группа

Четверная группа Клейна

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

Посмотреть Алмаз (теория графов) и Четверная группа Клейна

Минор графа

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

Посмотреть Алмаз (теория графов) и Минор графа

Бабочка (теория графов)

В теории графов граф «бабочка» (а также «галстук-бабочка» или «песочные часы») — это планарный неориентированный граф с 5 вершинами и 6 рёбрами.

Посмотреть Алмаз (теория графов) и Бабочка (теория графов)

Вершинно k-связный граф

В теории графов говорят, что граф G k-вершинно-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.

Посмотреть Алмаз (теория графов) и Вершинно k-связный граф

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

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

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

Граф единичных расстояний

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

Посмотреть Алмаз (теория графов) и Граф единичных расстояний

Грациозная разметка

Вершинная разметка показана чёрным цветом, рёберная — красным Грациозная разметка в теории графов — такая вершинная разметка графа с m рёбрами некоторым подмножеством целых чисел между 0 и m включительно, что разные вершины помечены разными числами, и такая, что, если каждое рёбро пометить абсолютной разностью величин вершин, которое оно соединяет, то все полученные разности будут различнымиVirginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001.

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

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

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

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

См. также

Графы, имеющие собственные названия