Теория графов - Введение

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

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

График - это графическое представление набора объектов, где некоторые пары объектов связаны ссылками. Взаимосвязанные объекты представлены точками, называемыми вершинами, а связи, соединяющие вершины, называются ребрами .

Формально граф - это пара множеств (V, E), где V - множество вершин, а E - множество ребер, соединяющих пары вершин. Посмотрите на следующий график -

Пример графика

На приведенном выше графике

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Приложения теории графов

Теория графов имеет свои приложения в различных областях техники -

  • Электротехника - понятия теории графов широко используются при проектировании схемных соединений. Типы или организация соединений называются топологиями. Некоторыми примерами топологий являются топологии «звезда», «мост», «серия» и «параллельная топология».

  • Информатика - теория графов используется для изучения алгоритмов. Например,

    • Алгоритм Крускала
    • Алгоритм Прима
    • Алгоритм Дейкстры
  • Компьютерная сеть - отношения между взаимосвязанными компьютерами в сети следуют принципам теории графов.

  • Наука - Молекулярная структура и химическая структура вещества, структура ДНК организма и т. Д. Представлены графами.

  • Лингвистика - дерево синтаксического анализа языка и грамматика языка использует графики.

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