Теория графов в дискретной математике

Теория графов в дискретной математике

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

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

Graph theory in discrete mathematics

Annotation. Currently, graph theory is actively developing. Graph theory is a branch of discrete mathematics that studies the properties of graphs. Graph theory methods are widely used in discrete mathematics. They are extremely important in the analysis and synthesis of various discrete converters: computer function blocks, software complexes, etc. Nowadays, it is difficult to imagine studying graph theory without using software of various types and levels, since it minimizes the difficulties in performing routine graph construction operations.

Keywords: mathematics, graphs, vertex, edge, path, problem, computer, computer engineering, programs.

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

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

Основоположник теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кенигсбергских мостах, ставшей впоследствии одной из классических задач теории графов [8].

Теория графов востребована во многих областях: в химии, информатике, программировании, экономике, логистике, схемотехнике и пр.

Многие структуры, представляющие практический интерес в логике, информатике, математике и других науках, могут быть представлены графами. Например, строение любого интернет-ресурса можно смоделировать при помощи ориентированного графа, в котором вершины — это статьи, а дуги — гиперссылки. Вся сеть Интернет тоже граф.

Терминология теории графов до сих пор строго не определена. В частности, в одной из IT-монографий сказано: «В программистском мире нет единого мнения о том, какой из двух терминов — "граф" или "сеть" — использовать. Мы выбрали термин "сеть", так как он, по-видимому, чаще встречается в прикладных областях». Более того, теория графов содержит большое количество нерешенных проблем и пока не доказанных гипотез [9].

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

Графы состоят из набора узлов, также называемых вершинами, и ребер, представляющих связи между этими узлами. Каждое ребро соединяет две вершины.

Графы делятся на ориентированные и неориентированные. Ориентированный граф – такой граф, в котором можно двигаться от вершины к вершине только в одном направлении. Например, на рисунке 1 можно двигаться из вершины v0 в v1, а из v1 в v0 нельзя. В неориентированных графах можно двигаться в обе стороны. Например, на рисунке 2 из вершины 1 можно двигаться в вершину 2, и наоборот [1].

[pic 1]

Рисунок 1 – Ориентированный граф

[pic 2]

Рисунок 2 – Неориентированный граф

Два варианта представления графов —  это списки смежности и матрицы смежности. Последние проще индексируются и управляются, но занимают больше места, чем первые.

Для ориентированных графов характерно направление. Во взвешенных графах к каждому узлу применяется понятие расстояния и затрат. Циклические графы содержат циклы, которые можно обходить бесконечно [1].

Алгоритм Дейкстры применяется для нахождения кратчайшего расстояния между двумя узлами взвешенного графа. Несмотря на свою эффективность, он в некотором смысле недоработан, в связи с чем разработано множество других алгоритмов, предназначенных для обнаружения наилучшего варианта обхода графа [6].