Специальность 071800 (Мехатроника) (стр. 12 )

Определение. Функционально полная система называется базисом, если при удалении из нее любой ПФ, она перестает быть функционально полной.

Если из нашей системы убрать , то останется 0, который один не дает функционально полной системы (он принадлежит ); если же убрать 0, то останется , которая сохраняет 1. Поэтому система ∑ образует базис.

Ответ. Данная система является функционально полной и образует базис.

Замечание.

1. Ранее отмечалось, что из функций двух переменных только ⊕  и линейные, поэтому нелинейность можно было определить сразу.

2. Для проверки функциональной полноты после того, как таблица заполнена для первой функции, для второй достаточно было проверить лишь принадлежность или непринадлежность ее классу . Для проверки на базис таблица просматривается полностью.

Дополнительные указания по графам

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

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

Мы должны изучить основные понятия теории графов и некоторые задачи, связанные с ними. Терминология этого раздела дискретной математики не является общеупотребительной, она своя у разных авторов. Мы будем придерживаться определений из [6]. Если вы пользуетесь другими пособиями, сравнивайте, какие понятия совпадают с [6], а какие отличаются. Рассмотрим эти понятия на примерах.

Пример. Дан граф G:

1. Определить степени всех вершин графа.

2. Записать матрицу смежности вершин .

3. Записать матрицу инцидентности .

4. Указать мосты и точки сочленения, если они есть.

5. Проверить, является ли граф эйлеровым.

6. Проверить, является ли граф гамильтоновым.

7. Проверить, является ли граф двудольным. Если да, указать подмножества V1 и V2.

8. Записать какой-нибудь маршрут от до .

9. Указать какой-нибудь простой цикл.

10. Построить дерево, покрывающее граф.

Решение. 1.Степенью вершины графа называется количество рёбер, инцидентных ей. Вершине инцидентно лишь  одно ребро e1, значит, , а вершине инцидентны ребра , , , значит, и т. д. Составим таблицу.

	1	3	2	2	4	3	3	3	1

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

, где — число вершин, равно количеству рёбер, соединяющих вершины и .

Если граф не содержит кратных рёбер и петель, то ,  если вершины и смежные, и в противном случае.

В нашем примере , так как нет петель, , так как вершина смежна , и т. д.

3.Матрица инцидентности имеет m строк (m-количество рёбер) и n столбцов, , если ребро инцидентно вершине , и в противном случае.

Так для графа G , так как ребро инцидентно вершине , , а .

,

.

4. В графе можно удалять рёбра и вершины. Если удаляется ребро, то все вершины сохраняются, если же удаляется вершина, то удаляются все инцидентные ей рёбра. Вершина, при удалении которой число компонент связности увеличивается, называется точкой сочленения.

Ребро с таким свойством называется мостом.

В графе G точками сочленения являются вершины Действительно, при удалении вершины связный граф G превращается в две компоненты,

так как удаляются рёбра , , . Аналогично при удалении   получается вершина и связный граф.

При удалении получим

Мостами являются рёбра и .

5. Необходимым и достаточным условием эйлеровости графа является его связность и четность степеней всех вершин. Так как в графе G есть вершины степени 3 и 1, то он не является эйлеровым.

6. Критерия гамильтоновости графа не существует. Однако при наличии висячих вершин (вершин степени 1), мостов или точек сочленения граф гамильтоновым не будет. В графе G есть и висячие вершины, и мосты, и точки сочленения. Следовательно, граф не является гамильтоновым.