Часть I. Что такое теория графов и почему она актуальна сегодня?
Графики, особенно сетевые, привлекают мое внимание.
Возможно, это интуитивное предчувствие, что анализ систем в виде графиков расширит мое понимание децентрализованных и централизованных сетей. Математик во мне видит, как точный сетевой анализ может принести большую пользу исследованиям систем, основанных на стимулах. Или, может быть, во мне дизайнер во многом увлечен врожденным артистизмом графиков, подобных приведенному выше - визуально привлекательным, но в конечном итоге богатым информацией.
По какой-то причине, столкнувшись с графами как деревьями в разработке программного обеспечения, как сетями в исследованиях блокчейнов или как r / datais красивой приманкой для кликов, я решил глубоко погрузиться в мир теории графов и ее подотрасль теории сетей. .
Область математики большая. Это дерево знаний разветвляется на постоянно растущее число подполей. Один из самых высокоуровневых способов разделения и описания набора ветвей - это тип числа внутри данной проблемы. Числа в задачах могут быть дискретными, например фиксированными, ограничиваемыми значениями, такими как натуральные числа 1,2,3,4. Или они могут быть непрерывными, числами, которые более точно отображают нашу реальность как динамические, изменяющиеся значения, такие как скорость движения объекта.
Дискретные числа для цифровых часов старой школы - это то же самое, что непрерывные числа для современных аналоговых часов (которые скользят, а не тикают). В первом случае между 11:32 и следующей минутой 11:33 не существует чисел. В последнем случае секундная стрелка непрерывно движется, что означает, что аналоговые часы технически показывают разные значения каждый отдельный момент, когда секундная стрелка перемещается от одной секунды к другой. Лучшим примером раздела математики, охватывающего дискретные числа, является комбинаторика, изучение конечных наборов объектов. Лучший пример раздела математики, основанного на непрерывных числах, - это исчисление, изучение того, как вещи меняются.
Теория графов, подраздел дискретной математики, - это высший уровень изучения связи между вещами. Эти объекты более формально называются вершинами, вершинами или узлами, а сами соединения называются ребрами.
История теории графов
Основная идея графов была впервые представлена в 18 веке швейцарским математиком Леонардом Эйлером. Его попытки и возможное решение знаменитой проблемы Кенигсбергского моста, изображенной ниже, обычно цитируются как источник теории графов:
Немецкий город Кенигсберг (современный Калининград, Россия) расположен на реке Преголя. Географическая структура состоит из четырех основных участков суши, соединенных в общей сложности семью мостами. Вопрос, заданный Эйлеру, был прост: можно ли пройтись по городу таким образом, чтобы пересечь каждый мост один и только один раз (известная как прогулка Эйлера)?
Эйлер, осознавая, что соответствующими ограничениями были четыре тела земли и семь мостов, нарисовал первое известное визуальное представление современного графа. Современный граф, как видно на нижнем правом изображении C, представлен набором точек, известных как v ertices или узлов, которые соединены набором соединительных линий, известных как e dges.
Сначала он попытался нарисовать пути на приведенном выше графе, а затем экспериментировал с несколькими теоретическими графами с чередующимся числом вершин и ребер, и в конце концов экстраполировал общее правило:
Чтобы иметь возможность идти по эйлеровому пути (иначе говоря, без повторения ребер), в графе не должно быть ни одного или двух нечетных узлов?
С этого момента отрасль математики, известная как теория графов, десятилетиями бездействовала. Однако в наше время его применение наконец-то набирает обороты.
Приложения теории графов
Теория графов - это, в конечном счете, изучение отношений. Учитывая набор узлов и соединений, которые могут абстрагироваться от всего, от макетов городов до компьютерных данных, теория графов предоставляет полезный инструмент для количественной оценки и упрощения многих движущихся частей динамических систем. Изучение графиков с помощью фреймворка дает ответы на многие проблемы компоновки, построения сетей, оптимизации, сопоставления и эксплуатации.
По мере того, как мы переходим к изучению основ набора графов и обозначений матриц (2), нам не помешает усилить нашу мотивацию самодидактизма, охватив несколько приложений - краткий обзор теории графов в действии:
В разработке программного обеспечения они известны как довольно распространенные структуры данных, удачно названные деревьями решений. В мире электротехники целая дисциплина вращается вокруг создания, расчета и обслуживания многокомпонентных электрических цепей, которые часто отображаются в виде диаграмм в соответствии с принципами теории графов. Тем временем в области молекулярной биологии ученые экстраполируют модели прогнозирования для отслеживания распространения болезней или моделей размножения. И, наконец, в противоречивом мире анализа сетей социальных сетей мы стали свидетелями того, как теория графов использовалась для создания уже стандартных функций, таких как степени разделения в LinkedIn и функции рекомендации друзей в Facebook. Давайте перейдем к следующей статье, чтобы познакомиться с общепринятыми обозначениями графов.
изначально опубликовано
источники
