ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 30
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Батухтин Максим Сергеевич
Билет №4
1.Бинарные отношения на множестве(определения, свойства, примеры)
Ответ:
Бинарным (или двухместным) отношением r между множествами A и B называется произвольное подмножество AB, т. е.
.В частности, если A=B (то есть rÍA2), то говорят, что r есть отношение на множестве A.
Элементы a и b называются компонентами (или координатами) отношения r.
Пример: Пусть даны два множества A={1; 3; 5; 7} и B={2; 4; 6}. Отношение зададим следующим образом t={(x; y)ÎA´B | x+y=9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере Dt={3; 5; 7} и Rt= B={2; 4; 6}.
2. Определение: Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа.
Теорема Дирака Если в простом графе с
вершинами 
для любой вершины 
, то граф 
является гамильтоновым.Пример:
Простой (гамильтонов) цикл выделен сплошной линией (1,2),(2,3),(3.4),(4,5),(5,1). Заметим, что если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.
Если гамильтонов граф объединить с еще одной вершиной ребром так, что образуется висячая вершина, то такой граф гамильтоновым не является, поскольку не содержит простого цикла, проходящего через все вершины графа.
№4
Решение: Порядок расположения элементов имеет значение и в узоре 10 кружков, т. е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска кружков повторяется (в условии сказано, что 6 белых и 4 черных), то это перестановка с повторением. Итак, Ответ: узор можно составить 20 способами.