Часть III - Переход от простых графов
Давайте сделаем шаг назад, чтобы сделать еще несколько шагов вперед в нашем изучении основ теории графов. Предыдущая статья в этой серии в основном вращалась вокруг объяснения и записи чего-то, что называется простым графиком. Теперь мы вернемся назад, чтобы выделить свойства простого графика, чтобы обеспечить знакомую отправную точку для остальной части этой статьи.
В предыдущей статье мы определили наш граф как простой из-за четырех ключевых свойств: ребра неориентированы и не взвешены; граф не содержит кратных ребер и самонаправленных петель. Это далеко не исчерпывающий список всех свойств графа, однако это подходящее место для продолжения нашего пути. В этой статье мы перейдем от простых графиков к более сложным (но довольно распространенным) графам за счет введения ключевых свойств графов.
Общие свойства графа
Графы, как и динамические системы объектов, которые они представляют, принимают непостижимое количество форм и размеров; поэтому он помогает создать набор свойств для определения уникальных атрибутов графа. Давайте рассмотрим определяющие свойства нашего примера простого графа:
- Ненаправленные края
- Невзвешенные края
- Исключение нескольких кромок и петель
Ненаправленные и направленные графики
Ребра, представленные в приведенном выше примере, не имеют никаких характеристик, кроме соединения двух вершин. Им явно не хватает направления.
Самая ясная и самая масштабная форма классификации графов начинается с типа ребер внутри графа. Существует два основных типа ребер: с направлением и без. Неориентированный граф, как и пример простого графа, представляет собой граф, состоящий из неориентированных ребер. В ориентированном графе или орграфе каждая вершина имеет как минимум одно входящее и одно исходящее ребра, что означает строгое направление каждого ребра относительно двух связанных вершин.
Невзвешенные и взвешенные графики
Точно так же взвешенное ребро - это просто ребро с соответствующим числом или значением, также известное как вес (обычно в форме не -отрицательные целые числа). Значения веса позволяют моделировать более сложные проблемы, которые более точно представляют реальные системы с помощью графиков. Во многих реальных приложениях вес края также обычно называют стоимостью края; Реальные примеры весов ребер на графиках включают измерение длины маршрута, пропускной способности кабеля или энергии, необходимой для перемещения по определенному пути. Изображение ниже представляет собой краткое наглядное представление о том, как должен был бы выглядеть наш примерный график, если бы он содержал взвешенные ребра:
Множественные края и петли
Третье наше простое свойство, выделенное в нашем примере графа, представляет два отдельных отношения графа, которые основаны на одном и том же свойстве: простоте графа, основанном на отношениях вершин.
В нашем примере графа каждая вершина имеет ровно одно ребро, соединяющее ее с другой вершиной - ни одна вершина не соединяется с другой вершиной через несколько ребер. Кроме того, ни одна вершина не возвращается к себе. Граф, который содержит одно или оба, несколько ребер и петли, известен как мультиграф.
На изображении ниже показаны эти два различия с помощью графика справа:
Циклы - ациклические и циклические графики
Мы не перечисляли это свойство ранее, потому что и ациклические, и циклические графы могут считаться простыми графами, однако циклическое свойство графа является ключевой формой классификации, которую стоит рассмотреть. В теории графов цикл - это путь из ребер и вершин, в котором вершина достижима из самой себя; Другими словами, цикл существует, если можно перейти от одной вершины обратно к самой себе, не повторяя (не возвращаясь) ни одно ребро или вершину на своем пути.
Граф, содержащий хотя бы один цикл, известен как циклический граф. Граф без единого цикла известен как ациклический граф. В нашем примере ниже мы выделим один из многих циклов на нашем простом графике, а справа покажем ациклический график:
источники
Теперь, когда мы охватили базовое понимание ключевых свойств, связанных с графами, пора перейти к очень интересной теме теории графов: сетям! В следующей статье и далее мы начнем строить понимание сетей на более глубоком уровне - в конечном итоге применяя эти принципы к сетевому анализу.
