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

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

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.

Графы - наиболее легкий и примитивный путь описания различных процессов разной природы и назначения. Значительная часть задач связанных с теорией графов не имеет простых решений и относится к задачам полного перебора, NP-полным задачам, для которых на сегодняшний день не найдено способов укладывающихся в конечное, поддающееся описанию число действий, называемых полиноминальными алгоритмами.

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

Очевидно - самый простой и наглядный способ представления графов - изображение их на плоскости, представляя вершины точками, а ребра - линиями их соединяющими. Графы не есть понятие геометрическое, ни даже топологическое, хотя в отдельно взятых приложениях можно их трактовать и таким образом.

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

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