Основные определения. Матрица смежности вершин

Логические функции

Матрица смежности вершин

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

В общем случае, имеет место следующая теорема, касающаяся матрицы смежности V графа.

Теорема. Матрица V ⁿ дает число ориентированных маршрутов длины n между любыми двумя вершинами ориентированного графа.

Пусть имеется функция, заданная на некотором множестве М. Функция называется логической, если она принимает значения в конечном множестве N. Если множество N содержит п элементов, то логическая функция называется п -значной. Перечень всех символов, соответствующих области значений логической функции, называется алфавитом, а сами элементы множества N – буквами этого алфавита.

Логическая функция называется однородной, если её аргументы принадлежат тому же множеству, что и значение функции. Другими словами, логическая функция отображает декартову степень множества N ⁿ в само множество N. Областью определения однородной функции служит множество наборов, называемых словами, где каждый из аргументов замещается буквами k -ичного алфавита {0, 1, …, k -1}. Количество п букв в данном слове определяет его длину.

Определим общее число различных однородных логических функций n переменных. Очевидно, число всевозможных слов длины п в k -ичном алфавите равно. Так как каждому из этих слов можно поставить в соответствие любое из k значений множества N, то общее количество однородных логических функций n переменных равно.

Если буквами алфавита служат числа от 0 до k- 1, то каждое слово символически представляется упорядоченной последовательностью п таких чисел и рассматривается как запись п -разрядного числа в позиционной системе счисления с основанием k, т. е.. Числа служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение стро­гого порядка). Аналогично номерами функций можно считать -разрядные числа в той же системе счисления.

Так, в трехзначном алфа­вите {0, 1, 2} словами длины 4 будут все четырехразрядные числа с основанием k = 3, т. е. 0000, 0001, 0002, 0010, 0011,..., 2221, 2222, которые соответствуют десятичным числам от 0 до 80. Поставив каждому такому четырехразрядному числу в соответствие одну из букв алфавита {0, 1, 2}, получим некоторую функцию четырех переменных,причем количество таких функций выражается огромным числом 3⁸¹.