Лекция 3. Элементы теории графов
Теория графов – это направление математики, особенностью которой является геометрический подход к изучению математических объектов. Часто ее относят к топологии, так как во многих случаях рассматриваются лишь топологические свойства графов. Однако она пересекается со многими направлениями теории множеств, комбинаторной математики, алгебры, геометрии, теории игр, математической логики и другими математическими дисциплинами.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Эйлер решал очень известную головоломку о мостах Кёнигсберга. Термин «граф» впервые был введен спустя 200 лет (в 1936 г) Д. Кениго. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния, максимального паросочетания и др. Математические развлечения и головоломки тоже являются частью теории графов. Теория графов быстро развивается, находит все новые приложения.
Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.
§ 3.1. Понятие графа.
Графом G (V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е его двухэлементных подмножеств множества V (Е – множество ребер).
G (V, E) = V; E , V ≠ , E ⊂ 2V
Определение 3.1.1. Граф G – это математический объект, состоящий из множества вершин X = <x1, x2, . xn> и множества ребер A = <a1, a2. an>. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A).
Для многих задач несущественно, являются ли ребра отрезками прямых или криволинейными дугами; важно лишь то, какие вершины соединяет каждое ребро.
Существуют два основных вида графов (и множество их подвидов): ориентированные и неориентированные.
Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).
Основные определения теории графов
В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).
Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).
Если имеется ребро [math] (v, u) \in E [/math] , то говорят:
- [math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
- [math] u [/math] и [math] v [/math] — смежные.
- Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
- Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .
Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,
v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.
| Определение: |
| Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname |
Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).
Кратные рёбра
Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.
Кратные рёбра, соединяющие две вершины.
В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):
- Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами[1] .
- Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра [2] .
Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов [3] . Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей [en] .
Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность [4] .
Диполь [en] — это граф с двумя вершинами, в котором все рёбра параллельны.
Кратные рёбра
Из Википедии, бесплатной энциклопедии
Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.
В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):
- Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами[1] .
- Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра [2] .
Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов [3] . Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей [en] .
Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность [4] .
Диполь [en] — это граф с двумя вершинами, в котором все рёбра параллельны.
