Графическое представление графов

Аналитическое сочетание.

Теория графов

Была введена в 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).

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

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

Если граф ориентированный, то ребра имеют одно направление, такие графы называются графами с кратными ребрами. Мультиграф – граф с кратными ребрами.

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

Мультиграф может быть задан матрицей смежности.

, где - кратность дуги.

Всякая квадратная матрица с целыми элементами может быть рассмотренная как матрица смежности некоторого мультиграфа.

- мера.

В некоторых задачах ребрам можно присвоить вещественное неотрицательное число – мера (мощность пропускной способности). Такой граф, в котором каждому ребру приписана мера – граф с напряженными ребрами. Он может быть представлен в виде матрицы
матрицы смежности. Но при этом её элементами является мера

В результате матрицу М называют матрицей мер.

Если имеем квадратную матрицу элементами которой вещественное неотрицательное число, то можно рассматривать как матрицу с напряженными ребрами.

Дата добавления: 2014-01-05