Это список важных терминов вместе с определениями, которые часто используются в теории графов. В следующей терминологии G обозначает простой граф, а u,v — вершины.
Точка сочленения: также известная как точка отсечения, вершина, удаление которой увеличивает количество компонентов в графе.
Biclique: полный двудольный граф.
Двудольный граф. Граф, множество вершин которого V можно разделить на два подмножества V1 и V2 так, что каждое ребро графа G соединяет V1 с V2.
Бридж: ультрасовременный.
Хорда: ребро, соединяющее две непоследовательные вершины пути или цикла.
Хроматическое число: минимальное количество цветов в правильной раскраске графа.
Окружность: длина самого длинного цикла.
Цикл: замкнутый след означает, что начальная и конечная вершины будут одинаковыми.
Закрытый обход: обход, последняя вершина которого совпадает с первой.
Полный граф: простой граф (обозначается Kn), в котором любые две вершины являются смежными.
Компонент: максимальный связный подграф, в котором все узлы доступны из любого другого. Максимальный означает, что это самый большой возможный подграф: нигде в графе нельзя было найти другой узел, который можно было бы добавить в подграф, и все узлы в подграфе по-прежнему были бы связаны.
Для ориентированных графов существуют сильные компоненты и слабые компоненты. Сильная компонента — это максимальный подграф, в котором существует путь из каждой точки в любую другую точку, следующий по всем ребрам. Слабая компонента — это максимальный подграф, который был бы связным, если бы мы не учитывали направление ребер.
Ребро: ребро, удаление которого увеличивает количество компонентов.
Клика: Клика графа — это полный максимальный подграф. Это подграф, который является полным, то есть каждая пара вершин является смежной, и максимальное означает, что добавление еще одной вершины к этому подграфу не позволит ему оставаться полным.
Цикл: замкнутый путь, закрытый означает, что начальная и конечная вершины одинаковы для этого пути.
Диаметр: максимальный эксцентриситет графа, т. е. максимальное расстояние d(u,v) по всем парам вершин u,v
Орграф: граф, в котором каждое ребро направлено. Также известен как ориентированный граф.
Эксцентриситет: эксцентриситет e(v) точки v в связном графе G равен максимальному расстоянию (u,v) для всех u в Г.
Сжатие ребра: сжатие ребра — это операция, которая удаляет ребро из графа, одновременно объединяя две вершины, которые оно ранее соединяло.
Покрытие ребер: набор ребер, покрывающий все вершины графа.
Эйлерова цепь: замкнутый путь, содержащий каждое ребро графа.
Гамильтонов цикл: цикл, содержащий каждую вершину графа ровно один раз.
Обхват: длина кратчайшего цикла, содержащегося в графике. Для ациклических графов обхват не определен.
Мощность графа: k-я степень неориентированного графа G — это другой граф, который имеет тот же набор вершин, но в котором две вершины являются смежными, когда их расстояния в G не превосходят k. Степени графа отличаются от произведения графа на самого себя.
Независимый набор. Это набор вершин графа, из которых никакие две не являются смежными. Максимальный независимый набор — это либо независимый набор, такой что добавление любой другой вершины к набору приводит к тому, что набор будет содержать ребро, либо набор всех вершин пустого графа. Максимальное независимое множество — это независимое множество максимально возможного размера для данного графа G. Этот размер называется числом независимости графа G.
Теорема Куратовского: граф планарный тогда и только тогда, когда он не имеет подразделения K5 или K3,3
Соответствие: набор ребер, не имеющих общих конечных вершин.
Минор: неориентированный граф H называется минором графа G, если H может быть образован из G путем удаления ребер и вершин и стягивания ребер.
Нечетный цикл: цикл с нечетным числом ребер.
Нечетная вершина: вершина нечетной степени.
Ориентация: ориентация неориентированного графа — это присвоение направления каждому ребру, превращающее исходный граф в ориентированный граф.
Путь: обход, в котором все вершины различны.
Планарный граф: граф, который можно нарисовать на плоскости таким образом, что его ребра пересекаются только в своих конечных точках.
Радиус: минимальный эксцентриситет вершин.
Число Рамси: минимальное количество вершин, скажем, v, такое, что все неориентированные простые графы порядка (число вершин) v содержат клику порядка m или независимое множество порядка n. Обозначается как R(m,n). Также теорема Рамсея утверждает, что такое число существует для всех m и n.
Регулярный граф: граф, все вершины которого имеют одинаковую степень.
Сильно связанный: орграф, в котором каждая вершина достижима из всех остальных вершин.
Подграф: граф, все вершины и ребра которого принадлежат данному графу.
Турнир: ориентация полного графа.
Тропа: прогулка, в которой ни один край не появляется более одного раза.
Дерево: связный граф без циклов.
Вершинное покрытие: набор вершин, в котором каждое ребро графа инцидентно хотя бы одной вершине набора.
Обход: чередующийся список вершин и ребер в графе, где каждая вершина принадлежит ребру до и после нее.
По любым вопросам, пожалуйста, оставьте комментарий.