Понятия орграфа, неорграфа, связности графа, дерева
Ориентированный граф (орграф) – граф, рёбрам которого присвоено направление
Неориентированный граф (неорграф) – граф, у которого все рёбра неориентированны, т.е. им не присвоено направление
Связный граф – граф, у которого для любой пары различных вершин существует цепь, соединяющая эти вершины
Дерево – связный ациклический граф
Связность – наличие путей между любой парой вершин
Ацикличность – отсутствие циклов и наличие только одного пути между вершинами
Планарность графа
Планарный граф – граф, который может быть изображён на плоскости без пересечения рёбер
Матрица смежности. Матрица инциденций
Матрица смежности – один из способов представления графа в виде матрицы
Матрица смежности графа G с конечным числом вершин n – это квадратная матрица A в размера n, в которой значение элемента 
в этом случае равно удвоенному числу петель вокруг i-й вершины
Матрица инциденций – одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (рёбрами или вершинами). Столбцы соответствуют рёбрам, строки – вершинам. 1 – связь между вершиной и ребром
Матрица основных циклов, основных разрезов, их свойства
Матрица основных циклов графа G – матрица, состоящая из v строк и m столбцов, в которой 
равно 1, если ребро 
принадлежит циклу 
, и равно 0 в противном случае.
Эйлеров и Гамильтонов граф
Эйлеров граф – граф, содержащий эйлеров цикл
|
|
|
Эйлеров цикл – эйлеров путь, являющийся циклом.
Эйлеров путь – путь, проходящий по всем рёбрам графа по одному разу
Условия существования эйлерова графа:
Эйлеров цикл существует тогда и только тогда, когда граф связный или будет являться связным, если удалить из него все изолированные вершины, и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени.
Гамильтонов граф – граф, который содержит гамильтонов цикл
Гамильтонов цикл – цикл, который проходит через каждую вершину ровно 1 раз
Гамильтонов путь – путь, проходящий через каждую вершину графа ровно 1 раз
Раскраска графа
Раскраска графа – частный случай разметки графа
Раскраска вершин – такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета
Раскраска рёбер - такой способ окраски рёбер графа, при котором любым двум смежным рёбрам соответствуют разные цвета
Раскраска областей планарного графа – назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет
|
|
|
Дата добавления: 2018-09-20; просмотров: 183; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!