Кратные рёбра (также называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.
В зависимости от контекста граф может быть определён с разрешением или запрещением иметь кратные рёбра (часто вместе с разрешением или запрещением иметь петли):
- Когда графы определяются с разрешением кратных рёбер и петель, графы без петель называются часто мультиграфами[1] .
- Когда графы определяются c запрещением кратных рёбер и петель, под мультиграфами или псевдографами часто понимаются «графы», которые могут иметь петли и кратные рёбра [2] .
Кратные рёбра полезны, например, при рассмотрении электрических цепей с точки зрения теории графов [3] . Кроме того, они составляют ядро дифференцирующих свойств многомерных цепей [en] .
Планарный граф остаётся планарным, если добавить ребро между двумя вершинами, уже связанными ребром. То есть добавление ребра сохраняет планарность [4] .
Диполь [en] — это граф с двумя вершинами, в котором все рёбра параллельны.
Содержание
Ориентированные графы [ править ]
Определение: |
Ориентированным графом (англ. directed graph) [math]G[/math] называется пара [math]G = (V, E)[/math] , где [math]V[/math] — множество вершин (англ. vertices), а [math] E subset V imes V [/math] — множество рёбер. |
Определение: |
Конечным графом (англ. finite graph) [math]G[/math] называется граф, в котором множества [math]V[/math] и [math]E[/math] — конечны. Следует заметить, что большинство рассматриваевых нами графов — конечны. |
Определение: |
Ребром (англ. edge, дугой (англ. arc), линией (англ. line)) ориентированного графа называют упорядоченную пару вершин [math] (v, u) in E [/math] . |
Определение: |
Изоморфные графы (англ. isomorphic graphs) — два графа [math]A[/math] и [math]B[/math] называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами. |
В графе ребро, концы которого совпадают, то есть [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 ightarrow V[/math] . |
Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).
История и применение
Глава 3. Введение в теорию графов
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о кенигсбергских мостах (1736 г.) Однако, она не находила применения в течение почти 100 лет. Интерес к теории возник благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. В 1847 г. Кирхгофом была разработана теория деревьев, которая послужила важным аналитическим средством для исследования электрических цепей. Законы Кирхгофа для напряжений и токов в цепи полностью определяются контурами и сечениями графа этой цепи и не зависят от природы используемых элементов. Поэтому тщательное изучение понятий контура, сечения и дерева графа дало толчок многим открытиям в теории цепей и, кроме того, внесло большой вклад в теорию графов.
Характерно то, что в терминах графов формулируются многие понятия и задачи прикладных областей: теории игр и программирования, теории передачи сообщений, транспортных сетей, электрических цепей, организационной структуры общества, а также биологии и психологии. В области вычислительной техники теория графов занимает особое место. Она предоставляет большие возможности для построения эффективных алгоритмов и анализа их сложности, дает готовые решения многим задачам вычислительной техники, например, для задачи оптимизации компиляторов. В то же время исследования в каждой из прикладных областей приводят к развитию самой теории графов.
Граф – математический объект, описываемый двумя множествами: G=( V, E ), где V – так называемое множество вершин, а E – множество дуг.
Элементами множества дуг являются упорядоченные пары вершин, т.е. E=< ( a, b): aÎV, bÎV >, т.о. множество Е является подмножеством декартова произведения V´V. Порядок вершин в парах может и не учитываться, тогда элементы множества Е называют ребрами, а сам граф – неориентированным графом, в противном случае – ориентированным или Орграфом. В некоторых случаях рассматриваются так называемые смешанные графы, в них множество Е состоит из элементов обоих видов: дуг и ребер.
В множестве ребер графа допускается более, чем одно ребро с одинаковыми концевыми вершинами. Такие ребра называются параллельными или кратными. Например: ek=(vi, vj) и em=(vi, vj) – кратные ребра.
Если обе концевые вершины ребра совпадают, то такое ребро называется петлей. Например: ek=(vi, vi) – петля.
Граф без петель и параллельных ребер называется простым, в противном случае – мультиграфом.
Граф, не имеющий ребер, называется пустым, а не имеющий вершин (а значит и ребер) – нуль‑графом.
Простой граф, у которого любая пара вершин смежна, называется полным.
Количество вершин в графе называется порядком графа.
Степенью или валентностью вершины называется число инцидентных ей ребер. Будем обозначать степень вершины vi – deg(vi). Вершина нулевой степени называется изолированной. Вершина степени 1 называется висячей, а ребро, инцидентное ей, называется висячим ребром. Заметим, что петля добавляет двойку к степени вершины.
§ 3.3. Способы задания графов
Рассмотрим три способа задания графов: графический, аналитический и матричный.
1) Графический способ.
Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.
На рисунке 12 изображен смешанный граф с вершинами v1, v2,¼, v6, ребрами e1, e2, e3, e5 и дугой e4. Смежные вершины v1, v2, инциденты ребру e1. Вершины v1, v3, инциденты параллельным ребрам e2 и e3. Вершине v4 инциденты петля e5 и дуга e4, причем v4 является началом дуги e4, а v5 – концом этой дуги. Степень вершины v1 равна 3, вершины v2 – 1, вершины v3 – 2, вершины v4 – 3, вершины v5 – 1, вершины v6 – 0. Таким образом, вершины v2 и v5 – висячие, а вершина v6 – изолированная. В случае дуги e4 точнее было бы говорить о полустепенях исхода и захода вершин v4 и v5, а именно: полустепень исхода вершины v4 равна 3, вершины v5 – 0, полустепень захода вершины v4 равна 2, вершины v5 – 1.
2) Аналитический способ.
3) Матричный способ.
Имеется несколько вариантов задать граф матрицей. Наиболее употребимыми являются матрица инциденций и матрица смежности.
а) Матрица инциденций – это прямоугольная матрица, число строк которой равно числу вершин, а число столбцов – числу дуг (ребер) графа. Элементы этой матрицы определяются следующим образом:
Таким образом, для графа на рисунке 12 матрица инциденций такова:
e1 | e2 | e3 | e4 | e5 |
v1 | ||||
v2 | ||||
I= | v3 | |||
v4 | ||||
v5 | -1 | |||
v6 |
По этой матрице легко судить о наличии в графе параллельных ребер (два одинаковых столбца), петли (одна единица в столбце), дуги (значения разных знаков в столбце), изолированной вершины (нулевая строка), висячих вершин (одно ненулевое значение в строке).
б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: . Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:
v1 | v2 | v3 | v4 | v5 | v6 |
v1 | |||||
v2 | |||||
S= | v3 | ||||
v4 | |||||
v5 | |||||
v6 |
По виду этой матрицы также несложно судить о наличии в графе кратных ребер, дуг, петель, висячих и изолированных вершин.
Понятно, что любая квадратная матрица с целыми неотрицательными коэффициентами может быть интерпретирована как граф, а значит, изучение графов можно свести к изучению матриц такого типа. Вообще изучение графов можно расширить, рассматривая матрицы не только с целыми, но и с неотрицательными вещественными элементами. Такие матрицы, например, могут соответствовать графу, представляющему схему дорог, в котором расстояние между вершинами vi и vj равно длине соответствующей дороги. Подобные матрицы называют обычно матрицами весов.
Представление графов матрицами очень удобно при решении задач на компьютере.
Не нашли то, что искали? Воспользуйтесь поиском: