Теория графов: основные понятия и определения

Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

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

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями — пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо — граф.

Графы служат удобным средством описания связей между объектами. Ранее мы уже использовали графы как способ наглядного представления конечных бинарных отношений. Но граф используют отнюдь не только как иллюстрацию. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный. Для решения задачи выбора требуется проводить определенные вычисления над графами. При решении подобных задач удобно использовать алгебраическую технику, да и само понятие графа необходимо формализовать.

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

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

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

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

Неориентированные графы

Неориентированный граф $G$ задается двумя множествами $G=(V,E)$ , где $V$ — конечное множество, элементы которого называют вершинами или узлами; $E$ — множество неупорядоченных пар на $V$ , т.е. подмножество множества двухэлементных подмножеств $V$ , элементы которого называют ребрами. Для каждого ребра $\{u,v\}\in E$ считаем, что $u$ и ${v}$ — различные вершины.

Если ребро $e=\{u,v\}$ , то говорят, что ребро $e$ соединяет вершины $u$ и ${v}$ , и обозначают это мы $u\mapsto v$ ; если необходимо, указывают имя графа $G\colon u\mapsto_{G}v$ .

Вершины $u$ и ${v}$ , соединенные ребром $(u\mapsto v)$ , называют смежными, а также концами ребра $\{u,v\}$ . Если $u\mapsto v$ , говорят, что вершины $u$ и ${v}$ связаны отношением непосредственной достижимости.

Ребро $e$ называют инцидентным вершине ${v}$ , если она является одним из его концов.

Степенью вершины ${v}$ называют число $\operatorname{dg}v$ всех инцидентных ей ребер.

Для вершины ${v}$ множество $\Gamma(v)=\{x\colon\,x\mapsto v\}$ называют множеством смежных с ${v}$ вершин. Справедливо равенство $\operatorname{dg}v=|\Gamma(v)|$ .

Цепь в неориентированном графе $G$ — это последовательность вершин (конечная или бесконечная) $v_0,v_1,\ldots,v_n,\ldots$ , такая, что $v_i\mapsto v_{i+1}$ для любого $i$ , если $v_{i+1}$ существует. (Под конечной последовательностью понимается кортеж вершин.)

Для конечной цепи $v_0,v_1,\ldots,v_n$ число $n~(n\geqslant0)$ называют длиной цепи. Таким образом, длина цепи есть число ее ребер, т.е. всех ребер, соединяющих вершины $v_i$ и $v_{i+1}~(i=\overline{0,n-1})$ . Цепь длины 0 — это произвольная вершина графа.

Говорят, что вершина ${v}$ неориентированного графа $G$ достижима из вершины $u$ этого графа и обозначают и $u\shortmid\!= \!\shortmid^{\ast}\!v$ , если существует цепь $v_0,v_1,\ldots,v_n$ такая, что $u=v_0,$ $v_n=v$ (при этом говорят также, что данная цепь соединяет вершины $u$ и ${v}$ , которые называют концами цепи). Таким образом, задано отношение достижимости $\shortmid\!=\!\shortmid^{\ast}$ в неориентированном графе. Оно является рефлексивно-транзитивным замыканием отношения $\shortmid\!\!\!-\!\!\!\shortmid$ непосредственной достижимости.

Отношение достижимости в неориентированном графе рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности

Если существует цепь ненулевой длины, соединяющая $u$ и ${v}$ , то пишут $u\shortmid\!= \!\shortmid^{+}\!v$ . Если необходимо явно указать длину цепи, то пишут $u \shortmid\!=\!\shortmid^{n}\!v$ и говорят, что существует цепь длины $n$ , соединяющая $u$ и ${v}$ .

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

Федорова Галина Владимировна

Страницы

Ориентированный и неориентированный граф.

Теория графов: основные понятия и определения

Неориентированные графы

Комментариев нет:

Отправить комментарий