Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Питання до коловіуму з дисципліни „Дискретна математика”

Питання до коловіуму з дисципліни „Дискретна математика”




Дата конвертації02.05.2017
Розмір15.9 Kb.

Питання до коловіуму з дисципліни
„Дискретна математика”


  1. Відношення, характеристичний предикат. Операції над відношеннями: проекція та згортка.

  2. Бінарні відношення спеціальних типів: рефлексивні, анти рефлексивні, симетричні, антисиметричні, транзитивні. Замикання відношення.

  3. Відношення еквівалентності. Теорема про розбиття на класи еквівалентності (з доведенням). Фактор-множина.

  4. Лишки за модулем. Порядок елемента за модулем. Мала теорема Ферма (з доведенням).
    Мала теорема Ферма - одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 18 жовтня 1640 року. В листі проте не було наведено доведення.


  5. Відношення часткового порядку. Частково-впорядкована множина. Відношення лінійного порядку. Ізоморфізм частково-впорядкованих множин.

  6. Прямий та зворотній лексикографічний порядок.
    Частково впорядкованою множиною ( P , ⩽ ) , називається множина P із заданим на ній рефлексивним, антисиметричним та транзитивним бінарним відношенням ⩽ (називається - відношення нестрогого порядку).
    Лексикографічний порядок - відношення лінійного порядку на множині кортежей Σ ∗ } ; Σ - упорядкований алфавіт. Свою назву лексикографічний порядок отримав по аналогії з сортуванням по алфавіту в словнику.
    Максимальний, мінімальний, найбільший, найменший елемент. Верхня, нижня грань, супремум, інфімум множини.
    Точна верхня межа (верхня грань) і точна нижня межа (нижня грань) - узагальнення понять максимуму та мінімуму відповідно.
    Решітка. Повна решітка.

  7. Загальний орієнтований та неорієнтований графи. Простий граф, повний та цілком незв’язний. Поняття суміжності, інцидентності, степеня, регулярності. Лема про рукопотискання (з доведенням).

  8. Матриці суміжності та інцидентності. Ізоморфізм простих графів. Дводольний граф. Операції над графами.

  9. Маршрути, ланцюги, цикли. Лема про існування циклу (з доведенням).

  10. Компоненти зв’язності. Мости. Теорема про зв’язок між кількістю вершин, ребер та компонент зв’язності графа (з доведенням).

  11. Ейлерові, напівейлерові графи. Теорема про ейлеровість графа (з доведенням).

  12. Теорема про напівейлеровість графа (з доведенням).

  13. Гамільтонові та ніпівгамільтонові графи. Теорема Діріка (з доведенням).

  14. Ліс, дерево. Лема про ребро лісу або дерева (з доведенням). Теорема про еквівалентність шести умов для деякого простого графа (з доведенням).

  15. Розфарбування графів. Хроматичне число. Лема про хроматичне число (з доведенням).

  16. Планарні графи. Розфарбування планарних графів.
    Хроматичне число графа G - мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається χ(G).
    Планарний граф - граф, який може бути зображений на площині без перетину ребер.
    Теорема Ейлера та наслідок з неї (з доведенням).

  17. Гомеоморфізм простих графів. Теорема Кураторського.

Список джерел, достатніх для підготовки до колоквіуму


  1. Конспект лекцій.

  2. http://www.ukma.kiev.ua/bogd/Discrete Mathematics/PosibnykDiscr.pdf



  • Мала теорема Ферма
  • Хроматичне число