Введение в теорию графов

 

Немного предыстории

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Эти две работы Эйлера заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.

Но сначала определимся с определением графа. Граф – это абстрактный математический объект, представляющий собой множество вершин и набор соединений между ними. В случае Эйлера, графами можно представить мосты Кенингберга где соединения будут сами мосты, а вершинами – их концы.

Типичный граф

Граф, как математический объект, оказался полезным во многих теоретических и практических задачах. Структуру мозга, как бы сложной и многоуровневой она не являлась, можно представить в виде огромного и длинного графа. Если говорить об информационных технологиях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. А теперь…

Немного определений

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

А вот и пример маршрута (красным цветом)

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

Граф, в котором известно направление линий, называется ориентированным, а если неизвестно – неориентированным. Все просто.

Undirected.svg Directed.svg

Причем в ориентированных графах соединения называются дугами.

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

Взвешенный граф во всей красе

И на последок одно свойство

Гомеоморфность графов

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

undefined Подразделённые графы

Несмотря на развитие теории графов и ее широком применении в сфере IT, теория графов содержит большое количество нерешенных проблем и пока не доказанных гипотез.  Например одна из гипотез, Гипотеза Харари, гласит если граф имеет более трёх cоединений , то его можно однозначно восстановить по подграфам, полученным удалением единственного соединений.

Поделиться постом
Have your say!
0 0
1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>