Jump to content

Теория графов


Recommended Posts

Думаю, пока сервер не открыт, можно пофлудить.

В этом треде хотел бы малым и незнающим раскидать за теорию графов.

Определение: Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где  V есть подмножество любого счётного множества, а  E — подмножество V*V}.

Определение, как всегда скучное. А теперь своими словами: Граф - это такая математическая абстракция, где есть точки и они соединены линиями. Вообще штука очень полезная и применяется повсеместно. И в вузах её изучают очень активно. Хотя для рядового программиста\айтишника её знать нахуй не надо. В основном всяким ученым - хуям дрочённым.

images?q=tbn:ANd9GcR_YyipsBWlONUygHTrTmi

 

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

На этот раз всё, если работягам зайдёт, то буду добавлять.

  • Like 1
Link to post

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...