Методические рекомендации рассмотрены и одобрены кафедрой вм и по 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, vj)ÎX, инцидентное этим вершинам (соединяющее эти вершины).
Матрицей смежности графа 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 |
Матрица инцидентности более информативна, чем матрица смежности, т.к. по ней можно восстановить не только нумерацию вершин и связи между ними, но и нумерацию ребер. Однако, при помощи матрицы инцидентности задают только графы, не имеющие изолированных вершин (в матрице смежности изолированной вершине соответствуют нулевая строка и нулевой столбец).
Кроме матриц инцидентности и смежности существуют и другие формы матричного задания графов. Матричный метод задания графов удобен для обработки данных на ЭВМ.