Это список важных терминов вместе с определениями, которые часто используются в теории графов. В следующей терминологии 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.

Регулярный граф: граф, все вершины которого имеют одинаковую степень.

Сильно связанный: орграф, в котором каждая вершина достижима из всех остальных вершин.

Подграф: граф, все вершины и ребра которого принадлежат данному графу.

Турнир: ориентация полного графа.

Тропа: прогулка, в которой ни один край не появляется более одного раза.

Дерево: связный граф без циклов.

Вершинное покрытие: набор вершин, в котором каждое ребро графа инцидентно хотя бы одной вершине набора.

Обход: чередующийся список вершин и ребер в графе, где каждая вершина принадлежит ребру до и после нее.

По любым вопросам, пожалуйста, оставьте комментарий.