1. Определение. Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
2. Виды графов
2.1. Ориентированные- такой граф, в котором можно двигаться от вершины к вершине только в одном направлении.
2.2. Неориентированные- граф, в котором можно двигаться в обе стороны.
2.3. Смешанный граф-в котором присутствуют как ориентированные ребра, так и неориентированные.
2.4. Взвешенный-граф, в котором каждому ребру в соответствие поставлено некоторое числовое значение – вес.
2.5. Невзвешенный-никакого числового значения рёбрам не поставлено.
2.6. Петля- это ребро, которое начинается и заканчивается в одной вершине.
3. Типы связи
3.1. Связный-граф, в котором между любой парой вершин существует, как минимум, один путь.
3.2. Несвязный-если в графе существует хотя бы одна вершина, не связанная с другими
3.3. Разреженный граф-граф имеющий малое число рёбер.
3.4. Мультиграф - грав, в котором разрешается присутствие кратных ребер (их также называют параллельными), то есть ребра, имеющие те же самые конечные вершины.
3.5. Плотный граф- граф, в котором число рёбер близко к максимальному (когда каждая вершина графа связана с любой другой вершиной графа рёбрами).
3.6. Двудольный граф - множество вершин данного графа можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины одной и той же части.
4. Свойства графа
4.1. Инцидентность – понятие, используемое только в отношении ребра и вершины. Если v1, v2 - вершины, а e = (v1, v2) - соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут.
4.2. Смежность – понятие, используемое в отношении только двух рёбер, либо только двух вершин: два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
4.3. Маршрут – это проход по графу через заданную последовательность вершин.
5. Представление графа
5.1. Таблица инцидентности.
5.1.1. Указываются связи между инцидентными элементами графа (ребра и вершины). Столбцы матрицы соответствуют ребрам, строки – вершинам. В каждом элементе матрицы инцидентности неориентированного графа стоит 0, если вершина не инцидентна ребру, или 1, если вершина инцидентна ребру. В случае ориентированного графа, в матрицу вносятся 1, если вершина инцидентна ребру и является его началом, или 0, если вершина не инцидентна ребру, или -1, если вершина инцидентна ребру и является его концом.
5.1.1.1. Взвешанный и неориентированный граф
5.1.1.1.1. Таблица инцидентности, соответствующая графу, выглядит следующим образом
5.2. Таблица смежности
5.2.1. Матрица смежности графа – это способ представления графа в виде квадратной матрицы, в которой каждый элемент принимает одно из двух значений: 0 или 1 для невзвешенного графа.
5.2.2. Например, на рисунке невзвешенный неориентированный граф, где между вершинами 1 и 2 есть ребро, а значит в матрице смежности на пересечении первой строки и второго столбца и второй строки и первого столбца будут стоять единицы.
5.2.2.1. Матрица смежности для графа, изображенного на рисунке, представлена следующим образом
5.2.3. Граф может быть представлен с помощью вектора смежности. В векторе смежности для каждой вершины хранятся номера смежных с ней вершин.
5.3. Список смежности – ещё один из способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из "соседей" этой вершины. Если граф взвешенный, то рядом с номером вершины-соседа также указывается длина ребра до этого соседа.
5.3.1. Cписок смежности для ориентированного взвешенного графа