Главная страница
Навигация по странице:

  • 2. Что такое граф 3. Классификация графов4. Где используются графы5. Графовые Базы6. СУБД Neo4jИстория происхождения графов

  • Что такое граф

  • Где используются графы

  • Польза графовой модели

  • Графовые базы данных. Субд neo4j История происхождения графов


    Скачать 2.34 Mb.
    НазваниеСубд neo4j История происхождения графов
    АнкорГрафовые базы данных
    Дата01.09.2022
    Размер2.34 Mb.
    Формат файлаpptx
    Имя файлаГрафовые базы данных.pptx
    ТипДокументы
    #658857

    Графовые базы данных

    Содержание:

    1. История происхождения графов


    2. Что такое граф?

    3. Классификация графов

    4. Где используются графы

    5. Графовые Базы

    6. СУБД Neo4j

    История происхождения графов

    Среди жителей Кёнигсберга (нынешний Калиниград) была распространена такая загадка: как пройти по всем городским мостам через реку, не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

    Решил задачку Леонард Эйлер, сформулировав ряд правил и доказав, что пройти по мостам, не повторяясь, невозможно.

    Так и зародилась теория графов.

    Что такое граф?

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

                                                                    

    Ориентированный граф

    Ориентированный граф — это граф, ребро которого имеет заданное направление между вершинами.

    Петля

    Если вершина графа соединена ребром сама с собой, то такое ребро называется петлей.

    Графовая модель данных

    Граф — это множество вершин (узлов, node) и ребер (взаимосвязей, edge). Вершины представляют сущности, а ребра — связи, в атрибутах которых может содержаться информация. Графовая база данных моделирует сущности в виде графа в том виде, как это определено в теории графов. Структуры данных — это вершины и ребра. Атрибуты — это свойства вершин и ребер. Связь — это соединение вершин. В отличие от других моделей данных, в графовых базах данных в приоритете взаимосвязи между сущностями. Поэтому не требуется вычислять связи с помощью внешних ключей или какими-то другими способами. Можно создавать сложные модели данных, используя только абстракции вершин и ребер.

    Классификация графов

    Связанный граф

    Если из любой вершины есть путь до любой другой — такой граф называется связанным.

    В данном примере есть путь от вершины А до вершины D, хоть он и пролегает через другие вершины.

    Сильно связанный граф

    Граф называется сильно связанным, если любая его вершина соединена с любой другой ребром. Если связи ориентированные — то граф называется ориентированно связанным.

    Взвешенный граф

    Если к каждому ребру в соответствие поставлено некоторое число (вес ребра) — такой граф называется взвешенным.

    Мультиграф

    Граф, в котором разрешается присутствие параллельных ребер, то есть ребер, имеющих те же самые конечные вершины. Параллельные ребра выделены красным.


    Где используются графы?

    Графы используются в геоинформационных системах (ГИС), логистике, социальных сетях, магазинах и других сферах жизни.

    Схема метро — взвешенный граф, на ребрах которого указано время перехода между станциями, или прогона состава.

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

    Данный граф применим в системах навигации для поиска оптимального маршрута. Перекрестки — вершины графа, а дороги — ребра.

    Молекулярный граф — связный неориентированный граф, соответствует формуле химического соединения таким образом, что вершины графа — атомы молекулы, а ребра — химические связи между этими атомами.

    Наиболее частный пример графов в разработке — граф социальной сети, в котором отображены дружеские отношения между людьми, их вкусовые предпочтения и прочее.

    Социальный граф

    Даже 3D-объект можно представить в виде графа:

    Графовая модель данных

    Граф — это множество вершин (узлов, node) и ребер (взаимосвязей, edge). Вершины представляют сущности, а ребра — связи, в атрибутах которых может содержаться информация. Графовая база данных моделирует сущности в виде графа в том виде, как это определено в теории графов. Структуры данных — это вершины и ребра. Атрибуты — это свойства вершин и ребер. Связь — это соединение вершин. В отличие от других моделей данных, в графовых базах данных в приоритете взаимосвязи между сущностями. Поэтому не требуется вычислять связи с помощью внешних ключей или какими-то другими способами. Можно создавать сложные модели данных, используя только абстракции вершин и ребер.


    Польза графовой модели?

    В настоящее время бизнес и пользователи требуют приложений, которые работают все с большим и большим объемом данных, ожидая при этом высокой производительности и надежности. Представление данных в виде графа предлагает удобные средства для обработки сложных связей. Этот подход позволяет решить многие проблемы и помогает получить результаты в рамках заданного контекста.

    Моделирование данных: от реляционной модели к графовой

    Графовые базы

    Первая графовая СУБД Neo4j создана в 2007 году, сейчас их уже десятки, наиболее популярные:


    написать администратору сайта