Минимальные элементы частично упорядоченного множества. Условие минимальности. Условие индуктивности. Условие обрыва убывающих цепей. Вполне упорядоченные множества.

всякое непустое подмножество имеет хотя бы один минимальный (в М)элемент (условие минимальности)

2) все элементы из Робладают нек-рым свойством s, если этим свойством обладают все минимальные элементы множества Ри если справедливость свойства е для любого можно вывести из того, что е справедливо для всех (условие индуктивности)

 

Билет 12

Компоненты графа. Точки сочленения. Число связности графа.

Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

 

Точка сочленения - вершина графа, при удалении которой количество компонент связности возрастает

 

Подграф G' графа G называется компонентой связности графа G, если все вершины G' составляют класс эквивалентности по отношению связности, а множество рёбер G' это все инцидентные этим

 

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

 

 

Билет 13

Аксиома выбора и эквивалентные ей утверждения

Аксиомой выбора называется следующее высказывание теории множеств: «Для каждого семейства непустых непересекающихся множеств существует (по меньшей мере одно) множество d, которое имеет только один общий элемент c c каждым из множеств b данного семейства».

 

Теорема Цермело

Любое множество можно вполне упорядочить.

 

Принцип максимума Хаусдорфа

В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество

 

Лемма Куратовского-Цорна

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

 

 

Билет 13

Метрика графов. Центр, радиус и диаметр графа.

Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.

Центром графа называется такая вершина, что максимальное расстояние между ней и любой другой вершиной является наименьшим из всех возможных; это расстояние называется радиусом графа.

 

Билет 14

Понятие алгебраической структуры. Гомоморфизм. Изоморфизм.

алгебраическая структура — множество G (носитель) с заданным на нём набором операций и отношений (сигнатура), удовлетворяющим некоторой системе аксиом. Понятие алгебраической системы родственно понятию универсальной алгебры.

 

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

 

Решётка, структура — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани. Отсюда вытекает существование этих граней для любых непустых конечных подмножеств.

 

Гомоморфизм (от др.-греч. ὁμός — равный, одинаковый и μορφή — вид, форма) — это морфизм в категории алгебраических систем. Это отображение алгебраической системы А, сохраняющее основные операции и основные соотношения.

Изоморфизм — взаимно однозначный (биективный) гомоморфизм.

 

Граф G называется изоморфным графу H, если существует биекция f из множества вершин графа G в множество вершин графа H, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот — если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины f − 1(A) в вершину f − 1(B). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Билет 14

Циклический ранг (цикломатическое число) графа. Фундаментальные циклы.

Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим. Существует соотношение: p1(G) = p0(G) + E − V, где p1(G) — цикломатическое число, p0 — число компонент связности графа,

 

Билет 15

Решетки. Группы. Кольца.

Решётка, структура — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани. Отсюда вытекает существование этих граней для любых непустхконечных подмножеств.

 

Билет 15