Содержание
21 отношения: Клика (теория графов), Кликовая ширина, Путевая ширина, Операции над графами, Рёберный граф гиперграфа, Рёберная раскраска, Раскраска графов, Сильно регулярный граф, Совершенный граф, Тотальная раскраска, Топологическая теория графов, Теорема Кёнига (комбинаторика), Характеризация запрещёнными графами, Изоморфизм графов, Блоковый граф, Гусеница (теория графов), Граф Петерсена, Граф без клешней, Граф пересечений, Гамильтоново дополнение, Доминирующее множество рёбер.
Клика (теория графов)
Граф с 23 кликами, содержащими 1 вершину (вершины графа), 42 кликами, состоящими из 2 вершин (рёбра графа), 19 кликами, состоящими из 3 вершин (закрашенные треугольники) и двумя кликами, состоящими из 4 вершин (тёмно-синие области).Шесть рёбер не входят ни в один треугольник и 11 светло-голубых треугольников образуют максимальные клики.Две тёмно-синие 4-клики являются как наибольшими, так и максимальными, и кликовое число графа равно 4.
Посмотреть Рёберный граф и Клика (теория графов)
Кликовая ширина
дистанционно-наследуемуего графа кликовой ширины 3 путём несвязного объединения, переименования вершин и объединения меток. Метки вершин показаны цветом. В теории графов кликовая ширина графа G — это параметр, который описывает структурную сложность графа.
Посмотреть Рёберный граф и Кликовая ширина
Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.
Посмотреть Рёберный граф и Путевая ширина
Операции над графами
Операции над графами образуют новые графы из старых.
Посмотреть Рёберный граф и Операции над графами
Рёберный граф гиперграфа
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение.
Посмотреть Рёберный граф и Рёберный граф гиперграфа
Рёберная раскраска
графа Дезарга. Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет.
Посмотреть Рёберный граф и Рёберная раскраска
Раскраска графов
Корректная раскраска вершин графа наименьшим набором цветов — тремя. В теории графов раскраска графов является частным случаем.
Посмотреть Рёберный граф и Раскраска графов
Сильно регулярный граф
Граф Пэли 13-го порядка, сильно регулярный граф с параметрами srg(13,6,2,3). В теории графов сильно регулярным графом называется граф, обладающий следующими свойствами: Пусть G.
Посмотреть Рёберный граф и Сильно регулярный граф
Совершенный граф
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа.
Посмотреть Рёберный граф и Совершенный граф
Тотальная раскраска
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа.
Посмотреть Рёберный граф и Тотальная раскраска
Топологическая теория графов
Топологическая теория графов — ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства.
Посмотреть Рёберный граф и Топологическая теория графов
Теорема Кёнига (комбинаторика)
Пример двудольного графа с наибольшим паросочетанием (выделено голубым) и наименьшим вершинным покрытием (выделено красным), оба имеют размер шесть. В теории графов теорема Кёнига, доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах.
Посмотреть Рёберный граф и Теорема Кёнига (комбинаторика)
Характеризация запрещёнными графами
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.
Посмотреть Рёберный граф и Характеризация запрещёнными графами
Изоморфизм графов
В теории графов изоморфизмом графов G.
Посмотреть Рёберный граф и Изоморфизм графов
Блоковый граф
Блоковый граф Блоковый граф (кликовое дерево) — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.
Посмотреть Рёберный граф и Блоковый граф
Гусеница (теория графов)
Гусеница Гусеница или гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии 1 от центрального пути.
Посмотреть Рёберный граф и Гусеница (теория графов)
Граф Петерсена
Граф Петерсена — это неориентированный граф с 10 вершинами и 15 рёбрами.
Посмотреть Рёберный граф и Граф Петерсена
Граф без клешней
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
Посмотреть Рёберный граф и Граф без клешней
Граф пересечений
right В теории графов графом пересечений называется граф, схему пересечений семейства множеств.
Посмотреть Рёберный граф и Граф пересечений
Гамильтоново дополнение
Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым.
Посмотреть Рёберный граф и Гамильтоново дополнение
Доминирующее множество рёбер
Примеры доминирующих множеств рёбер. В теории графов доминирующее множество рёбер (или рёберное доминирующее множество) графа G.
Посмотреть Рёберный граф и Доминирующее множество рёбер