Краткое введение в теорию графов
Первая часть: основные понятия и полные графики
Теория графов — это раздел науки о данных и больших данных. Например, это мощный инструмент для обучения без учителя, поскольку его можно использовать для классификации, кластеризации, визуализации данных сложных сетей и многого другого. Но обо всем по порядку, давайте начнем с основных понятий и определений.
Определения
Прежде всего, что такое график? Граф G — это упорядоченная пара G=(V, E), где V представляет набор вершин, а E — набор ребер. На практике мы можем добавить W в качестве весов, связанных с каждым ребром, чтобы G=(V, E, W). В этой статье мы рассмотрим это последнее определение графа.
Графы могут быть как ориентированными, так и неориентированными. В неориентированных графах ребра идут в обе стороны, но в ориентированных графах ребра направлены из одной вершины в другую.
Полный граф — это конкретный граф, каждая вершина которого связана с каждой другой вершиной (см. иллюстрацию ниже). Полный граф неориентирован.
Иллюстрации
Давайте проиллюстрируем эту концепцию графиков на карте железных дорог:
- каждая железнодорожная станция представляет собой вершину
- каждый путь от вокзала к другому является ребром
- стоимость билета (связанного с каждым путем) для перехода с одной железнодорожной станции на другую является весом
Веса могут представлять многие вещи. В нашем предыдущем примере вес — это стоимость билета, но это также может быть расстояние между каждой железнодорожной станцией или любой другой показатель.
Графики на практике
Для упрощения мы теперь будем рассматривать только полные графы. Но имейте в виду, что существует множество типов графиков.
На практике графики часто представляют в виде декартовой координатной плоскости:
- Вершины — это точки плана с координатами (x,y).
- Ребра - векторы плана
- Вес ребер - евклидово расстояние
Пример: неориентированный полный граф из четырех вершин
Этот полный граф «G» имеет 4 вершины и 6 ребер. Слева направо координаты вершин: A (0,0), B (2,2), C (2,5), D (4,0).
Если учесть, что веса, связанные с каждое ребро представляет собой евклидово расстояние (округленное до целого числа), теперь мы можем полностью представить этот график как:
G = ((A,B,2), (A,C,5), (A,D,4), (B,C,3), (B,D,2), (C,D,5))
Каждый элемент списка выше является ребром. Вы можете прочитать его первый элемент как:
«Существует ребро (в обе стороны) между вершинами A и B, и вес, связанный с этим ребром, равен 2».
Примечание. На приведенной выше диаграмме ось X и ось Y имеют разные масштабы. Вот почему расстояние между A и D выглядит больше, чем расстояние между A и C (или C и D), но на самом деле это не так.
Теперь, когда вы получили основные понятия о графах, мы увидим, как реализовать и визуализировать их в python в моих следующих статьях.
Обо мне: французский студент, изучающий науку о данных, всегда готовый к новым вызовам. Не стесняйтесь добавлять меня в LinkedIn, Twitter или Medium.
