4. Графы и векторные пространства

Современная алгебра является ценным и полезным инструментом при изучении и решении многих научных и инженерных проблем. Очень полезным оказалось определение алгебраической структуры множества объектов, так как сильные и элегантные результаты, полученные для алгебраической структуры, можно затем перенести на эти множества. Теории систем, электрических цепей, кодирования, последовательных и комбинационных переключательных цепей, а также вычислительная техника — лишь немногие примеры, показывающие преимущество такого подхода.

В этой главе мы покажем, что графу можно сопоставить векторное пространство, и детально изучим свойства двух важных векторных подпространств: циклов и разрезающих множеств. В части II книги мы увидим, что эти подпространства фактически определяют пространства напряжений и токов электрической цепи.

В первых двух разделах этой главы мы дадим представление о некоторых элементарных алгебраических понятиях и некоторых результатах, используемых в дальнейшем. Для более детального ознакомления с этими вопросами следует обратиться к работам [4.1- 4.3].

4.1. Группы и поля

Рассмотрим конечное множество . Обозначим символом «+» бинарную операцию, определенную на множестве S. Эта операция сопоставляет каждой паре элементов а и b, принадлежащих S, единственный элемент, обозначаемый а + b. Множество S называется замкнутым относительно операции «+», если элементы a, b, а + b принадлежат S. Говорят, что операция «+» ассоциативна, если для любых а, b, с из множества S. Операция «+» называется коммутативной, если равенство справедливо для любых а, b, принадлежащих S.

Определим понятие группы. Множество S, в котором выполняется бинарная операция «+», называемая операцией сложения, является группой, если имеют место следующие аксиомы:

1) S замкнуто относительно «+»,

2) «+» является ассоциативной операцией,

3) в множестве существует такой единственный элемент , что для любого а, принадлежащего S. Элемент называется

нулевым элементом группы.

4) Для каждого элемента а множества S существует такой единственный элемент b, что Элемент b называется элементом, обратным к а, и наоборот. Очевидно, что нулевой элемент является обратным к самому себе. Группа называется абелевой, если операция «+» коммутативна. Обычным примером группы является множество всех целых чисел, на котором определена обычная операция сложения. В этой группе О является нулевым элементом, обратным элементом для всех а, принадлежащих S. Отметим, что эта группа — абелева. Является ли множество 5 всех целых чисел, на котором определена операция умножения, группой? (Нет. Почему?).

Другим важным примером группы является множество целых чисел с операцией сложения по модулю этой группе 0 — нулевой элемент. Далее, целое число является обратным к целому числу а, для любого а не равного 0. Естественно, 0 обратен к самому себе. Эта группа также абелева.

Ниже приведена таблица операции сложения для

Введем понятие «поле». Множество F, на котором определены две операции называемые операциями сложения и умножения соответственно, является полем, если выполняются следующие аксиомы:

1) F — абелева группа относительно операции «+», нулевой элемент которой обозначается через е.

3) Множество — абелева группа относительно операции умножения.

3) Операция умножения является дистрибутивной относительно операции сложения, т. е. для любых а, b, с, принадлежащих множеству F.

В качестве примера вновь рассмотрим множество на котором выполняются операции сложения и умножения по модулю . Как было показано ранее, множество является абелевой группой относительно операции сложения по модулю с нулевым элементом 0. Нетрудно видеть, что множество будет группой относительно операции умножения

по модулю тогда и только тогда, когда — простое число. Эта группа также является абелевой. Можно проверить, что операция умножения по модулю дистрибутивна относительно операции сложения по модулю . Таким образом, множество будет полем тогда и только тогда, когда простое число.

Поле обычно обозначают символом и называют полем Галуа. Ниже в качестве примера приводится таблица операции умножения для GF (5):

Особый интерес представляет поле GF (2), т. е. множество целых чисел с операциями сложения и умножения по модулю 2. В этом поле