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 that you have read and understand our privacy policy and code of conduct.

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