Д и с к р е т н а м а т е м а т и к а
Індивідуальні завдання
МОДУЛЬ Б
(2 семестр)
для студентів І курсу
напряму підготовки 6.040302 „Інформатика”
Полтава – 2011
ЗАВДАННЯ ДЛЯ ІНДИВІДУАЛЬНОЇ РОБОТИ
МОДУЛЬ Б
(рік навчання 1, семестр 2)
Варіант№1
1. Побудуйте граф на множині 
бінарного відношення 
числа х та у взаємно прості. Побудуйте матрицю суміжностей та матрицю інциденцій цього графа.
2. Деякі з міст Р1, Р2, ... , P1983 попарно з'єднані авіалініями, що належать компаніям А1, ... , А10. Відомо, що із кожного міста можна перелетіти в інше місто без пересадок, і, що кожна авіалінія діє в обох напрямках. Довести, що існує хоча б одна компанія, яка може забезпечити подорож із початком і закінченням в одному і тому ж місті із непарним числом використаних авіаліній.
3. Зібралось n осіб. Деякі із них знайомі між собою, причому кожні двоє незнайомих мають точно два спільних знайомих, а кожні двоє знайомих не мають спільних знайомих. Довести, що кожний із присутніх знайомий з однаковим числом осіб.
4. Турист, який приїхав до Києва поїздом увесь день ходив по місту пішки. Повечерявши на Голосіївській площі він вирішив повернутись на вокзал, слідуючи тими вулицями, які він вже проходив непарне число разів. Довести, що турист зможе повернутися на вокзал.
