Теория графов и ее применение

В последние годы интенсивно развивается и широко применяется теория графов. Существует несколько причин нарастания интереса к этой теории:

- наглядности теоретико-графовых структур;

- доходчивость языка теории графов;

- широкое применение теории в практических системах;

- использование ПК в написании графовых алгоритмов и решении практических задач.

Теория графов применяется в таких областях как: физика, химия, теория связей, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология, лингвистика и т.д.

В свою очередь, теория графов тесно связана и пользуется такими разделами математики как:

- теория групп;

- теория матриц;

- численный анализ;

- теория вероятностей;

- топология;

- комбинаторный анализ.

Существует множество практических применений и приложений графовых моделей (как было уже перечислено) во многих науках.

Рассмотрим поподробнее некоторые из применений:

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

2. В физике-теоретике вершинами обозначают молекулы, а смежность вершин толкуют как взаимодействие наибольшей близости.

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

Подобная интерпретация ориентированных графов возникает и в разделах численного анализа, посвященных вычислению собственных значений матриц.

4. Теория деревьев (вид графов) используется в электротехнике и электронике. Так решение совместной системы линейных алгебраических уравнений позволяет найти значение силы тока в каждом проводнике (дуге) электрической цепи и в каждом ее контуре и наоборот, моделируя электротехнический процесс можно решить систему линейных алгебраических уравнений и дифференциальных уравнений. Таким образом, связаны теория графов и электротехнические процессы.

5. Теория графов применяется в органической химии при изучении изомеров предельных углеводородов.

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

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