Смекни!
smekni.com

Методические рекомендации рассмотрены и одобрены кафедрой вм и по 13 февраля 2008 г., протокол №5 Рецензент Кацуба В. С., канд физ мат наук, доцент кафедры высшей математики и программного обеспечения (стр. 5 из 10)

Каждой релейно-контактной схеме (РКС), составленной из переключателей x1, x2, …, xn, можно поставить в соответствие булеву функцию, называемую ее функцией проводимости:

Функция проводимости РКС задается при помощи формулы логики, соответствующей этой РКС. Например, РКС, изображенная на рис. 2, имеет функцию проводимости

, таблица значений которой имеет вид:

х

y

f(x, y)

1

1

1

1

0

0

0

1

0

0

0

0

3. Графы

3.1. Основные определения

Рассмотрим некоторое конечное множество точек V = {v1, v2,…,vn} и конечное множество линий Х, соединяющих некоторые пары из точек множества V. Полученная совокупность точек и линий называется графом и обозначается G = {V, X}.

Элементы множества V называются вершинами графа, а элементы множества Хребрами.

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

Ребра, соединяющие одну и ту же пару вершин, называются кратными (или параллельными) ребрами (ребра х4, х5 графа G1 на рис. 4).

Если х – ребро графа, соединяющее вершины vi, vj, то вершины vi и vj называются концами ребра х.

Множество ребер графа Х можно задать, как множество пар вершин из множества V. Если пары в этом множестве Х являются упорядоченными, то граф называется ориентированным или орграфом. Ребра орграфа называют дугами и на рисунках помечают стрелками (рис. 4).

Если х = (vi, vj) – дуга орграфа, то вершина vi называется началом дуги х, а вершина vjконцом дуги х.

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

3.2. Матрицы графов

Для того, чтобы задать граф, необходимо задать множества его вершин и ребер (V и X). Иногда граф задают списком ребер (дуг), например, орграф G2, изображенный на рис. 4, можно задать следующим списком дуг:

X = {х1, х2, х3, х4, х5, х6} = {(v1, v4), (v1, v4), (v4, v2), (v2, v4), (v2, v3), (v3, v4)}.

В этом списке каждой из 6-ти дуг орграфа соответствует упорядоченная пара вершин (если граф неориентированный, то порядок записи вершин в каждой паре – произвольный).

Если граф содержит изолированные вершины, т.е. не связанные ни с одной другой вершиной ребрами (дугами) графа (см. вершину v5 в графе G1 на рис. 4), то список ребер не даст полного представления о графе. Кроме того, использовать список ребер (дуг) можно только при относительно небольшом количестве вершин графа. Для практического использования более удобен матричный способ задания графов.

Пусть G = {V, X} – граф, где V = {v1, v2,…,vn}, X = {x1, … , xm}.

Если вершины графа vi, vj являются концами ребра х, то говорят, что вершины vi, vj и ребро х инцидентны.

Матрицей инцидентности графа G называется матрица размерности n´m B(G), элементы которой

bij =

Строки матрицы инцидентности графа соответствуют его вершинам, а столбцы – ребрам.

Для орграфа вершина vi и дуга хj инцидентны, если vi является началом или концом дуги хj. Элементы матрицы инцидентности орграфа определяются по формулам:

bij =

(1)

Вершины vi, vj графа G называются смежными, если существует ребро х = (vi, vjX, инцидентное этим вершинам (соединяющее эти вершины).

Матрицей смежности графа G называется квадратная матрица A(G) порядка п, каждый элемент которой aij равен количеству ребер, инцидентных вершинам vi и vj.

Для орграфа G = {V, X} элементы матрицы смежности определяются по формулам:

aij =

(2)

Пример. Записать матрицу инцидентности и матрицу смежности для орграфа G2, изображенного на рис. 4.

Решение. Данный граф является ориентированным. Для построения матрицы инцидентности составим таблицу, используя формулы (1). Заполняем таблицу по столбцам, соответствующим дугам орграфа: в j-м столбце ставим в i-й строке

«–1», если вершина vi является началом дуги хj,

«1», если вершина vi является концом дуги хj,

«0» в остальных случаях (вершина vi и дуга хj не инцидентны).

x1

x2

x3

x4

x5

x6

Получили матрицу инцидентности:

В(G2) =

.

v1

–1

–1

0

0

0

0

v2

0

0

1

–1

–1

0

v3

0

0

0

0

1

–1

v4

1

1

–1

1

0

1

Для построения матрицы смежности составим таблицу, используя формулы (2). Так как граф G2 ориентированный, то элемент матрицы aij равен количеству ребер с началом в i-й вершине, а концом в j-й вершине.

v1

v2

v3

v4

Получили матрицу смежности

A(G2) =

v1

0

0

0

2

v2

0

0

1

1

v3

0

0

0

1

v4

0

1

0

0

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

Кроме матриц инцидентности и смежности существуют и другие формы матричного задания графов. Матричный метод задания графов удобен для обработки данных на ЭВМ.