Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
В теории графов два типа объектов обычно называются циклами.
Точкой сочленения в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «шарнир».
Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
В теории графов говорят, что нетривиальный граф G вершинно k-связен, если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.
Вершинa графа — фундаментальное понятие теории графов. Неориентированный граф состоит из множества вершин и множества рёбер, в то время как ориентированный граф состоит из множества вершин и множества дуг. На рисунках, представляющих граф, вершина обычно обозначается кружком с меткой, ребро — линией, дуга — стрелкой, соединяющей вершины.
Блоковый граф — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.
В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями.
Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа. Панциклические графы являются обобщением гамильтоновых графов, графов, которые имеют циклы максимальной возможной длины.
В теории графов псевдолес — это неориентированный граф, в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Ребро в геометрии — отрезок, соединяющий две вершины многоугольника или многогранника. В многоугольниках ребро является отрезком, лежащим на границе и чаще называется стороной многоугольника. В трёхмерных многогранниках и в многогранниках большей размерности ребро — это отрезок, общий для двух граней. Отрезок, соединяющий две вершины и проходящий через внутренние или внешние точки, ребром не является и называется диагональю.
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и отражает другие меры разреженности, такие как древесность графа.
Ранг неориентированного графа имеет два не связанных друг с другом определения. Пусть n равно числу вершин графа.
- В терминах теории матриц ранг r неориентированного графа определяется как ранг его матрицы смежности.
- Аналогично, дефект графа определяется как дефект ядра его матрицы смежности, что равно n − r.
- В терминах теории матроидов графов ранг неориентированного графа определяется как число n − c, где c — число связных компонент графа. Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, ассоциированной с графом.
- Аналогично, дефект графа — это дефект ядра ориентированной матрицы инцидентности, который задаётся формулой m − n + c, где n и c определены выше, а m — число рёбер графа. Дефект равен первому числу Бетти графа. Сумма ранга и дефекта даёт число рёбер.
Биполярная ориентация или st-ориентация неориентированного графа — это назначение ориентации каждому ребру (ориентации), что превращает граф в направленный ациклический граф с единственным источником s и единственном стоком t, а st-нумерация графа — это топологическая сортировка полученного ориентированного ациклического графа.
Периферийный цикл в неориентированном графе — цикл, который, неформально говоря, не отделяет любую часть графа от любой другой. Периферийные циклы, первым изучал Татт, Уильям Томас. Они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.
![[1]](http://mathworld.wolfram.com/images/eps-gif/BiconnectedGraphs_1000.gif){kind=link}