Графическое представление графов
Аналитическое сочетание.
Теория графов
Была введена в 17 веке немецким математиком Кёнигом. Развитие нашла в теории автоматов, программировании и т.д. Проблема с терминологией, новая терминология была разработана отечественными математиками.
Определения и способы задания графов.
Следуя Бержу, будем называть графом упорядоченную пару (x, Г) из непустого множества X и его отображения Г, множества x в себе.
G=(x, F)
G=G(x)
Отображение Г ставит в соответствие элемент некоторого декартового множества (X*X).
То есть граф, в этой формулировке, есть отношение на множестве x.
Граф может быть задан:
1. Аналитически
2. Графически
3. с помощью матрицы
Пример:
Пусть X есть граф X = { }
А факториальное множество X по отношению отображения и каждого элемента будет выражением X/Г = {Г } – отношение в виде сочетаний.
Задание графов, при котором задается множество Х и переплетаются все пары множества в котором и являются отображением .
Из приведенного отображения можно записать:
- граф с петлей
..
Каждому элементу множества Х ставится в соответствие точка плоскости или точка пространства называется вершиной.
Каждой паре ставится в соответствие линия, соединяющая с , стрелкой направленной от к . Эта линия называется дугой. Независимо от конкретного изображения Г множество , называют дугой или множеством дуг, а множество к – множеством вершин
Для представления дуги вершина – начальная, а – конечная. Если начальная и конечная совпадают, то дуга называется петлей. Говорят, что вершины , инвариантны дуге и говорят, что дуги инвариантны вершинам .
Такие вершины называют смежными. Для смежных дуг есть хоть одна вершина инвариантная им обоим.
Матричный способ задания графов
Отношение можно задать на множестве, при этом матрица будет прямоугольной.
Каждому ставится в соответствие отображение дуги , причем
,то есть дуга не существует. Поскольку в этой матрице единица ставится на пересечении смежных строк и столбцов, то эта матрица называется матрицей смежности.
Каждому графу ставится в соответствие единственная матрица смежности. Каждую квадратную матрицу, составленную из нулей и единиц, можно рассматривать как матрицу смежности.
Предположим, что у матрицы смежности некоторого графа каждой дуге соответствует противоположно направленная дуга :
Такую пару дуг чертят без стрелок.
А*B
A = {a, b, c, d, e}
B = {x, y, z}
Aa bc de
Ba, ax, ay, bx, by, bz, cx, cy, cz, dx, dy, dz, cx, cy, cz
Для каждого графа G(x) можно построить обратный ему G(x) = отличающийся от всех его дуг, противоположный, такой граф называется обратным.
Очевидно, что если G(x) неориентированный граф, то не меняет ориентации.
Матрица смежности такого графа получается транспонированием начального графа. Существуют графы, в которых вершины не инцидентны ни одному ее ребру. Вершины – изолированные.
Граф, состоящий только из изолированных вершин, называют нуль-графом. Противоположный нуль-граф G(x) называется полным, если из утверждения, что не принадлежит G(x) => , принадлежит G(x).
Это означает, что любая пара вершин соединены в одном направлении. В полном неориентированном графе любая пара вершин соединены звеном. Если в полном графе в каждой вершине добавить петлю, то получим граф с петлями.
В теории графов рассмотрены мультиграфы, в которых некоторые пары вершин соединены между собой.
Если граф ориентированный, то ребра имеют одно направление, такие графы называются графами с кратными ребрами. Мультиграф – граф с кратными ребрами.
В виде мультиграфа может быть представление в виде турнирной таблицы. Мультиграфы нельзя рассматривать как отношения множества вершин, так как им нельзя построить кратность отношения на множестве.
Мультиграф может быть задан матрицей смежности.
, где - кратность дуги .
Всякая квадратная матрица с целыми элементами может быть рассмотренная как матрица смежности некоторого мультиграфа.
- мера.
В некоторых задачах ребрам можно присвоить вещественное неотрицательное число – мера (мощность пропускной способности). Такой граф, в котором каждому ребру приписана мера – граф с напряженными ребрами. Он может быть представлен в виде матрицы
матрицы смежности. Но при этом её элементами является мера
В результате матрицу М называют матрицей мер.
Если имеем квадратную матрицу элементами которой вещественное неотрицательное число, то можно рассматривать как матрицу с напряженными ребрами.