Дискретная Математика
Элементы теории графов
Приведенный ниже материал далеко не исчерпывает разнообразные разделы общей теории графов, содержит некоторые факты из общей теории, (которые за неимением времени можно даже опускать), а основное внимание уделяется приложениям к теории сетей связи. На взгляд авторов центральной частью раздела является нахождение путей и сечений (разрезов) методами булевой алгебры и теорема Форда–Фалкерсона. Именно из этих разделов и предлагаются индивидуальные задания.
Содержание
- Cодержание:
- Логические (булевы) функции
- 1. Основные логические функции
- Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).
- 2. Свойства конъюнкции, дизъюнкции и отрицания
- 3. Днф, сднф, кнф, скнф
- 4. Представление логических функций в виде сднф (скнф)
- 5. Нахождение сокращенной днф по таблице истинности (карты Карно)
- 6. Полиномы Жегалкина
- 7. Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций. Полные наборы. Базисы
- 8. Некоторые приложения теории булевых функций
- 8.1. Функциональные элементы и схемы
- 8.2. Решение логических задач с помощью теории булевых функций
- Элементы теории графов
- 9. Общие понятия теории графов
- 10. Эйлеровы и полуэйлеровы графы
- 11. Матрицы и графы. Нахождение путей и сечений с помощью структурной матрицы
- 12. Сети, потоки в сетях. Теорема Форда – Фалкерсона
- 13. Раскраска графа
- 14. Деревья и их простейшие свойства
- 15. Решение типовых задач
- Литература