2

Подскажите пожалуйста какова область применения графов?

Какие в основном решаются задачи на графах?

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

3 ответа 3

4

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

К недостаткам можно отнести некоторую прожорливость в плане памяти, пропорциональную числу вершин графа, что вполне логично

1
  • @DreamChild прожорливость в плане памяти, пропорциональную числу вершин графа это вопросы реализации. Матрица смежности, например имеет размерность n^2
    – alexlz
    5 мар 2013 в 9:34
4

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

Ну и отсюда следует что графы не подходят для тех задач, которые к алгоритмам из теории графов не сводятся.

1

Согласен с аналогией про молоток. Графами можно сделать почти всё, но далеко не всегда это будет оптимально. И, наверное, надо ещё сказать, что это всё-таки не структура(т.к. представлений графов полно), а математическая абстракция.
Т.е. массив можно рассматривать как бинарное дерево, но вы ведь не будете говорить про список, что это граф!
Наверное большинство задач на графах -- поиск пути:). В частности, логистика.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.