Дискретная математика. Часть II

Министерство образования и науки Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

Б. М. Веретенников, В. И. Белоусова, А. Б. Веретенников

ДИСКРЕТНАЯ 
МАТЕМАТИКА

Часть II

Учебное пособие

Рекомендовано методическим советом
Уральского федерального университета
для студентов вуза, обучающихся
по всем направлениям подготовки бакалавриата
и специалитета ИРИТ-РтФ

Екатеринбург
Издательство Уральского университета
2017

УДК 519(075.8)
ББК 22.176А73
          В31

Рецензенты:
кафедра прикладной математики ФГБОУ ВО «Уральский государственный 
экономический университет» (завкафедрой, канд. физ.-
мат. наук, доц. Ю. Б. Мельников);
канд. физ.-мат. наук, ст. науч. сотр. И. Н. Белоусов (Институт математики 
и механики УрО РАН)

Научный редактор — канд. физ.-мат. наук, доц. Н. В. Чуксина

 
Веретенников, Б. М.
В31    Дискретная математика : учебное пособие / Б. М. Веретенников, 
В. И. Белоусова, А. Б. Веретенников. — Екатеринбург : Изд-во 
Урал. ун-та, 2017. — Ч. II. — 84 с.

ISBN 978-5-7996-2165-0 (ч. II)
ISBN 978-5-7996-1195-8

Данное учебное пособие является продолжением учебного пособия 
«Дискретная математика», Ч. I (авторы: Б. М. Веретенников, В. И. Белоу-
сова). Работа включает в себя следующие разделы дискретной математики: 
многочлены над конечными полями, коды, исправляющие ошибки и эле-
менты теории графов. Предлагаются упражнения для самостоятельного ре-
шения. Пособие предназначено для студентов инженерных направлений 
и специальностей ИРИТ–РтФ УрФУ.
Библиогр.: 8 назв. Табл. 3. Рис. 12.

УДК 519(075.8)
ББК 22.176А73

ISBN 978-5-7996-2165-0 
© Уральский федеральный
ISBN 978-5-7996-1195-8 
     университет, 2017

Оглавление

Глава I  
Многочлены над конечными полями .......................................... 5
§ 1. Обзор общей теории многочленов ..................................... 5
§ 2. Теория сравнений для многочленов и примеры 
        построения полей небольшого составного порядка ......... 9
§ 3. Основные теоремы о многочленах над конечными 
        полями ...............................................................................12

Глава II  
Коды, исправляющие ошибки ...................................................22
§ 1. Линейные коды .................................................................22

1.2. Вычисление проверочной матрицы с помощью 
        систематической порождающей матрицы .................24
1.3. Дуальные коды ............................................................27
1.4. Примеры специальных кодов .....................................28
        Упражнения для самостоятельной подготовки .........29
§ 2. Линейные коды, исправляющие ошибки .........................30

2.1. Декодирование линейных кодов с помощью 
        смежных классов .........................................................31
2.2. Декодирование с помощью синдромов ......................34
2.3. Код Хэмминга и расширенный код Хэмминга ..........38
2.5. Циклические коды ......................................................43
2.6. Нахождение систематической порождающей 
        матрицы циклического кода.......................................48
2.7. Специальный вид проверочной матрицы 
        циклического кода ......................................................50
2.8. Коды, порожденные элементами из расширения 
        основного поля ...........................................................51
2.9. Коды БЧХ ....................................................................53
2.10. Примеры кодов БЧХ .................................................54
2.11. Декодирование кодов БЧХ........................................56

Оглавление

Глава III  
Элементы теории графов ...........................................................62
§ 1. Основные понятия теории графов ....................................62
        1.1. Матрицы графов .........................................................67
§ 2. Алгоритмы на графах.........................................................71

2.1. Поиск в глубину ..........................................................71
2.2. Поиск в ширину ..........................................................73
2.3. Минимальный остов графа .........................................74
2.4. Наибольшее паросочетание в двудольном графе ......79

Список литературы ..................................................................82

Глава I.  
Многочлены над конечными полями

§ 1. Обзор общей теории многочленов

Напомним, что многочленом степени n над полем F  называется 
выражение f x
( ) вида a x
a x
a
n
n
n
0
1
1
+
+
+
-

, где все aj лежат 

в F, причем a0
0
№ . В частности, многочлен степени 0 над F  — 
это элемент F, причем степень нулевого многочлена считается 
равной (
).
-Ґ  При этом a0 называется старшим коэффициентом, 
а a xn
0
 называется старшим членом f x
( ). Будем обозначать 

deg ( )
f x  как степень f x
( ).

Складываются и умножаются многочлены по обычным 
школьным правилам, из чего следует, что deg
( ) ( )
deg ( )
f x g x
f x
(
) =
+
 

g
( ) ( )
deg ( )
deg ( ).
f x g x
f x
g x
(
) =
+

Теорема 1. Множество всех многочленов над полем F  является 
ассоциативным коммутативным кольцом с единицей, причем 
это целостное кольцо главных идеалов.
Эта теорема была доказана в части I данного пособия. На-
помним, что коммутативное кольцо R называется целостным, 
если из того, что a b
R
, О  и ab = 0 всегда следует, что a или b равны 
нулю. Заметим, что в данном пособии понятие идеала не используется, 
хотя в литературе встречается изложение основ теории 
алгебраического кодирования с широким применением 
этого понятия.
Кольцо всех многочленов над полем F  обозначается F x
[ ].

Глава I. Многочлены над конечными полями 

Теорема 2. Для любых многочленов f x
( ) и g x
( ) из F x
[ ] при 

g x
( ) № 0 существует единственный многочлен r x
( ) из F x
[ ] такой, 
что f x
g x
q x
r x
( )
( )
( )
( )
=
Ч
+
 для некоторого q x
( ) из F x
[ ], причем 

deg ( )
deg ( ).
r x
g x
<

Заметим, что r x
( ) называется остатком при делении f x
( ) на 

g x
( ), а q x
( ) — частным.
Определение. Пусть f x
( ) и g x
( ) — многочлены из F x
[ ] 
и хотя бы один из них не равен 0. Тогда наибольшим общим делителем 
называется нормированный многочлен из F x
[ ] наибольшей 
степени, который без остатка делит f x
( ) и g x
( ).

Практически наибольший общий делитель f x
( ) и g x
( ), который 
будем в дальнейшем обозначать f x
g x
( ), ( ) ,
(
)  находится 
с помощью алгоритма Евклида, описанного в части I данного 
пособия.
Очень важной является следующая теорема.
Теорема 3. Пусть f x
( ) и g x
( ) — многочлены из F x
[ ] и d x
( ) их 
наибольший общий делитель. Тогда найдутся такие многочлены 
u x
( ) и v x
( ) из F x
[ ], что f x u x
g x v x
d x
( ) ( )
( ) ( )
( ).
+
=

Нахождение многочленов u x
( ) и v x
( ) осуществляется с помощью 
модифицированного алгоритма Евклида, описанного 
также в части I пособия.
Определение. Многочлены f x
( ) и g x
( ) из F x
[ ] называются 
взаимно простыми, если их наибольший общий делитель равен 
1.

Теорема 4. Пусть f x
g x
h x
F x
( ), ( ), ( )
[ ].
О
 тогда имеют место 
следующие утверждения:
1) f x
( ) и g x
( ) взаимно простые тогда и только тогда, когда 
существуют такие многочлены u x
( ) и v x
( ) над F, что f x u x
g x v x
( ) ( )
( ) ( )
+
=1
 

f x u x
g x v x
( ) ( )
( ) ( )
;
+
=1

2) f x
h x
g x
h x
f x g x
h x
( ), ( )
,
( ), ( )
( ) ( ), ( )
;
(
) =
=
(
) Ю (
) =
1
1
1

§ 1. Обзор общей теории многочленов

3) f x g x
h x
g x
h x
f x
h x
( ) ( )
( ),
( ), ( )
( )
( );


(
) = Ю
1

4) f x
g x
f x
h x
g x
h x
f x
g x h x
( )
( ), ( )
( ),
( ), ( )
( )
( ) ( ).



(
) = Ю
1

Здесь запись f x
g x
( )
( )

 означает, что f x
( ) делится на g x
( ) без 
остатка. В дальнейшем этот факт мы часто будем обозначать 
так: g x
f x
g x
f x
( )|
( )
( )делит
( ) .
(
)

Определение. Элемент α из F  называется корнем многочлена 
f x
( ) из F x
[ ], если f ( )
,
a = 0  т. е. при подстановке в выражение 
для f x
( ) элемента α вместо x в итоге получается 0.

Теорема 5 (Безу). Если α — корень многочлена f x
( ), то f x
( ) 
делится на (
)
x -a  без остатка.
Следствие 1. Любой многочлен f x
( ) степени n і1 над полем 

F  имеет не более n различных корней.
Определение. Поле F  называется алгебраически замкнутым, 
если любой многочлен над F  степени і1 имеет корень в F .

Пример. Поля  и  не являются алгебраически замкнутыми, 
так как, например, x 2
1
+  не имеет корней в , зато поле  
алгебраически замкнуто (это утверждение называется основной 
теоремой алгебры).
Теорема 6. Пусть F  — алгебраически замкнутое поле  
и f x
F x
f x
( )
[ ], deg ( )
.
О
і1  Тогда f x
a
x
x
n
( )
(
)
(
),
=
-
ј
-
0
1
a
a
 где a0 — 
старший коэффициент f x
( ), n
f x
= deg ( ).

Определение. Элемент α из F  называется корнем кратности k 
многочлена f x
( ) из F, если f x
x
g x
k
( )
(
)
( )
=
-a
 и g( )
.
a № 0

С учетом этого определения получаем следствие к теореме 6.
Следствие 2. Любой многочлен f x
( ) степени і1 над алгебраически 
замкнутым полем F  представим в виде f(x) = 

f x
a
x
x
k
r
kr
( )
(
)
(
) ,
=
-
ј
-
0
1

1
b
b
 где элементы bi — попарно различные 
корни f x
( ) кратностей ki соответственно.
Определение. Пусть f x
F x
( )
[ ].
О
 Тогда f x
( ) неприводим над 

F, если f x
( ) нельзя представить в виде f x
g x h x
( )
( ) ( ),
=
 где g x
( ) 

Глава I. Многочлены над конечными полями 

и h x
( ) — многочлены степеней і1 над F . В противном случае 

f x
( ) называется приводимым над F .

Примеры. Ясно, что любой многочлен первой степени непри-
водим, но существуют неприводимые многочлены степени >1. 
Например, квадратный вещественный трехчлен неприводим 
над  тогда и только тогда, когда его дискриминант меньше 
нуля. Однако над алгебраически замкнутым полем все непри-
водимые многочлены имеют степени 1.

Теорема 7. Любой многочлен f x
( ) степени і1 над полем F  
представим в виде f x
g
x
g
x
r
( )
( )
( ),
=
ј
1
 где все g x
i( ) неприводи-
мы над F  и данное представление однозначно с точностью 
до перестановки сомножителей и их умножения на ненулевые 
элементы из F .

Формула для f x
( ) в теореме 7 называется неприводимым раз-
ложением f x
( ) над полем F .

Пример. (
)(
)
(
)(
)
2
2 3
6
3
3 2
4
x
x
x
x
+
+
=
+
+
 — неприводимые раз-
ложения многочлена f x
x
x
( ) =
+
+
6
18
12
2
 над .

Теорема 8. Пусть f x
( ) — многочлен над полем F  степени 2 
или 3. Тогда f x
( ) неприводим над F  тогда и только тогда, ког-
да f x
( ) имеет корень в F .

С помощью этой теоремы можно получить все неприводи-
мые многочлены над F2 степеней 2, 3 и 4. А именно, существу-
ет единственный неприводимый многочлен степени 2: x
x
2
1
+
+ , 
два неприводимых многочлена степени 3: x
x
3
1
+
+  и x
x
3
2
1
+
+  
и три неприводимых многочлена степени 4: x
x
4
1
+
+ , x
x
4
3
1
+
+ , 

x
x
x
x
4
3
2
1
+
+
+
+ . Доказательство имеется в части I данного по-
собия.
В качестве еще одного примера использования теоремы 
8 найдем все нормированные неприводимые многочлены сте-
пени 2 над F3.

Пусть многочлен f x
x
x
( ) =
+
+
2
a
b неприводим над F3. Тогда 

b =1 или b = 2.

§ 2. Теория сравнений для многочленов  и примеры построения полей небольшого составного порядка

Пусть сначала f x
x
x
( )
.
=
+
+
2
1
a

Имеем: f ( )
1
2
0
1
=
+
=
Ю
=
a
a
 и f ( )
.
2
2
2
0
2
=
+
=
Ю
=
a
a
 Таким 
образом, по теореме 8, x
x
2
1
+
+
a
 неприводим тогда и только 
тогда, когда a = 0.

Теперь f x
x
x
( )
.
=
+
+
2
2
a

Имеем: f
f x
x
( )
( )
1
0
2
2
=
=
Ю
=
+
a
 и f
f x
x
( )
( )
.
2
2
0
2
2
=
=
Ю
=
+
a
 

f x
x
( )
.
0
2
2
=
Ю
=
+
a
 Снова из теоремы 8 следует, что x
x
2
2
+
+
a
 неприводим 
тогда и только тогда, когда a =1 или a = 2.

Таким образом, существует ровно 3 неприводимых многоч-
лена над F3 :
 
x
x
x
2
2
1
2
+
+
+
,
 и x
x
2
2
2
+
+ .

§ 2. Теория сравнений для многочленов  
и примеры построения полей небольшого составного порядка

Всюду ниже F * — мультипликативная группа поля F, т. е. 

F
F
*
\{ }.
=
0  Выпишем сначала основные определения и тео-
ремы. Считаем, что все многочлены лежат в F [x].
Определение 1. g x
h x
f x
( )
( )mod
( )
є
 (читается: g x
( ) сравнимо 
с h x
( ) по модулю f x
( )), если g x
h x
( )
( )
-
 делится на f x
( ).

Определение 2. g x
h x
h x
g x
f x
( )
( )| ( )
( )mod
( ) .
=
є
{
}  Классом вы-

четов по модулю f x
( ) называется g x
( ).
Множество всех классов вычетов F x
[ ] по модулю f x
( ) из F x
[ ] 
обозначается F x
f x
[ ]
( ) .
(
)

Теорема 1. Отношение сравнения в F x
[ ] по модулю f x
( ) из 

F x
[ ] является эквивалентностью в F x
[ ].

Теорема 2 (о свойствах классов вычетов по модулю f x
( )). Пусть 

f x
F x
( )
[ ].
ОТогда имеют место следующие утверждения:

Глава I. Многочлены над конечными полями 

1) "
О
g x
F x
( )
[ ] g x
g x
( )
( );
О

2) g x
h x
g x
h x
( )
( )
( )
( );
О
Ю
=

3) g x
h x
g x
h x
( )
( )
( )
( );
З
№ Ж Ю
=

4) g x
r x
( )
( ),
=
 где r x
( ) — остаток от деления многочлена g x
( ) 
на многочлен f x
( ).

Теорема 3. Пусть f x
F x
( )
[ ].
ОТогда F x
f x
[ ]
( )
(
) — поле тогда 
и только тогда, когда f x
( ) неприводим над F x
[ ].

Теорема 4. В общем случае, если f x
F x
( )
[ ],
Ото F x
f x
[ ]
( )
(
) — 
ассоциативное коммутативное кольцо с единицей. Это кольцо 
называется кольцом вычетов по модулю f x
( ).

Теорема 5. Пусть F  — конечное поле порядка q, f x
F x
( )
[ ].
О
Тогда
 
F x
f x
qn
[ ]
( )
,
(
) =

где n
f x
=
і
deg ( )
,1  причем F x
f x
[ ]
( )
(
) = =
+
+ј+
-
-
{
},
a
a
an
n
0
1
1
1
a
a
 

где все a
F
i О
, а a = x.

Доказательство. Пусть g x
( ) — произвольный многочлен из F x
[ ], 

r x
a
a x
a
x
n
n
( ) =
+
+ј+
-
-
0
1
1
1 — его остаток при делении на f x
( ). 
Тогда g x
r x
a
a x
a
x
a
a
a
n

n

n

n
( )
( )
{
}
,
=
=
+
+ј+
=
+
+ј+
-

-

-

-

0
1
1

1

0
1
1

1
a
a
 
и вторая часть теоремы доказана. Предположим, что a b
F
, О
 
и a
b
=
. Тогда a
b
-  делится на f x
( ), откуда a
b
= . Таким образом, 
число различных классов вычетов по модулю f x
( ) вида a, где 

a
F
О
, равно q и теорема доказана полностью.
Замечание. Отождествив для любого a из F  класс a с a, полу-
чим F x
f x
a
a
an
n
[ ]
( )
{
},
(
) =
+
+ј+
-
-
0
1
1
1
a
a
 где все a
F
i О
.

Следствие 1. Если F  — конечное поле порядка q и f x
( ) — 
неприводимый над F  многочлен степени n і1, то F x
f x
[ ]
( )
(
) — 
поле порядка qn.

Пример 1. Пусть F
F
=
2, f x
x
x
( ) =
+
+
2
1 — неприводимый над 

F2 многочлен. Тогда по теореме 5, F x
f x
[ ]
( )
(
) — поле порядка 4 

§ 2. Теория сравнений для многочленов и примеры построения полей небольшого составного порядка 

и F x
f x
a
a
[ ]
( )
{
},
(
) =
+
0
1a  где a = x и a a
F
0
1
2
0 1
,
{ , }.
О
=
 Найдем все 

степени элемента α. Так как a
a
2
2
2
1
1
1
0
+
+ =
+
+
=
+
+ =
x
x
x
x
, 
то a
a
2
1
= + , a
a
a
a
3
2
1
2
1
=
+
= +
= . Таким образом <a> = 

<
>=
(
)
(
)
a
F x
f x
[ ]
( )
,
*  т. е. α — порождающий элемент мультиплика-

тивной группы рассматриваемого поля порядка 4.

Пример 2. Пусть F
F
=
2, f x
x
x
( ) =
+
+
4
1 — неприводимый над 

F2 многочлен. Тогда по теореме 5, E
F x
f x
=
(
)
[ ]
( )  — поле поряд-
ка 16, причем E
a
a
a
a
=
+
+
+
{
},
0
1
2
2
3
3
a
a
a
 где все ai О{ , }
0 1  и a = x. 
Найдем все степени α. Имеем, a
a
4
1
0
+
+ = , откуда a
a
4
1
= + , 

a
a
a
5
2
=
+
, a
a
a
6
2
3
=
+
, a
a
a
a
a
7
3
3
1
1
=
+ +
= +
+
, α8 = α + α2 + α4 =  

a
a
a
a
a
a
a
2
4
2
2
1
1
=
+
+
=
+
+
+
= +
(
)
, a
a
a
9
3
=
+
, a
a
a
a
a
10
2
4
2
1
=
+
= +
+
, α11 = 

a
a
a
a
11
2
3
=
+
+
, a
a
a
a
a
a
a
12
2
3
4
2
3
1
=
+
+
= +
+
+
 
 
, α13 = α + α2 + α3 + 

a
a
a
a
a
a
2
3
4
2
3
1
=
+
+
+
= +
+
, a
a
a
a
a
14
3
4
3
1
=
+
+
= +
, a
a
a
15
4
1
=
+
= . Таким об-
разом, как и в примере 1, <
>=
a
E *.

Пример 3. Пусть F
F
=
2, f x
x
x
x
x
( ) =
+
+
+
+
4
3
2
1 — другой 
неприводимый многочлен степени 4 над F2. Тогда снова 
E
F x
f x
=
(
)
[ ]
( )  — поле порядка 16. Найдем все степени a = x. 
Имеем: 1
0
2
3
4
+
+
+
+
=
  
 
a
a
a
a
. Так как по хорошо известной 
формуле a
a
a
a
a
a
5
4
3
2
1
1
1
- =
-
+
+
+
+
(
)(
),
 
 
 то a5
1
= . Таким обра-
зом, |
|
a = 5 в E * и в этом случае α уже не является порождающим 
элементом группы E *.

Пример 4. Пусть F
F
=
3, f x
x
x
( ) =
+
+
2
1 — неприводимый мно-
гочлен над F3. Тогда E
F x
f x
=
(
)
[ ]
( )  — поле порядка 9, причем 

E
a
a
=
+
{
},
0
1a  где ai О{ , , },
0 1 2  а a = x. найдем снова все степени α. 
Имеем a
a
2
2
0
+
+
= , откуда a
a
a
2
2
1
2
= - -
= +
, a3 = a + 2a2 = 

a
a
a
a
a
a
3
2
2
2 1
2
2
2
=
+
=
+
+
=
+
(
)
, 
a
a
a
a
a
4
2
2
2
2
2 1
2
2
=
+
=
+
+
=
(
)
, 
a
a
5
2
=
, 

a
a
a
a
6
2
2
2 1
2
2
=
=
+
=
+
(
)
, a
a
a
a
7
2
2
1
=
+
= + , a8 = a + a2 = a + 1 + 

a
a
a
a
2
1
2
1
+
=
+ +
= . Таким образом, <
>=
a
E *.