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

Другими словами, он устраняет восприятие того, что считается трудным, из реальности, что это может быть легко вычисленный.

Итак, каков пример теории графов?

Подумайте, когда вы планируете путешествие из A в B.

Когда вы это говорите, это не звучит почти как сложно по сравнению с тем, когда вы изображаете это. Важно определить шаги, которые необходимо предпринять, чтобы добраться от отправной точки до пункта назначения. Например, вы планируете путешествие, чтобы добраться от основания до вершины горы, но на пути есть несколько препятствий ... Что вы делаете?

Создайте путь!

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

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

Это еще один пример использования теории графов для упрощения вашего путешествия. Обратным будет направленный график, где вы можете только перейти от A к B, но можете не переходить от B к A.

Отличный пример использования теории графов - это Карты Google. Если вы пытаетесь добраться из одного места в другое, он дает вам четкие указания, по которым вам нужно двигаться. Причины, по которым это не неориентированный график:

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

Вы заметили что-то другое на графиках?

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

Итак, вернемся к вопросу.

Особенность этих графов заключается в том, что некоторые из узлов имеют два или более ребра, соединенных с ними. Что это значит?

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

Итак, каково значение наличия одного или нескольких ребер для определенного узла? Разве это не сбивает с толку? Какова его настоящая цель?

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

немаркированный график противоположен этому - он описывает график, который не содержит информации, прикрепленной к ребра, который является примером графов, которые мы видели ранее.

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

А? Почему дополнительная информация требует стоимости?

Ну…

Стоимость можно определить разными способами. Может случиться так, что при планировании поездки вам может стоить много денег или времени, чтобы переходить от одного узла к другому по сравнению с тем, когда вы выбираете другой маршрут, который дает вам более низкую стоимость или более эффективные временные рамки. Например, начиная с узла C на графике выше, какое ребро будет самым дешевым или самым быстрым для получения на другой узел. Будет ли это узел 5, 6 или 4?

Было бы, конечно, 4. Это показывает, что вы упрощаете путь от одного узла к другому, используя взвешенный график. взвешенный график имеет такой же алгоритмический подход, что и поиск в ширину . Если вы хотите узнать больше о поиске в ширину и поиске в глубину, оставьте комментарий ниже.

Надеюсь, вы уже многому научились. Есть еще несколько графиков, о которых нужно знать…

Ого! Что здесь происходит? Не пугайтесь, это так же просто, как и другие графики, которые я вам показал ... Вы можете видеть, что это оба взвешенных, маркированных, неориентированных графиков (потому что края имеют некоторую стоимость, на краях нет стрелок, и к каждому край). Однако один из графиков является связанным графом, а другой - двусвязным графом. . Вы можете угадать, какой из них какой?

Да ты прав! Полагаю, ты прав ...

Итак, график слева - это связный граф, потому что все узлы, которые проходят в графе, связаны кромкой. Справа изображенный граф представляет собой двусвязный граф, который описывает граф, в котором некоторые из его частей связаны , а некоторые из них не подключены.

Что такое несвязанный граф? Как выглядит несвязанный график? Это описывает диаграмму, которая отключена. В этом примере Узел 0 не подключен ни к одному из других узлов.

Последний! Мы почти закончили ...

Слышали ли вы о термине в теории графов, называемом изоморфным?

Итак, чтобы график был изоморфным, он должен быть идентичным другому график.

Возьмите этот пример ниже. Оба они не изоморфны - это означает, что они не одинаковы.

Вы можете сказать почему?

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

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

Прежде чем мы подведем итоги, предлагаем вам небольшую викторину. Если вы думаете, что знаете ответ, попробуйте! Подсказка: c обратите внимание на стрелки и на то, на что они указывают!

Какие из этих графов изоморфны?

Большое спасибо за чтение. Надеюсь, вы узнали что-то новое сегодня .

Сделайте несколько хлопков, если вы хотите больше таких чтений.

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

Пока…