3.3.2.5. Решите следующие задачи по обходу графов:

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

2. В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы, выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

3. Утверждают, что в одной компании из пяти человек каждый знаком с двумя другими. Возможна ли такая компания?

4. В некотором государстве 101 город. Все города соединены дорогами с односторонним движением, причем в каждый город входит 50 дорог и из каждого города выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой, проехав не более, чем по двум дорогам.

5. На плоскости даны 6 точек так, что никакие три из них не лежат на одной прямой. Каждая пара точек соединена отрезком синего или красного цвета. Докажите, что среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет.

6. В некотором государстве 101 город. Некоторые города соединены дорогами с односторонним движением, причем в каждый город входит 40 дорог и из каждого города выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого, проехав не более, чем по трем дорогам.

7. Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки.

8. Жук ползет по ребрам куба. Сможет ли он последовательно обойти все ребра, проходя по каждому ребру ровно один раз? Указание: задумайтесь над вопросом: сколько раз жук может побывать в каждой вершине?

8. Художник нарисовал картину "Контур квадрата и его диагонали". Мог ли он нарисовать свою картину, не отрывая карандаша от бумаги и не проводя одну линию дважды? Указание: из каждой точки, за исключением начала и конца пути карандаша, должно исходить четное число линий.

9. Содержание

   • Кубанский государственный аграрный университет
   • 1.1.2. Изобразите геометрически множество истинности одноместных предикатов g(X) и p(X), если:
   • 1.1.3. Изобразите геометрически множество истинности предиката p(X), решив систему неравенств:
   • 1.1.4. Постройте матрицу двуместного предиката p(X,y) и проверьте решение геометрически:
   • 1.1.5. Изобразите геометрически множество истинности двуместного предиката a(X, y).
   • 1.1.6. Изобразите геометрически множество истинности двуместного предиката q(X,y).
   • 1.2. Операции над предикатами и кванторами
   • 1. Пусть предикат q(X,y) определен на конечных множествах:
   • 1.3. Виды форм логики предикатов
   • 1. Приведите формулу логики предикатов к приведенной форме:
   • 2. Приведите формулу логики предикатов к приведенной форме, где X,y,z– вещественные переменные, применив отрицание к формуле:
   • 3. Приведите формулу логики предикатов к предваренной нормальной форме XyP(X, y)  XyQ(X, y).
   • 1.3.1. Приведите формулу логики предикатов к приведенной нормальной форме:
   • 1.3.2. Приведите формулы логики предикатов к приведенной нормальной форме, где X,y,z– вещественные переменны, применив отрицание к формуле:
   • 1.3.3. Приведите к предваренной нормальной форме следующие формулы логики предикатов:
   • 1.4. Применение логики предикатов
   • 1.4.1. Запишите аксиомы положительных величин на языке логики предикатов, используя ограниченные кванторы:
   • 9)Аксиома соизмеримости отрезков
   • 1.4.2. Запишите некоторые аксиомы действительных чисел на языке логики предикатов, используя ограниченные кванторы:
   • 1.4.3. Подберите элементарные предикаты и запишите следующие высказывания:
   • 1.4.4. Запишите определения на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
   • 1.4.5. Запишите определения на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
   • 1.4.6. Запишите теоремы и свойства на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
   • 0) Основная теорема алгебры.
   • 1.4.7. Запишите теоремы на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
   • Глава 2. Комбинаторика
   • 2.2. Размещения без повторений
   • 2.3. Размещения с повторениями
   • 2.4. Перестановки без повторений
   • 2.5. Перестановки с повторениями
   • 2.6. Инверсии. Обратные перестановки
   • 2.7. Сочетания без повторений
   • 2.8. Сочетания с повторениями
   • 2.9. Примеры решения сложных задач
   • 2.10. Треугольник Паскаля. Бином Ньютона
   • 1. Запишите разложение бинома:
   • 2. Вычислите без калькулятора:
   • 3. Запишите разложение бинома:
   • Зачетные задания по теме «Комбинаторика»
   • Глава 3. Графы
   • 3.1. Виды графов. Изоморфизм графов.
   • Основные положения о вершинах графа:
   • Алгоритм распознавания изоморфизма двух графов g1(X, e)и g2(y,e)
   • 2. Докажите, что графы g1(x1, e1) и g2(y2, e2) изоморфны.
   • 3. Решите задачу по вычислению валентности вершин графа
   • 4. Решите задачу по выявлению связности компонент графа
   • 3.1.5. Определите виды графов и подсчитайте валентность вершин:
   • 3.1.6. Определите виды графов и подсчитайте валентность вершин:
   • 3.1.7. Решите задачи по вычислению валентности вершин графа:
   • 3.1.8. Решите задачи по вычислению валентности вершин графа:
   • 3.1.9. Решите задачи по выявлению связности графа:
   • 3.2. Операции над графами
   • 3.2.1. Пусть заданы два графа g1(v1, e1) и g2(v2, e2). Изобразите геометрически объединение, пересечение и сумму по модулю два.
   • 3.3. Представление графов в пэвм
   • 3.3.1. Неориентированные графы
   • Способы задания графа:
   • Свойства матрицы смежности:
   • Свойства матрицы инцидентности:
   • 2. Граф g(V,e): задан геометрически.
   • 3. Графы g1(v1,e1) и g2(v2,e2) заданы геометрически.
   • 3.3.1.2. Постройте для графа g(V,e), заданного геометрически
   • 3.3.1.3. Дана матрица смежности графа. Задайте граф геометрически. Укажите: 1) матрицу инцидентности; 2) валентность вершин. 7)
   • Свойства матрицы инцидентности:
   • 1. Орграф g1(V,e) задан геометрически. Постройте для орграфа:
   • 2. Решите следующую задачу по обходу графов:
   • 3.3.2.2. Орграф задан геометрически. Укажите валентность вершин. Постройте матрицу смежности орграфа.
   • 3.3.2.3. Дана матрица смежности орграфа. А) Задайте орграф геометрически, в) постройте матрицу инцидентности.
   • 3.3.2.4. Дана матрица инцидентности орграфа. А) Задайте орграф геометрически, в) постройте матрицу смежности.
   • 3.3.2.5. Решите следующие задачи по обходу графов:
   • Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
   • 3.3.2.6. Решите следующие задачи по обходу графов:
   • 3.4. Задачи оптимизации на графах
   • 3. Задайте граф геометрически и решите задачу:
   • 3.5. Эйлеровы и гамильтоновы графы
   • Критерий эйлеровости графа
   • 1. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо "красный", либо "синий" граф не является плоским. 7)
   • 3.5.3. Граф задан геометрически. Выпишите гамильтонов цикл у данного графа, если он есть:
   • Глава 4. Автоматы
   • 4.1. Задачи анализа автоматов
   • 4.2. Задачи синтеза автоматов
   • Глава 5. Алгоритмы
   • 5.1.1. Опишите алгоритмы в словесной форме:
   • 5.1.2. Опишите алгоритмы в словесно-формульной форме:
   • 5.2. Виды алгоритмов
   • 5.2.1. Линейные алгоритмы
   • 1. Опишите графическим способом алгоритм расчета нормы расхода гербицида (л/га) по формуле:.
   • 1. Опишите алгоритмы в графической форме, в которых переменной d присваивают:
   • 2. Опишите алгоритмы в графической форме. Даны положительные вещественные числа X и y. Присвойте целой переменной z:
   • 5.2.2. Разветвляющиеся алгоритмы
   • 1. Опишите графическим способом алгоритм вычисления значения выражения:
   • 4. Даны действительные числа X, y и z. Вычислите:
   • 5.2.3. Циклические алгоритмы
   • Выход из цикла Выход из цикла
   • 1.Составьте блок-схему алгоритма вычисления среднеквадратической взвешенной по формуле:
   • 2.Составьте блок-схему алгоритма вычисления суммы кубов последовательности, состоящей из положительных чисел до первого введенного отрицательного числа.
   • 5.3. Применение теории алгоритмов. Машины Тьюринга
   • 1. Пусть требуется добавить 1 к натуральному числу n, представленному на ленте машины Тьюринга в двоичной системе счисления, то есть в алфавите {0,1}.
   • 3. Составьте программу машины Тьюринга, подсчитывающую число вхождений символа a в слово р в алфавите {a, b, c}.
   • 5.3.1. Постройте машину Тьюринга,
   • 5.3.2. Постройте машину Тьюринга, подсчитывающую
   • 5.3.3. Постройте машину Тьюринга, осуществляющую перевод натурального числа n
   • 5.3.4. Постройте машину Тьюринга,