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

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

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

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

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

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

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

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

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

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

Electrical Engineering- Понятия теории графов широко используются при проектировании схемных соединений. Типы или организация соединений называются топологиями. Некоторые примеры топологий: звезда, мост, последовательная и параллельная топологии.

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

• Алгоритм Крускала
• Алгоритм Прима
• Алгоритм Дейкстры

Computer Network - Отношения между взаимосвязанными компьютерами в сети соответствуют принципам теории графов.

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

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

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