Начать. Это бесплатно
или регистрация c помощью Вашего email-адреса
Графы создатель Mind Map: Графы

1. Определение. Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

2. Виды графов

2.1. Ориентированные- такой граф, в котором можно двигаться от вершины к вершине только в одном направлении.

2.2. Неориентированные- граф, в котором можно двигаться в обе стороны.

2.3. Смешанный граф-в котором присутствуют как ориентированные ребра, так и неориентированные.

2.4. Взвешенный-граф, в котором каждому ребру в соответствие поставлено некоторое числовое значение – вес.

2.5. Невзвешенный-никакого числового значения рёбрам не поставлено.

2.6. Петля- это ребро, которое начинается и заканчивается в одной вершине.

3. Свойства графа

3.1. Инцидентность – понятие, используемое только в отношении ребра и вершины. Если v1, v2 - вершины, а e = (v1, v2) - соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут.

3.2. Смежность – понятие, используемое в отношении только двух рёбер, либо только двух вершин: два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

3.3. Маршрут – это проход по графу через заданную последовательность вершин.

4. Типы связи

4.1. Связный-граф, в котором между любой парой вершин существует, как минимум, один путь.

4.2. Несвязный-если в графе существует хотя бы одна вершина, не связанная с другими

4.3. Разреженный граф-граф имеющий малое число рёбер.

4.4. Мультиграф - грав, в котором разрешается присутствие кратных ребер (их также называют параллельными), то есть ребра, имеющие те же самые конечные вершины.

4.5. Плотный граф- граф, в котором число рёбер близко к максимальному (когда каждая вершина графа связана с любой другой вершиной графа рёбрами).

4.6. Двудольный граф - множество вершин данного графа можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины одной и той же части.

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писок смежности для ориентированного взвешенного графа